1.ArrayList mengimplementasikan struktur data berdasarkan array dinamis, dan LinkedList mengimplementasikan struktur data berdasarkan daftar tertaut.
2. Untuk mendapatkan dan mengatur akses acak, ArrayList lebih baik daripada LinkedList karena ArrayList dapat diposisikan secara acak, sedangkan LinkedList perlu memindahkan penunjuk ke node selangkah demi selangkah. (Pikirkan dengan mengacu pada array dan daftar tertaut)
3. Untuk operasi baru dan penghapusan, LinedList lebih menguntungkan, hanya perlu memodifikasi pointer, sedangkan ArrayList perlu memindahkan data untuk mengisi ruang objek yang dihapus.
ArrayList dan LinkedList adalah dua kelas koleksi yang digunakan untuk menyimpan serangkaian referensi objek. Misalnya, kita bisa menggunakan ArrayList untuk menyimpan rangkaian String atau Integer. Lalu apa perbedaan performa antara ArrayList dan LinkedList? Kapan sebaiknya Anda menggunakan ArrayList dan kapan sebaiknya Anda menggunakan LinkedList?
satu. kompleksitas waktu
Poin penting pertama adalah bahwa implementasi internal ArrayList didasarkan pada array objek dasar. Oleh karena itu, ketika menggunakan metode get untuk mengakses elemen apa pun dalam daftar (akses acak), ini lebih cepat daripada LinkedList. Metode get di LinkedList memeriksa dari satu ujung daftar ke ujung lainnya secara berurutan. Untuk LinkedList, tidak ada cara yang lebih cepat untuk mengakses elemen tertentu dalam daftar.
Misalkan kita memiliki daftar yang besar, dan elemen di dalamnya telah diurutkan. Daftar ini mungkin bertipe ArrayList atau tipe LinkedList. Sekarang kita melakukan pencarian biner pada daftar ini. lihat program berikut:
Waktu LinkedList yang digunakan: 2596
Hasil ini tidak tetap, tetapi pada dasarnya waktu ArrayList jauh lebih sedikit dibandingkan waktu LinkedList. Oleh karena itu LinkedList tidak boleh digunakan dalam kasus ini. Metode pencarian biner menggunakan strategi akses acak (randomaccess), dan LinkedList tidak mendukung akses acak cepat. Waktu yang digunakan oleh akses acak ke LinkedList sebanding dengan ukuran daftar. Sejalan dengan itu, waktu yang digunakan untuk akses acak di ArrayList adalah tetap.
Apakah ini berarti ArrayList selalu berkinerja lebih baik daripada LinkedList? Hal ini belum tentu benar, dalam beberapa kasus LinkedList berkinerja lebih baik daripada ArrayList, dan beberapa algoritme lebih efisien bila diterapkan di LinkedList. Misalnya, performanya lebih baik saat menggunakan metode Collections.reverse untuk membalikkan daftar.
Lihat contoh seperti itu, jika kita memiliki daftar dan ingin melakukan operasi penyisipan dan penghapusan dalam jumlah besar, dalam hal ini LinkedList adalah pilihan yang lebih baik. Perhatikan contoh ekstrem berikut, di mana kita berulang kali menyisipkan elemen di awal daftar:
Saat ini, output saya adalah: ArrayList membutuhkan: 2463
LinkedList membutuhkan: 15
Ini benar-benar kebalikan dari hasil contoh sebelumnya. Ketika sebuah elemen ditambahkan ke awal ArrayList, semua elemen yang ada akan dipindahkan ke belakang, yang berarti overhead perpindahan dan penyalinan data. Sebaliknya, menambahkan elemen ke awal LinkedList hanya menetapkan catatan ke elemen dan kemudian menyesuaikan dua link. Biaya penambahan elemen di awal LinkedList adalah tetap, sedangkan biaya penambahan elemen di awal ArrayList sebanding dengan ukuran ArrayList.
dua. kompleksitas ruang
Ada kelas dalam pribadi di LinkedList, yang didefinisikan sebagai berikut:
Entri kelas statis pribadi {
elemen objek;
Masuk berikutnya;
Entri sebelumnya;
}
Setiap objek Entri mereferensikan elemen dalam daftar, serta elemen sebelumnya dan elemen berikutnya dalam LinkedList. Objek LinkedList dengan 1000 elemen akan memiliki 1000 objek Entri yang ditautkan bersama, masing-masing objek terkait dengan elemen dalam daftar. Dalam hal ini, akan ada banyak ruang overhead dalam struktur LinkedList, karena struktur tersebut perlu menyimpan informasi yang relevan dari 1000 objek Entitas tersebut.
ArrayList menggunakan array bawaan untuk menyimpan elemen. Kapasitas awal array ini adalah 10. Ketika array perlu bertambah, kapasitas baru diperoleh sesuai dengan rumus berikut: kapasitas baru = (kapasitas lama*3)/2+ 1, artinya Kapasitas akan meningkat sekitar 50% setiap kali. Artinya jika Anda memiliki objek ArrayList dengan jumlah elemen yang banyak, Anda akan mendapatkan banyak ruang yang terbuang. Pemborosan ini disebabkan oleh cara kerja ArrayList. Jika tidak ada cukup ruang untuk menyimpan elemen baru, array harus dialokasikan ulang agar elemen baru dapat ditambahkan. Mengalokasikan kembali array akan menyebabkan penurunan kinerja secara drastis. Jika kita mengetahui berapa banyak elemen yang dimiliki ArrayList, kita dapat menentukan kapasitasnya melalui konstruktor. Kita juga dapat menggunakan metode trimToSize untuk menghapus ruang yang terbuang setelah ArrayList dialokasikan.
tiga. Meringkaskan
ArrayList dan LinkedList masing-masing memiliki kelebihan dan kekurangan dalam hal kinerja, dan masing-masing memiliki penerapannya sendiri-sendiri.
Ringkasan kinerja:
| - | operasi tambahkan() | hapus() operasi | operasi penyisipan | operasi nilai indeks | operasi nilai iterator |
|---|---|---|---|---|---|
| Daftar Array/Vektor/Tumpukan | Bagus | Perbedaan | Perbedaan | Bagus sekali | Bagus sekali |
| Daftar Tertaut | Bagus | Bagus | Bagus | Perbedaan | Bagus sekali |
1. Untuk ArrayList dan LinkedList, biaya penambahan elemen di akhir daftar adalah tetap. Untuk ArrayList, ini terutama menambahkan item ke array internal, menunjuk ke elemen yang ditambahkan, yang terkadang menyebabkan array dialokasikan kembali; untuk LinkedList, overhead ini seragam, mengalokasikan objek Entri internal.
2. Memasukkan atau menghapus elemen di tengah-tengah ArrayList berarti elemen-elemen yang tersisa dalam daftar akan dipindahkan; sedangkan memasukkan atau menghapus elemen di tengah-tengah LinkedList memiliki biaya tetap.
3． LinkedList tidak mendukung akses elemen acak yang efisien.
4． Pemborosan ruang di ArrayList terutama tercermin dalam pemesanan sejumlah ruang di akhir daftar, sedangkan konsumsi ruang di LinkedList tercermin dalam setiap elemen di dalamnya perlu mengonsumsi sejumlah besar ruang.
Dapat dikatakan seperti ini: Ketika operasinya adalah menambahkan data setelah kolom data, bukan di depan atau tengah, dan Anda perlu mengakses elemen secara acak, menggunakan ArrayList akan memberikan kinerja yang lebih baik ketika operasi Anda berada di depan kolom data Saat Anda menambah atau menghapus data di tengah dan mengakses elemen secara berurutan, Anda harus menggunakan LinkedList.
Perbedaan antara ArrayList dan List di java
Koleksi daftar
Daftar mewarisi dari antarmuka Koleksi. Daftar adalah kumpulan yang diurutkan. Elemen-elemen dalam Daftar dapat diperoleh/dihapus/dimasukkan berdasarkan indeks (nomor urut: informasi posisi elemen dalam koleksi).
Berbeda dengan koleksi Set, Daftar mengizinkan elemen duplikat. Untuk elemen objek e1 dan e2 yang memenuhi ketentuan e1.equals(e2), elemen tersebut dapat berada dalam koleksi Daftar pada saat yang bersamaan. Tentu saja, ada juga kelas implementasi Daftar yang tidak mengizinkan elemen duplikat.
Pada saat yang sama, List juga menyediakan metode listIterator(), yang mengembalikan objek antarmuka ListIterator. Dibandingkan dengan antarmuka Iterator, ListIterator menambahkan metode untuk menambah, menghapus, dan mengatur elemen, dan juga dapat melintasi maju atau mundur.
Hubungan antara Daftar dan Koleksi:
java.util.Koleksi[I]
+--java.util.Daftar[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vektor [C]
+--java.util.Stack [C]
Kelas implementasi antarmuka Daftar terutama mencakup ArrayList, LinkedList, Vector, Stack, dll.
Hubungan ayah-anak.
Daftar adalah sebuah antarmuka, dan ArrayList mewarisi antarmuka ini dan mengimplementasikannya.
Saat menggunakannya, saya biasanya menggunakan ArrayList. Saya belum pernah menggunakan List. Anda bisa menggunakannya seperti ini: List list = new ArrayList();
Antarmuka koleksi
Koleksi adalah antarmuka koleksi paling dasar. Koleksi mewakili sekumpulan Objek, yaitu elemen Koleksi. Beberapa Koleksi mengizinkan elemen yang identik dan yang lainnya tidak. Ada yang semacam dan ada yang tidak. Java SDK tidak menyediakan kelas yang mewarisi langsung dari Koleksi. Kelas yang disediakan oleh Java SDK semuanya merupakan "sub-antarmuka" yang mewarisi dari Koleksi, seperti Daftar dan Set.
Semua kelas yang mengimplementasikan antarmuka Koleksi harus menyediakan dua konstruktor standar: konstruktor tanpa parameter untuk membuat Koleksi kosong, dan konstruktor parameter Koleksi untuk membuat Koleksi baru. Input Collection memiliki elemen yang sama. Konstruktor terakhir memungkinkan pengguna untuk menyalin Koleksi.
Bagaimana cara mengulangi setiap elemen dalam Koleksi? Terlepas dari tipe Koleksi sebenarnya, ini mendukung metode iterator(), yang mengembalikan iterator yang dapat digunakan untuk mengakses setiap elemen dalam Koleksi satu per satu. Penggunaan umumnya adalah sebagai berikut:
Iterator it = collection.iterator(); // Dapatkan iterator
while(it.hasNext()) {
Objek obj = it.next(); // Dapatkan elemen selanjutnya
}
Dua antarmuka yang berasal dari antarmuka Koleksi adalah Daftar dan Set.
Antarmuka daftar:
Daftar adalah Koleksi yang diurutkan. Dengan menggunakan antarmuka ini, Anda dapat mengontrol posisi penyisipan setiap elemen dengan tepat. Pengguna dapat mengakses elemen dalam Daftar menggunakan indeks (posisi elemen dalam Daftar, mirip dengan subskrip array), yang mirip dengan array Java.
Berbeda dengan Set yang disebutkan di bawah, List mengizinkan elemen yang sama.
Selain metode iterator() yang diperlukan untuk antarmuka Koleksi, List juga menyediakan metode listIterator(), yang mengembalikan antarmuka ListIterator, Dibandingkan dengan antarmuka Iterator standar, ListIterator memiliki lebih banyak add() dan metode lainnya, yang memungkinkan penambahan. Hapus, atur elemen, dan lintasi maju atau mundur.
Kelas umum yang mengimplementasikan antarmuka Daftar adalah LinkedList, ArrayList, Vector dan Stack.
kelas LinkedList
LinkedList mengimplementasikan antarmuka Daftar dan mengizinkan elemen nol. Selain itu, LinkedList menyediakan metode dapatkan, hapus, dan sisipkan tambahan di bagian awal atau akhir LinkedList. Operasi ini memungkinkan LinkedList digunakan sebagai tumpukan, antrian, atau deque.
Perhatikan bahwa LinkedList tidak memiliki metode yang disinkronkan. Jika beberapa thread mengakses Daftar secara bersamaan, mereka harus menerapkan sinkronisasi akses sendiri. Salah satu solusinya adalah dengan membuat Daftar yang disinkronkan saat membuat Daftar:
Daftar daftar = Koleksi.synchronizedList(new LinkedList(...));
kelas Daftar Array
ArrayList mengimplementasikan array berukuran variabel. Ini mengizinkan semua elemen, termasuk null. ArrayList tidak disinkronkan.
Waktu berjalan metode size, isEmpty, get, dan set adalah konstan. Namun, biaya metode penjumlahan merupakan konstanta diamortisasi, dan penambahan n elemen memerlukan waktu O(n). Metode lain memiliki waktu berjalan linier.
Setiap instance ArrayList memiliki kapasitas (Capacity), yaitu ukuran array yang digunakan untuk menyimpan elemen. Kapasitas ini meningkat secara otomatis seiring dengan penambahan elemen baru, namun algoritma pertumbuhannya tidak ditentukan. Ketika sejumlah besar elemen perlu dimasukkan, metode sureCapacity dapat dipanggil untuk meningkatkan kapasitas ArrayList sebelum memasukkan guna meningkatkan efisiensi penyisipan.
Seperti LinkedList, ArrayList juga tidak disinkronkan.
Ringkasan: Jika operasi seperti tumpukan dan antrian terlibat, Anda harus mempertimbangkan untuk menggunakan Daftar. Jika Anda perlu menyisipkan dan menghapus elemen dengan cepat, Anda harus menggunakan LinkedList. Jika Anda memerlukan akses acak cepat ke elemen, Anda harus menggunakan ArrayList.
Cobalah untuk mengembalikan antarmuka daripada tipe sebenarnya, seperti mengembalikan Daftar alih-alih ArrayList, sehingga jika Anda perlu mengganti ArrayList dengan LinkedList di masa mendatang, kode klien tidak perlu diubah. Ini adalah pemrograman untuk abstraksi.