Saya selalu menjadi orang yang hanya menggunakan:
List<String> names = new ArrayList<>();
Saya menggunakan antarmuka sebagai nama tipe untuk portabilitas , sehingga ketika saya mengajukan pertanyaan seperti ini, saya dapat mengerjakan ulang kode saya.
Kapan harus LinkedList
digunakan ArrayList
dan sebaliknya?
java
arraylist
collections
linked-list
sdellysse
sumber
sumber
Jawaban:
Ringkasan
ArrayList
denganArrayDeque
lebih disukai dalam banyak kasus penggunaan daripadaLinkedList
. Jika Anda tidak yakin - mulailah denganArrayList
.LinkedList
danArrayList
dua implementasi berbeda dari antarmuka Daftar.LinkedList
mengimplementasikannya dengan daftar yang ditautkan dua kali lipat.ArrayList
mengimplementasikannya dengan array pengubahan ukuran secara dinamis.Seperti halnya operasi daftar dan larik standar, berbagai metode akan memiliki runtime algoritmik yang berbeda.
Untuk
LinkedList<E>
get(int index)
adalah O (n) (dengan n / 4 langkah rata-rata), tetapi O (1) ketikaindex = 0
atauindex = list.size() - 1
(dalam hal ini, Anda juga dapat menggunakangetFirst()
dangetLast()
). Salah satu manfaat utamaLinkedList<E>
add(int index, E element)
adalah O (n) (dengan n / 4 langkah rata-rata), tetapi O (1) ketikaindex = 0
atauindex = list.size() - 1
(dalam hal ini, Anda juga dapat menggunakanaddFirst()
danaddLast()
/add()
). Salah satu manfaat utamaLinkedList<E>
remove(int index)
adalah O (n) (dengan n / 4 langkah rata-rata), tetapi O (1) ketikaindex = 0
atauindex = list.size() - 1
(dalam hal ini, Anda juga dapat menggunakanremoveFirst()
danremoveLast()
). Salah satu manfaat utamaLinkedList<E>
Iterator.remove()
adalah O (1) . Salah satu manfaat utamaLinkedList<E>
ListIterator.add(E element)
adalah O (1) . Salah satu manfaat utamaLinkedList<E>
Catatan: Banyak operasi membutuhkan n / 4 langkah rata-rata, jumlah langkah konstan dalam kasus terbaik (misalnya indeks = 0), dan langkah n / 2 dalam kasus terburuk (tengah daftar)
Untuk
ArrayList<E>
get(int index)
adalah O (1) . Manfaat utamaArrayList<E>
add(E element)
adalah O (1) diamortisasi, tetapi O (n) terburuk karena array harus diubah ukurannya dan disalinadd(int index, E element)
adalah O (n) (dengan n / 2 langkah rata-rata)remove(int index)
adalah O (n) (dengan n / 2 langkah rata-rata)Iterator.remove()
adalah O (n) (dengan n / 2 langkah rata-rata)ListIterator.add(E element)
adalah O (n) (dengan n / 2 langkah rata-rata)Catatan: Banyak operasi membutuhkan n / 2 langkah rata-rata, jumlah langkah konstan dalam kasus terbaik (akhir daftar), n langkah dalam kasus terburuk (awal daftar)
LinkedList<E>
memungkinkan penyisipan atau pemindahan waktu-konstan menggunakan iterator , tetapi hanya akses berurutan elemen. Dengan kata lain, Anda dapat berjalan daftar ke depan atau ke belakang, tetapi menemukan posisi dalam daftar membutuhkan waktu sebanding dengan ukuran daftar. Javadoc mengatakan "operasi yang mengindeks ke dalam daftar akan melintasi daftar dari awal atau akhir, mana yang lebih dekat" , sehingga metode tersebut rata-rata adalah O (n) ( n / 4 langkah), meskipun O (1) untukindex = 0
.ArrayList<E>
, di sisi lain, memungkinkan akses baca acak cepat, sehingga Anda dapat mengambil elemen apa pun dalam waktu yang konstan. Tetapi menambahkan atau menghapus dari mana saja tetapi akhirnya membutuhkan pergeseran semua elemen yang terakhir, baik untuk membuat celah atau mengisi celah. Juga, jika Anda menambahkan lebih banyak elemen daripada kapasitas array yang mendasarinya, array baru (1,5 kali ukuran) dialokasikan, dan array lama disalin ke yang baru, jadi menambahkan keArrayList
is O (n) di yang terburuk kasus tetapi konstan rata-rata.Jadi tergantung pada operasi yang ingin Anda lakukan, Anda harus memilih implementasi yang sesuai. Iterasi atas kedua jenis Daftar itu praktis sama murahnya. (Iterasi lebih
ArrayList
cepat secara teknis, tetapi kecuali Anda melakukan sesuatu yang benar-benar peka terhadap kinerja, Anda tidak perlu khawatir tentang hal ini - mereka berdua adalah konstanta.)Manfaat utama menggunakan
LinkedList
timbul ketika Anda kembali menggunakan iterator yang ada untuk menyisipkan dan menghapus elemen. Operasi ini kemudian dapat dilakukan di O (1) dengan mengubah daftar hanya secara lokal. Dalam daftar array, sisa array perlu dipindahkan (yaitu disalin). Di sisi lain, mencari denganLinkedList
cara mengikuti tautan di O (n) ( langkah n / 2 ) untuk kasus terburuk, sedangkan dalamArrayList
posisi yang diinginkan dapat dihitung secara matematis dan diakses di O (1) .Manfaat lain dari menggunakan
LinkedList
muncul ketika Anda menambah atau menghapus dari kepala daftar, karena operasi tersebut adalah O (1) , sedangkan mereka adalah O (n) untukArrayList
. Perhatikan bahwaArrayDeque
mungkin merupakan alternatif yang baikLinkedList
untuk menambah dan menghapus dari kepala, tetapi itu bukanList
.Juga, jika Anda memiliki daftar besar, perlu diingat bahwa penggunaan memori juga berbeda. Setiap elemen dari
LinkedList
memiliki lebih banyak overhead karena pointer ke elemen berikutnya dan sebelumnya juga disimpan.ArrayLists
tidak memiliki overhead ini. Namun,ArrayLists
gunakan memori sebanyak yang dialokasikan untuk kapasitas, terlepas dari apakah elemen telah ditambahkan.Kapasitas awal default suatu
ArrayList
cukup kecil (10 dari Java 1.4 - 1.8). Tetapi karena implementasi yang mendasarinya adalah sebuah array, array harus diubah ukurannya jika Anda menambahkan banyak elemen. Untuk menghindari perubahan ukuran biaya tinggi ketika Anda tahu Anda akan menambahkan banyak elemen, buatArrayList
dengan kapasitas awal yang lebih tinggi.sumber
O(n/2)
atauO(n/4)
. Notasi O besar memberitahu Anda bagaimana skala operasi dengan n lebih besar . dan suatu operasi yang membutuhkann/2
langkah - langkah berskala persis seperti operasi yang membutuhkann
langkah - langkah, yang merupakan alasan mengapa jumlah atau faktor konstan dihilangkan.O(n/2)
danO(n/4)
keduanya adilO(n)
.LinkedList
danArrayList
memiliki faktor konstan yang berbeda, jadi tidak masuk akal untuk membandingkanO(n/2)
satuO(n/4)
dari yang lain, keduanya hanya menunjukkan operasi penskalaan linear.Sejauh ini, tidak ada yang tampaknya telah membahas jejak memori dari masing-masing daftar ini selain konsensus umum bahwa a
LinkedList
adalah "lebih banyak" daripadaArrayList
jadi saya melakukan sejumlah angka untuk menunjukkan dengan tepat berapa banyak kedua daftar tersebut digunakan untuk referensi N null.Karena referensi adalah 32 atau 64 bit (bahkan ketika nol) pada sistem relatif mereka, saya telah memasukkan 4 set data untuk 32 dan 64 bit
LinkedLists
danArrayLists
.Catatan: Ukuran yang ditunjukkan untuk
ArrayList
garis adalah untuk daftar yang dipangkas - Dalam praktiknya, kapasitas array dukungan dalamArrayList
umumnya lebih besar dari jumlah elemen saat ini.Catatan 2: (terima kasih BeeOnRope) Karena CompressedOops adalah default sekarang dari pertengahan JDK6 ke atas, nilai-nilai di bawah ini untuk mesin 64-bit pada dasarnya akan cocok dengan rekan-rekan 32-bit mereka, kecuali tentu saja Anda mematikannya secara khusus.
Hasilnya jelas menunjukkan bahwa
LinkedList
jauh lebih banyak daripadaArrayList
, terutama dengan jumlah elemen yang sangat tinggi. Jika ingatan merupakan faktor, jauhiLinkedLists
.Rumus yang saya gunakan mengikuti, beri tahu saya jika saya telah melakukan kesalahan dan saya akan memperbaikinya. 'b' adalah 4 atau 8 untuk sistem 32 atau 64 bit, dan 'n' adalah jumlah elemen. Perhatikan alasan mod adalah karena semua objek di java akan memakan banyak ruang 8 byte terlepas dari apakah semuanya digunakan atau tidak.
Daftar Array:
ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)
LinkedList:
LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
sumber
int
, jadi 4 atau 8 byte data. Dalam daftar tertaut, pada dasarnya ada 4 "kata" overhead. Grafik Anda dengan demikian memberikan kesan bahwa daftar tertaut menggunakan "lima kali" penyimpanan daftar array. Ini salah. Overhead adalah 16 atau 32 byte per objek, sebagai penyesuaian tambahan, bukan faktor penskalaan.CompressedOops
default sekarang dalam semua JDKs baru-baru ini (7, 8 dan update dari 6 selama beberapa tahun), sehingga 64-bit tidak akan membuat perbedaan dalamArrayList
atauLinkedList
ukuran, kecuali Anda secara eksplisit dimatikan oops dikompresi untuk beberapa alasan.ArrayList
tanpa menentukan kapasitas awal, itu masih akan menggunakan memori yang jauh lebih sedikit daripada aLinkedList
.ArrayList
adalah apa yang kamu inginkan.LinkedList
hampir selalu merupakan bug (kinerja).Kenapa
LinkedList
menyebalkan:ArrayList
digunakan.ArrayList
, itu mungkin akan secara signifikan lebih lambat.LinkedList
sumbernya karena itu mungkin pilihan yang salah.sumber
Sebagai seseorang yang telah melakukan rekayasa kinerja operasional pada layanan web SOA skala sangat besar selama sekitar satu dekade, saya lebih suka perilaku LinkedList daripada ArrayList. Sementara throughput steady-state dari LinkedList lebih buruk dan karena itu dapat menyebabkan pembelian lebih banyak perangkat keras - perilaku ArrayList di bawah tekanan dapat menyebabkan aplikasi dalam sebuah cluster memperluas array mereka dalam sinkronisasi dekat dan untuk ukuran array yang besar dapat menyebabkan kurangnya responsif dalam aplikasi dan pemadaman, sementara di bawah tekanan, yang merupakan perilaku bencana.
Demikian pula, Anda bisa mendapatkan throughput yang lebih baik dalam aplikasi dari pengumpul sampah bertenor throughput throughput default, tetapi begitu Anda mendapatkan aplikasi java dengan tumpukan 10GB, Anda dapat mengunci aplikasi selama 25 detik selama GC penuh yang menyebabkan batas waktu dan kegagalan pada aplikasi SOA dan hancurkan SLA Anda jika itu terjadi terlalu sering. Meskipun kolektor CMS membutuhkan lebih banyak sumber daya dan tidak mencapai throughput mentah yang sama, itu adalah pilihan yang jauh lebih baik karena memiliki latensi yang lebih mudah diprediksi dan lebih kecil.
ArrayList hanya pilihan yang lebih baik untuk kinerja jika yang Anda maksud dengan kinerja adalah throughput dan Anda dapat mengabaikan latensi. Dalam pengalaman saya di pekerjaan saya, saya tidak bisa mengabaikan latensi terburuk.
sumber
LinkedList
selalu mengalokasikan memori lima kali lipat dari array referensi biasa, jadiArrayList
sementara yang membutuhkan 2,5 kali masih mengkonsumsi memori jauh lebih sedikit, bahkan ketika memori tidak direklamasi. Karena alokasi array besar melewati ruang Eden, mereka tidak memiliki dampak pada perilaku GC, kecuali benar-benar tidak cukup memori, dalam hal ini, yangLinkedList
meledak jauh lebih awal ...LinkedList
hanya perlu sepotong kecil memori bebas untuk mengalokasikan untuk elemen selanjutnya.ArrayList
akan membutuhkan blok ruang bebas yang besar dan berkesinambungan untuk mengalokasikan array yang diubah ukurannya. Jika tumpukan menjadi terfragmentasi, maka GC mungkin akan menata ulang seluruh tumpukan hanya untuk membebaskan satu blok memori yang sesuai.Algoritma: Notasi Besar-Oh
ArrayLists baik untuk write-once-read-many atau appenders, tetapi buruk untuk add / remove dari depan atau tengah.
sumber
O(1)
. Itu harus dijalankan melalui setengah daftar untuk menemukan titik penyisipan.LinkedList
adalahO(1)
jika Anda memiliki iterator ke posisi memasukkan , yaituListIterator.add
seharusnyaO(1)
untuk aLinkedList
.Ya, saya tahu, ini adalah pertanyaan kuno, tapi saya akan memasukkan dua sen:
LinkedList hampir selalu merupakan pilihan yang salah, berdasarkan kinerja. Ada beberapa algoritma yang sangat spesifik di mana LinkedList dipanggil, tetapi itu sangat, sangat langka dan algoritma biasanya akan secara khusus bergantung pada kemampuan LinkedList untuk memasukkan dan menghapus elemen di tengah daftar secara relatif cepat, setelah Anda menavigasi ke sana. dengan ListIterator.
Ada satu kasus penggunaan umum di mana LinkedList mengungguli ArrayList: antrian. Namun, jika sasaran Anda adalah kinerja, alih-alih LinkedList, Anda juga harus mempertimbangkan untuk menggunakan ArrayBlockingQueue (jika Anda dapat menentukan batas atas pada ukuran antrian Anda sebelumnya, dan mampu mengalokasikan semua memori di muka), atau implementasi CircularArrayList ini . (Ya, ini dari tahun 2001, jadi Anda harus membuatnya, tapi saya mendapat rasio kinerja yang sebanding dengan apa yang dikutip dalam artikel tadi di JVM baru-baru ini)
sumber
ArrayDeque
. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.htmlArrayDeque
lebih lambat daripadaLinkedList
kecuali semua operasi pada ujung yang sama. Tidak apa-apa bila digunakan sebagai tumpukan tetapi tidak membuat antrian yang baik.ArrayDeque
cenderung lebih cepat daripadaStack
saat digunakan sebagai tumpukan, dan lebih cepat dariLinkedList
saat digunakan sebagai antrian.ArrayDeque
dokumentasi.Ini pertanyaan efisiensi.
LinkedList
cepat untuk menambah dan menghapus elemen, tetapi lambat untuk mengakses elemen tertentu.ArrayList
cepat untuk mengakses elemen tertentu tetapi bisa lambat untuk menambahkan ke kedua ujungnya, dan terutama lambat untuk menghapus di tengah.Array vs ArrayList vs LinkedList vs Vector berjalan lebih mendalam, seperti halnya Linked List .
sumber
Benar atau Salah: Silakan jalankan tes secara lokal dan putuskan sendiri!
Edit / Hapus lebih cepat
LinkedList
daripadaArrayList
.ArrayList
, didukung olehArray
, yang perlu dua kali lipat ukuran, lebih buruk dalam aplikasi volume besar.Di bawah ini adalah hasil tes unit untuk setiap operasi. Waktu diberikan dalam Nanosecond.
Berikut kodenya:
sumber
LinkedList
memiliki overhead memori yang jauh lebih besar karena untuk setiap elemen ada objek simpul dengan lima bidang. Pada banyak sistem yang membuat overhead 20 byte. Overhead memori rata-rata per elemenArrayList
adalah satu setengah kata, yang menghasilkan 6 byte, dan 8 byte dalam kasus terburuk.removeIf(element -> condition)
mana yang cocok, yang bisa secara signifikan lebih cepat untukArrayList
, dibandingkan dengan perulangan dan menghapus melalui iterator, karena tidak diperlukan untuk menggeser seluruh sisa untuk setiap elemen individu. Apakah ini berkinerja lebih baik atau lebih buruk daripadaLinkedList
tergantung pada skenario tertentu, sepertiLinkedList
O (1) dalam teori, tetapi menghapus hanya satu node memerlukan beberapa akses memori, yang dapat dengan mudah melebihi jumlah yang diperlukan untukArrayList
saat menghapus sejumlah besar elemen .ArrayList
pada dasarnya adalah sebuah array.LinkedList
diimplementasikan sebagai daftar yang ditautkan ganda.The
get
cukup jelas. O (1) untukArrayList
, karenaArrayList
memungkinkan akses acak dengan menggunakan indeks. O (n) untukLinkedList
, karena perlu mencari indeks terlebih dahulu. Catatan: ada beberapa versiadd
danremove
.LinkedList
lebih cepat dalam menambah dan menghapus, tetapi lebih lambat di dapatkan. Secara singkat,LinkedList
sebaiknya lebih disukai jika:=== ArrayList ===
=== LinkedList ===
tambah (E e)
tambah (indeks int, elemen E)
Berikut adalah gambar dari programcreek.com (
add
danremove
merupakan tipe pertama, yaitu, tambahkan elemen di akhir daftar dan hapus elemen pada posisi yang ditentukan dalam daftar.):sumber
Joshua Bloch, penulis LinkedList:
Tautan: https://twitter.com/joshbloch/status/583813919019573248
Saya minta maaf karena jawabannya tidak informatif seperti jawaban lainnya, tapi saya pikir itu akan menjadi yang paling menarik dan cukup jelas.
sumber
ArrayList
diakses secara acak, sementaraLinkedList
sangat murah untuk memperluas dan menghapus elemen dari. Untuk sebagian besar kasus,ArrayList
tidak masalah.Kecuali Anda telah membuat daftar besar dan mengukur kemacetan, Anda mungkin tidak perlu khawatir tentang perbedaannya.
sumber
TL; DR karena arsitektur komputer modern,
ArrayList
akan jauh lebih efisien untuk hampir semua kasus penggunaan yang mungkin - dan karenanyaLinkedList
harus dihindari kecuali beberapa kasus yang sangat unik dan ekstrem.Secara teori, LinkedList memiliki O (1) untuk
add(E element)
Juga menambahkan elemen di tengah daftar harus sangat efisien.
Praktiknya sangat berbeda, karena LinkedList adalah struktur Data Cache Hostile . Dari kinerja POV - ada sedikit kasus di mana
LinkedList
bisa lebih baik daripada Cache-friendlyArrayList
.Berikut adalah hasil dari elemen penyisipan pengujian patokan di lokasi acak. Seperti yang Anda lihat - daftar array jika jauh lebih efisien, meskipun dalam teori setiap insert di tengah daftar akan membutuhkan "pindahkan" elemen n kemudian array (nilai yang lebih rendah lebih baik):
Bekerja pada perangkat keras generasi selanjutnya (cache yang lebih besar, lebih efisien) - hasilnya bahkan lebih konklusif:
LinkedList membutuhkan lebih banyak waktu untuk menyelesaikan pekerjaan yang sama. kode sumber sumber
Ada dua alasan utama untuk ini:
Terutama - bahwa node
LinkedList
tersebar secara acak di memori. RAM ("Random Access Memory") tidak benar-benar acak dan blok memori perlu diambil ke cache. Operasi ini membutuhkan waktu, dan ketika pengambilan itu sering terjadi - halaman memori dalam cache harus diganti setiap saat -> Cache misses -> Cache tidak efisien.ArrayList
elemen disimpan pada memori terus menerus - itulah yang dioptimalkan oleh arsitektur CPU modern.Sekunder
LinkedList
diperlukan untuk menahan pointer maju / mundur, yang berarti 3 kali pemakaian memori per nilai yang disimpan dibandingkan denganArrayList
.DynamicIntArray , btw, adalah implementasi implementasi ArrayList kustom
Int
(tipe primitif) dan bukan Objects - maka semua data benar-benar disimpan secara bersebelahan - karenanya bahkan lebih efisien.Elemen kunci yang perlu diingat adalah bahwa biaya mengambil blok memori, lebih signifikan daripada biaya mengakses sel memori tunggal. Itu sebabnya pembaca 1MB memori sekuensial hingga x400 kali lebih cepat daripada membaca jumlah data ini dari berbagai blok memori:
Sumber: Nomor Latensi yang Harus Diketahui Setiap Programmer
Agar poinnya lebih jelas, silakan periksa tolok ukur penambahan elemen di awal daftar. Ini adalah kasus penggunaan di mana, dalam teori,
LinkedList
harus benar-benar bersinar, danArrayList
harus menyajikan hasil kasus yang buruk atau bahkan lebih buruk:Catatan: ini adalah tolok ukur dari C ++ Std lib, tetapi pengalaman saya sebelumnya menunjukkan hasil C ++ dan Java sangat mirip. Kode sumber
Menyalin sebagian besar memori adalah operasi yang dioptimalkan oleh CPU modern - mengubah teori dan benar-benar membuat, sekali lagi,
ArrayList
/Vector
jauh lebih efisienKredit: Semua tolok ukur yang diposting di sini dibuat oleh Kjell Hedström . Bahkan lebih banyak data dapat ditemukan di blog-nya
sumber
Jika kode Anda memiliki
add(0)
danremove(0)
, gunakan aLinkedList
dan itu lebih cantikaddFirst()
danremoveFirst()
metode. Kalau tidak, gunakanArrayList
.Dan tentu saja, jambu 's ImmutableList adalah teman terbaik Anda.
sumber
Saya tahu ini adalah postingan lama, tapi jujur saya tidak percaya tidak ada yang menyebutkan
LinkedList
implementasinyaDeque
. Lihat saja metode diDeque
(danQueue
); jika Anda ingin perbandingan yang adil, coba jalankanLinkedList
melawanArrayDeque
dan lakukan perbandingan fitur-untuk-fitur.sumber
Berikut adalah notasi Big-O di keduanya
ArrayList
danLinkedList
dan jugaCopyOnWrite-ArrayList
:ArrayList
LinkedList
CopyOnWrite-ArrayList
Berdasarkan ini, Anda harus memutuskan apa yang harus dipilih. :)
sumber
LinkedList.add()
, meskipun sebagian besar jawaban di sini mengatakan demikian.Mari kita bandingkan parameter LinkedList dan ArrayList wrt di bawah ini:
1. Implementasi
2. Kinerja
dapatkan (indeks int) atau operasi pencarian
Alasan di balik ArrayList menjadi lebih cepat daripada LinkedList adalah bahwa ArrayList menggunakan sistem berbasis indeks untuk elemen-elemennya karena secara internal menggunakan struktur data array, di sisi lain,
LinkedList tidak menyediakan akses berbasis indeks untuk elemen-elemennya karena iterasi baik dari awal atau akhir (mana yang lebih dekat) untuk mengambil node pada indeks elemen yang ditentukan.
masukkan () atau tambahkan operasi (Objek)
hapus operasi (int)
Hapus operasi di LinkedList umumnya sama dengan ArrayList yaitu O (n).
3. Reverse Iterator
4. Kapasitas awal
5. Memory Overhead
Sumber
sumber
Saya biasanya menggunakan yang satu berdasarkan yang lain berdasarkan kompleksitas waktu dari operasi yang saya lakukan pada Daftar itu.
sumber
Selain argumen bagus lainnya di atas, Anda harus memperhatikan antarmuka
ArrayList
implementRandomAccess
, sementaraLinkedList
implementQueue
.Jadi, entah bagaimana mereka mengatasi masalah yang sedikit berbeda, dengan perbedaan efisiensi dan perilaku (lihat daftar metode mereka).
sumber
Tergantung pada operasi apa yang akan Anda lakukan lebih banyak pada Daftar.
ArrayList
lebih cepat untuk mengakses nilai yang diindeks. Jauh lebih buruk saat memasukkan atau menghapus objek.Untuk mengetahui lebih lanjut, baca artikel apa saja yang membahas perbedaan antara array dan daftar tertaut.
sumber
Daftar array pada dasarnya adalah array dengan metode untuk menambahkan item dll (dan Anda harus menggunakan daftar generik sebagai gantinya). Ini adalah koleksi item yang dapat diakses melalui pengindeks (misalnya [0]). Ini menyiratkan perkembangan dari satu item ke item berikutnya.
Daftar tertaut menentukan perkembangan dari satu item ke item berikutnya (Item a -> item b). Anda bisa mendapatkan efek yang sama dengan daftar array, tetapi daftar tertaut benar-benar mengatakan item apa yang seharusnya mengikuti yang sebelumnya.
sumber
Lihat Tutorial Java - Daftar Implementasi .
sumber
Fitur penting dari daftar tertaut (yang saya tidak baca di jawaban lain) adalah gabungan dari dua daftar. Dengan array, ini O (n) (+ overhead dari beberapa realokasi) dengan daftar tertaut, ini hanya O (1) atau O (2) ;-)
Penting : Untuk Java
LinkedList
ini tidak benar! Lihat Apakah ada metode concat cepat untuk daftar tertaut di Jawa?sumber
next
dari satu daftar ke simpul pertama di daftar kedua. Satu-satunya cara adalah menggunakanaddAll()
yang menambahkan elemen secara berurutan, meskipun lebih baik daripada mengulang-ulang dan memanggiladd()
setiap elemen. Untuk melakukan ini dengan cepat dalam O (1) Anda akan memerlukan kelas pengomposit (seperti org.apache.commons.collections.collection.CompositeCollection) tetapi kemudian ini akan bekerja untuk semua jenis Daftar / Koleksi.ArrayList dan LinkedList memiliki pro dan kontra sendiri.
ArrayList menggunakan alamat memori yang berdekatan dibandingkan dengan LinkedList yang menggunakan pointer ke node berikutnya. Jadi ketika Anda ingin mencari elemen dalam ArrayList lebih cepat daripada melakukan iterasi dengan LinkedList.
Di sisi lain, penyisipan dan penghapusan dalam LinkedList jauh lebih mudah karena Anda hanya perlu mengubah pointer sedangkan ArrayList menyiratkan penggunaan operasi shift untuk penyisipan atau penghapusan.
Jika Anda memiliki operasi pengambilan yang sering di aplikasi Anda gunakan ArrayList. Jika Anda sering memasukkan dan menghapus, gunakan LinkedList.
sumber
Saya telah membaca tanggapannya, tetapi ada satu skenario di mana saya selalu menggunakan LinkedList daripada ArrayList yang ingin saya bagikan untuk mendengar pendapat:
Setiap kali saya memiliki metode yang mengembalikan daftar data yang diperoleh dari DB, saya selalu menggunakan LinkedList.
Alasan saya adalah bahwa karena tidak mungkin untuk mengetahui dengan pasti berapa banyak hasil yang saya dapatkan, tidak akan ada memori yang terbuang (seperti dalam ArrayList dengan perbedaan antara kapasitas dan jumlah elemen aktual), dan tidak akan ada waktu yang terbuang untuk mencoba menduplikasi kapasitas.
Sejauh ArrayList, saya setuju bahwa setidaknya Anda harus selalu menggunakan konstruktor dengan kapasitas awal, untuk meminimalkan duplikasi array sebanyak mungkin.
sumber
ArrayList
danLinkedList
keduanya mengimplementasikanList interface
serta metode dan hasilnya hampir identik. Namun ada beberapa perbedaan di antara mereka yang membuat satu lebih baik daripada yang lain tergantung pada kebutuhan.ArrayList Vs LinkedList
1)
Search:
ArrayList
operasi pencarian cukup cepat dibandingkan denganLinkedList
operasi pencarian.get(int index)
diArrayList
berikan kinerjaO(1)
saatLinkedList
kinerjaO(n)
.Reason:
ArrayList
memelihara sistem berbasis indeks untuk elemen-elemennya karena menggunakan struktur data array secara implisit yang membuatnya lebih cepat untuk mencari elemen dalam daftar. Di sisi lainLinkedList
mengimplementasikan daftar tertaut ganda yang memerlukan traversal melalui semua elemen untuk mencari elemen.2)
Deletion:
LinkedList
operasi penghapusan memberikanO(1)
kinerja sementaraArrayList
memberikan kinerja variabel:O(n)
dalam kasus terburuk (saat menghapus elemen pertama) danO(1)
dalam kasus terbaik (Saat menghapus elemen terakhir).Alasan: Setiap elemen LinkedList memiliki dua pointer (alamat) yang menunjuk ke kedua elemen tetangga dalam daftar. Oleh karena itu penghapusan hanya memerlukan perubahan lokasi pointer di dua node tetangga (elemen) dari node yang akan dihapus. Sementara di ArrayList semua elemen harus digeser untuk mengisi ruang yang dibuat oleh elemen yang dihapus.
3)
Inserts Performance:
LinkedList
metode add memberikanO(1)
kinerja sementaraArrayList
memberiO(n)
dalam kasus terburuk. Alasannya sama seperti yang dijelaskan untuk dihapus.4)
Memory Overhead:
ArrayList
memelihara indeks dan data elemen sementaraLinkedList
mempertahankan data elemen dan dua pointer untuk node tetanggaAda beberapa kesamaan antara kelas-kelas ini yaitu sebagai berikut:
iterator
danlistIterator
dikembalikan oleh kelas-kelas inifail-fast
(jika daftar dimodifikasi secara struktural kapan saja setelah iterator dibuat, dengan cara apa pun kecuali melalui metodeiterator’s
hapus atau tambahkan sendiri, iterator akanthrow
aConcurrentModificationException
).Kapan menggunakan LinkedList dan kapan menggunakan ArrayList?
(O(1))
diLinkedList
dibandingkan denganArrayList(O(n))
.get method
Operasi pencarian ( ) cepatArraylist (O(1))
tetapi tidak diLinkedList (O(n))
sumber
Pengoperasian get (i) di ArrayList lebih cepat daripada LinkedList, karena:
ArrayList: Implementasi array-resizable dari antarmuka Daftar
LinkedList: Implementasi daftar yang dikaitkan secara tak terduga dari antarmuka Daftar dan Deque
Operasi yang mengindeks ke dalam daftar akan melintasi daftar dari awal atau akhir, mana yang lebih dekat ke indeks yang ditentukan.
sumber
1) Struktur Data yang Mendasari
Perbedaan pertama antara ArrayList dan LinkedList datang dengan fakta bahwa ArrayList didukung oleh Array sementara LinkedList didukung oleh LinkedList. Ini akan menyebabkan perbedaan lebih lanjut dalam kinerja.
2) LinkedList mengimplementasikan Deque
Perbedaan lain antara ArrayList dan LinkedList adalah bahwa selain dari antarmuka Daftar, LinkedList juga mengimplementasikan antarmuka Deque, yang menyediakan operasi masuk pertama keluar pertama untuk add () dan polling () dan beberapa fungsi Deque lainnya. 3) Menambahkan elemen di ArrayList Menambahkan elemen di ArrayList adalah operasi O (1) jika tidak memicu ukuran ulang Array, dalam hal ini menjadi O (log (n)), Di sisi lain, menambahkan elemen dalam LinkedList adalah operasi O (1), karena tidak memerlukan navigasi apa pun.
4) Menghapus elemen dari suatu posisi
Untuk menghapus suatu elemen dari indeks tertentu misalnya dengan memanggil remove (indeks), ArrayList melakukan operasi penyalinan yang membuatnya dekat dengan O (n) sementara LinkedList perlu melintasi ke titik itu yang juga membuatnya O (n / 2) , karena dapat melintasi dari kedua arah berdasarkan kedekatan.
5) Iterasi melalui ArrayList atau LinkedList
Iterasi adalah operasi O (n) untuk LinkedList dan ArrayList di mana n adalah sejumlah elemen.
6) Mengambil elemen dari suatu posisi
Operasi get (index) adalah O (1) di ArrayList sementara O (n / 2) di LinkedList, karena perlu dilalui hingga entri itu. Padahal, dalam notasi O Besar O (n / 2) hanyalah O (n) karena kita mengabaikan konstanta di sana.
7) Memori
LinkedList menggunakan objek pembungkus, Entri, yang merupakan kelas bersarang statis untuk menyimpan data dan dua node berikutnya dan sebelumnya, sementara ArrayList hanya menyimpan data dalam Array.
Jadi persyaratan memori tampaknya kurang dalam kasus ArrayList daripada LinkedList kecuali untuk kasus di mana Array melakukan operasi ukuran ulang ketika menyalin konten dari satu Array ke Array yang lain.
Jika Array cukup besar mungkin memerlukan banyak memori pada saat itu dan memicu pengumpulan Sampah, yang dapat memperlambat waktu respons.
Dari semua perbedaan di atas antara ArrayList vs LinkedList, Tampaknya ArrayList adalah pilihan yang lebih baik daripada LinkedList dalam hampir semua kasus, kecuali ketika Anda sering melakukan operasi add () daripada menghapus (), atau mendapatkan ().
Lebih mudah untuk mengubah daftar yang ditautkan daripada ArrayList, terutama jika Anda menambahkan atau menghapus elemen dari awal atau akhir karena daftar tertaut secara internal menyimpan referensi dari posisi-posisi itu dan mereka dapat diakses dalam waktu O (1).
Dengan kata lain, Anda tidak perlu menelusuri daftar tertaut untuk mencapai posisi di mana Anda ingin menambahkan elemen, dalam hal itu, penambahan menjadi operasi O (n). Misalnya, memasukkan atau menghapus elemen di tengah daftar tertaut.
Menurut pendapat saya, gunakan ArrayList melalui LinkedList untuk sebagian besar tujuan praktis di Jawa.
sumber
Salah satu tes yang saya lihat di sini hanya melakukan tes satu kali. Tetapi yang saya perhatikan adalah bahwa Anda perlu menjalankan tes ini berkali-kali dan akhirnya waktu mereka akan bertemu. Pada dasarnya JVM perlu pemanasan. Untuk kasus penggunaan khusus saya, saya perlu menambah / menghapus item ke daftar yang tumbuh sekitar 500 item. Dalam tes saya
LinkedList
keluar lebih cepat, denganLinkedList
masuk sekitar 50.000 NS danArrayList
datang di sekitar 90.000 NS ... memberi atau menerima. Lihat kode di bawah ini.sumber
Baik remove () dan insert () memiliki efisiensi runtime O (n) untuk ArrayLists dan LinkedLists. Namun, alasan di balik waktu pemrosesan linier berasal dari dua alasan yang sangat berbeda:
Dalam ArrayList, Anda mendapatkan elemen di O (1), tetapi sebenarnya menghapus atau menyisipkan sesuatu membuatnya menjadi O (n) karena semua elemen berikut perlu diubah.
Dalam LinkedList, dibutuhkan O (n) untuk benar-benar mencapai elemen yang diinginkan, karena kita harus mulai dari awal hingga mencapai indeks yang diinginkan. Sebenarnya menghapus atau menyisipkan adalah konstan, karena kita hanya perlu mengubah 1 referensi untuk remove () dan 2 referensi untuk insert ().
Yang mana dari keduanya yang lebih cepat untuk dimasukkan dan dilepaskan tergantung di mana itu terjadi. Jika kita lebih dekat ke awal, LinkedList akan lebih cepat, karena kita harus melalui beberapa elemen. Jika kita mendekati akhir, ArrayList akan lebih cepat, karena kita sampai di sana dalam waktu yang konstan dan hanya perlu mengubah beberapa elemen yang tersisa yang mengikutinya. Ketika dilakukan tepat di tengah, LinkedList akan lebih cepat karena melalui elemen n lebih cepat daripada memindahkan nilai n.
Bonus: Meskipun tidak ada cara untuk membuat kedua metode ini O (1) untuk ArrayList, sebenarnya ada cara untuk melakukan ini di LinkedLists. Katakanlah kita ingin melalui seluruh Daftar menghapus dan memasukkan elemen dalam perjalanan kita. Biasanya, Anda akan mulai dari awal untuk setiap elemen menggunakan LinkedList, kami juga bisa "menyimpan" elemen saat ini yang sedang kami kerjakan dengan Iterator. Dengan bantuan Iterator, kami mendapatkan efisiensi O (1) untuk menghapus () dan menyisipkan () ketika bekerja di LinkedList. Menjadikannya satu-satunya manfaat kinerja, saya mengetahui di mana LinkedList selalu lebih baik daripada ArrayList.
sumber
ArrayList memperluas AbstractList dan mengimplementasikan Daftar Antarmuka. ArrayList adalah array dinamis.
Dapat dikatakan bahwa itu pada dasarnya dibuat untuk mengatasi kelemahan array
Kelas LinkedList memperluas AbstractSequentialList dan mengimplementasikan antarmuka Daftar, Deque, dan Antrian.
Kinerja
arraylist.get()
adalah O (1) sedangkanlinkedlist.get()
O (n)arraylist.add()
adalah O (1) danlinkedlist.add()
0 (1)arraylist.contains()
adalah O (n) danlinkedlist.contains()
O (n)arraylist.next()
adalah O (1) danlinkedlist.next()
O (1)arraylist.remove()
adalah O (n) sedangkanlinkedlist.remove()
O (1)Dalam arraylist
iterator.remove()
adalah O (n)sedangkan In linkedlist
iterator.remove()
adalah O (1)sumber