Kapan menggunakan LinkedList daripada ArrayList di Java?

3123

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 LinkedListdigunakan ArrayListdan sebaliknya?

sdellysse
sumber
4
Lihat juga: Array versus daftar terkait
Hawkeye Parker
1
Lihat saja kutipan dari penulis LinkedList stackoverflow.com/a/42529652/2032701 dan Anda akan mendapatkan pemahaman praktis tentang masalah ini.
Ruslan
Lihat posting Java LinkedList vs ArrayList , yang menjelaskan perbedaan, dan termasuk beberapa tes kinerja.
alonana

Jawaban:

3372

Ringkasan ArrayList dengan ArrayDequelebih disukai dalam banyak kasus penggunaan daripada LinkedList. Jika Anda tidak yakin - mulailah dengan ArrayList.


LinkedListdan ArrayListdua implementasi berbeda dari antarmuka Daftar. LinkedListmengimplementasikannya dengan daftar yang ditautkan dua kali lipat. ArrayListmengimplementasikannya 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) ketika index = 0atau index = list.size() - 1(dalam hal ini, Anda juga dapat menggunakan getFirst()dan getLast()). Salah satu manfaat utama LinkedList<E>
  • add(int index, E element)adalah O (n) (dengan n / 4 langkah rata-rata), tetapi O (1) ketika index = 0atau index = list.size() - 1(dalam hal ini, Anda juga dapat menggunakan addFirst()dan addLast()/ add()). Salah satu manfaat utama LinkedList<E>
  • remove(int index)adalah O (n) (dengan n / 4 langkah rata-rata), tetapi O (1) ketika index = 0atau index = list.size() - 1(dalam hal ini, Anda juga dapat menggunakan removeFirst()dan removeLast()). Salah satu manfaat utama LinkedList<E>
  • Iterator.remove()adalah O (1) . Salah satu manfaat utama LinkedList<E>
  • ListIterator.add(E element)adalah O (1) . Salah satu manfaat utama LinkedList<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 utama ArrayList<E>
  • add(E element)adalah O (1) diamortisasi, tetapi O (n) terburuk karena array harus diubah ukurannya dan disalin
  • add(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) untuk index = 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 ke ArrayListis 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 ArrayListcepat 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 LinkedListtimbul 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 dengan LinkedListcara mengikuti tautan di O (n) ( langkah n / 2 ) untuk kasus terburuk, sedangkan dalam ArrayListposisi yang diinginkan dapat dihitung secara matematis dan diakses di O (1) .

Manfaat lain dari menggunakan LinkedListmuncul ketika Anda menambah atau menghapus dari kepala daftar, karena operasi tersebut adalah O (1) , sedangkan mereka adalah O (n) untuk ArrayList. Perhatikan bahwa ArrayDequemungkin merupakan alternatif yang baik LinkedListuntuk menambah dan menghapus dari kepala, tetapi itu bukan List.

Juga, jika Anda memiliki daftar besar, perlu diingat bahwa penggunaan memori juga berbeda. Setiap elemen dari LinkedListmemiliki lebih banyak overhead karena pointer ke elemen berikutnya dan sebelumnya juga disimpan. ArrayListstidak memiliki overhead ini. Namun, ArrayListsgunakan memori sebanyak yang dialokasikan untuk kapasitas, terlepas dari apakah elemen telah ditambahkan.

Kapasitas awal default suatu ArrayListcukup 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, buat ArrayListdengan kapasitas awal yang lebih tinggi.

Jonathan Tran
sumber
183
Lupa menyebutkan biaya penyisipan. Dalam LinkedList, setelah Anda memiliki posisi yang benar, biaya penyisipan O (1), sedangkan dalam ArrayList naik ke O (n) - semua elemen yang melewati titik penyisipan harus dipindahkan.
David Rodríguez - dribeas
26
Mengenai penggunaan Vector: Benar-benar tidak perlu kembali ke Vector. Cara untuk melakukan ini adalah dengan implementasi Daftar pilihan Anda dan panggilan ke daftar disinkronkan untuk memberikannya pembungkus yang disinkronkan. Lihat: java.sun.com/docs/books/tutorial/collections/implementations/…
Ryan Cox
69
Tidak, untuk LinkedList, get masih O (n) bahkan jika Anda tahu posisi itu, karena untuk sampai ke posisi itu, implementasi yang mendasarinya harus berjalan pada pointer "selanjutnya" dari daftar tertaut untuk mendapatkan nilai posisi itu. Tidak ada yang namanya akses acak. Untuk posisi 2, berjalan pointer mungkin murah, tetapi untuk posisi 1 juta, tidak begitu murah. Intinya adalah, proporsional dengan posisi, yang berarti O (n).
Jonathan Tran
53
@Kevin Mungkin saja ingatannya "berdekatan". Perangkat keras akan melakukan cache blok memori yang berdekatan (RAM dinamis) ke dalam RAM statis yang lebih cepat di cache L1 atau L2. Secara teori dan sebagian besar waktu secara praktis, memori dapat diperlakukan sebagai akses acak. Namun pada kenyataannya, membaca memori secara berurutan akan sedikit lebih cepat daripada dalam urutan acak. Untuk loop kinerja-kritis, ini bisa jadi masalah. Mereka menyebutnya "lokalitas spasial" atau lokalitas referensi .
Jonathan Tran
92
Tidak ada yang namanya O(n/2)atau O(n/4). Notasi O besar memberitahu Anda bagaimana skala operasi dengan n lebih besar . dan suatu operasi yang membutuhkan n/2langkah - langkah berskala persis seperti operasi yang membutuhkan nlangkah - langkah, yang merupakan alasan mengapa jumlah atau faktor konstan dihilangkan. O(n/2)dan O(n/4)keduanya adil O(n). LinkedListdan ArrayListmemiliki faktor konstan yang berbeda, jadi tidak masuk akal untuk membandingkan O(n/2)satu O(n/4)dari yang lain, keduanya hanya menunjukkan operasi penskalaan linear.
Holger
630

Sejauh ini, tidak ada yang tampaknya telah membahas jejak memori dari masing-masing daftar ini selain konsensus umum bahwa a LinkedListadalah "lebih banyak" daripada ArrayListjadi 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 LinkedListsdan ArrayLists.

Catatan: Ukuran yang ditunjukkan untuk ArrayListgaris adalah untuk daftar yang dipangkas - Dalam praktiknya, kapasitas array dukungan dalam ArrayListumumnya 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.


Grafik LinkedList dan ArrayList No. dari Elemen x Bytes


Hasilnya jelas menunjukkan bahwa LinkedListjauh lebih banyak daripada ArrayList, terutama dengan jumlah elemen yang sangat tinggi. Jika ingatan merupakan faktor, jauhi LinkedLists.

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)

Numeron
sumber
2
Cukup menarik untuk melihat bahwa LinkedList membutuhkan memori sebanyak ArrayList untuk menyimpan satu elemen. Sungguh tidak intuitif! Apa yang terjadi jika Anda menjalankan contoh Anda dengan -XX: + UseCompressedOops?
jontejj
215
Masalah dengan matematika Anda adalah grafik Anda sangat melebih-lebihkan dampaknya. Anda memodelkan objek yang masing-masing hanya berisi satu 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.
Heath Hunnicutt
6
Tak satu pun dari objek ArrayList / LinkedList / Node yang hanya berisi int, jadi saya tidak mengerti apa yang Anda katakan di sana. Saya telah menulis ulang 'objek overhead' menjadi 'objek header' menjadi jelas - ada header 8 byte untuk setiap objek terlepas dari sistem, dan ya itu mencakup semua objek Node di LinkedList, yang semuanya dihitung dengan benar sejauh yang saya bisa menceritakan. Kebetulan, dalam melihatnya lagi, saya memang menemukan beberapa masalah lain dengan matematika saya di LinkedList yang sebenarnya membuat membaginya dan ArrayList lebih buruk . Saya senang terus memperbarui, jadi jangan ragu untuk menjelaskan dan menguraikan lebih lanjut.
Numeron
6
Perlu dicatat bahwa CompressedOopsdefault sekarang dalam semua JDKs baru-baru ini (7, 8 dan update dari 6 selama beberapa tahun), sehingga 64-bit tidak akan membuat perbedaan dalam ArrayListatau LinkedListukuran, kecuali Anda secara eksplisit dimatikan oops dikompresi untuk beberapa alasan.
BeeOnRope
1
@jontejj peningkatan kapasitas default adalah 50%, jadi ketika Anda mengisi ArrayListtanpa menentukan kapasitas awal, itu masih akan menggunakan memori yang jauh lebih sedikit daripada a LinkedList.
Holger
244

ArrayListadalah apa yang kamu inginkan. LinkedListhampir selalu merupakan bug (kinerja).

Kenapa LinkedListmenyebalkan:

  • Ini menggunakan banyak objek memori kecil, dan karenanya berdampak pada kinerja di seluruh proses.
  • Banyak objek kecil buruk untuk cache-lokalitas.
  • Setiap operasi yang diindeks memerlukan traversal, yaitu memiliki kinerja O (n). Ini tidak jelas dalam kode sumber, yang mengarah ke algoritma O (n) lebih lambat daripada jika ArrayListdigunakan.
  • Mendapatkan kinerja yang baik itu sulit.
  • Bahkan ketika kinerja big-O sama dengan ArrayList, itu mungkin akan secara signifikan lebih lambat.
  • Sangat menggelikan untuk melihat LinkedListsumbernya karena itu mungkin pilihan yang salah.
Tom Hawtin - tackline
sumber
237
Maaf. menandai Anda. LinkedList tidak payah. Ada situasi di mana LinkedList adalah kelas yang benar untuk digunakan. Saya setuju bahwa tidak banyak situasi di mana lebih baik daripada daftar array, tetapi mereka memang ada. Mendidik orang yang melakukan hal-hal konyol!
David Turner
40
Maaf melihat Anda mendapat banyak suara untuk ini. Memang ada sedikit alasan untuk menggunakan LinkedList Java. Selain kinerja buruk itu juga menggunakan banyak memori lebih dari kelas Daftar beton lainnya (setiap node memiliki dua pointer tambahan dan setiap node adalah objek pembungkus terpisah dengan byte overhead tambahan yang menyertainya).
Kevin Brock
42
Ini adalah salah satu jawaban paling berguna di sini. Ini memalukan begitu banyak programmer gagal untuk memahami (a) perbedaan antara tipe data abstrak dan implementasi konkret, dan (b) pentingnya dunia nyata faktor konstan dan overhead memori dalam menentukan kinerja.
Porculus
50
-1: Ini adalah tampilan yang agak berkedip. Ya, memang benar bahwa ArrayList adalah alat yang sangat serbaguna. Namun, ia memiliki keterbatasan. Ada beberapa kasus di mana ini akan menyebabkan Anda bermasalah, dan Anda harus menggunakan LinkedList. Tentu saja, ini adalah solusi yang sangat terspesialisasi, dan, seperti alat khusus apa pun, dalam kebanyakan kasus itu dikalahkan oleh yang serbaguna. Tetapi itu tidak berarti bahwa itu "menyebalkan" atau sesuatu seperti itu, Anda hanya perlu tahu kapan menggunakannya.
Malcolm
27
@ DavidTurner: Mereka memang ada, tapi saya pikir maksud Tom adalah jika Anda harus bertanya, Anda mungkin menginginkan ArrayList.
user541686
139

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.

lamont
sumber
8
Tidakkah solusi lain akan mengelola ukuran daftar secara terprogram dengan menggunakan metode ArrayList acceptCapacity ()? Pertanyaan saya adalah mengapa begitu banyak hal disimpan dalam banyak struktur data yang rapuh padahal mungkin lebih baik disimpan dalam mekanisme caching atau db? Suatu hari saya melakukan wawancara di mana mereka bersumpah tentang kejahatan ArrayList, tetapi saya datang ke sini dan saya menemukan bahwa analisis kompleksitas lebih baik! TITIK BESAR UNTUK PEMBAHASAN, PIKIRAN. TERIMA KASIH!
ingyhere
22
setelah Anda mendapatkan aplikasi java dengan tumpukan 10GB, Anda dapat mengunci aplikasi selama 25 detik selama GC penuh yang menyebabkan batas waktu. Sebenarnya dengan LinkedList Anda membunuh pengumpul sampah selama GC penuh, ia harus mengulangi LinkedList yang terlalu besar dengan cache yang hilang. setiap node.
bestsss
5
Itu ... solusi yang mengerikan. Anda pada dasarnya bergantung pada pembersihan GC untuk Anda, yang sangat mahal, ketika Anda hanya dapat memanggil sureCapacity () pada daftar array sebagai gantinya ...
Philip Devine
5
@ Andreas: A LinkedList selalu mengalokasikan memori lima kali lipat dari array referensi biasa, jadi ArrayListsementara 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, yang LinkedListmeledak jauh lebih awal ...
Holger
5
@Andreas Masalah lainnya adalah bagaimana memori dialokasikan. LinkedListhanya perlu sepotong kecil memori bebas untuk mengalokasikan untuk elemen selanjutnya. ArrayListakan 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.
Piotr Kusmierczyk
128
Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algoritma: Notasi Besar-Oh

ArrayLists baik untuk write-once-read-many atau appenders, tetapi buruk untuk add / remove dari depan atau tengah.

Michael Munsey
sumber
42
Anda tidak dapat membandingkan nilai O besar secara langsung tanpa memikirkan faktor konstan. Untuk daftar kecil (dan sebagian besar daftar kecil), ArrayList's O (N) lebih cepat daripada LinkedList's O (1).
Porculus
4
Saya tidak peduli tentang kinerja daftar kecil, dan komputer saya tidak kecuali itu digunakan dalam satu lingkaran entah bagaimana.
Maarten Bodewes
45
LinkedList tidak bisa benar-benar memasukkan di tengah O(1). Itu harus dijalankan melalui setengah daftar untuk menemukan titik penyisipan.
Thomas Ahle
8
LinkedList: masukkan di tengah O (1) - SALAH! Saya menemukan bahwa bahkan penyisipan ke posisi 1/10 dari ukuran LinkedList lebih lambat daripada memasukkan elemen ke posisi 1/10 dari ArrayList. Dan lebih buruk lagi: akhir koleksi. menyisipkan ke posisi terakhir (bukan yang terakhir) dari ArrayList lebih cepat daripada ke posisi terakhir (bukan yang terakhir) dari LinkedList
kachanov
14
@ kachanov Menyisipkan dalam LinkedList adalah O(1) jika Anda memiliki iterator ke posisi memasukkan , yaitu ListIterator.addseharusnya O(1)untuk a LinkedList.
Memiliki QUIT - Anony-Mousse
107

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)

Daniel Martin
sumber
39
Dari Java 6 Anda bisa menggunakan ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html
Thomas Ahle
1
ArrayDequelebih lambat daripada LinkedListkecuali semua operasi pada ujung yang sama. Tidak apa-apa bila digunakan sebagai tumpukan tetapi tidak membuat antrian yang baik.
Daftar Jeremy
2
Tidak Benar - setidaknya untuk implementasi Oracle di jdk1.7.0_60 dan dalam pengujian berikut. Saya membuat tes di mana saya mengulang sebanyak 10 juta kali dan saya memiliki Deque 10 juta bilangan bulat acak. Di dalam loop saya polling satu elemen dari dan menawarkan elemen konstan. Di komputer saya, LinkedList lebih dari 10 kali lebih lambat dari ArrayDeque dan menggunakan lebih sedikit memori). Alasannya adalah bahwa tidak seperti ArrayList, ArrayDeque menyimpan pointer ke kepala array sehingga tidak harus memindahkan semua elemen ketika kepala dihapus.
Henno Vermeulen
6
ArrayDequecenderung lebih cepat daripada Stacksaat digunakan sebagai tumpukan, dan lebih cepat dari LinkedListsaat digunakan sebagai antrian.
akhil_mittal
3
Perhatikan bahwa komentar akhil_mittal adalah kutipan dari ArrayDequedokumentasi.
Stuart Marks
65

Ini pertanyaan efisiensi. LinkedListcepat untuk menambah dan menghapus elemen, tetapi lambat untuk mengakses elemen tertentu. ArrayListcepat 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 .

dgtized
sumber
54

Benar atau Salah: Silakan jalankan tes secara lokal dan putuskan sendiri!

Edit / Hapus lebih cepat LinkedListdaripada ArrayList.

ArrayList, didukung oleh Array, 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.


Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

Berikut kodenya:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}
Abu
sumber
1
ArrayList tidak perlu digandakan, tepatnya. Silakan periksa sumbernya terlebih dahulu.
Danubian Sailor
Perlu dicatat bahwa contoh Anda cacat ... Anda menghapus dari string antara: 18 + [2, 12] byte ("true0false", "true500000false"), rata-rata 25 byte, yang merupakan ukuran elemen. di tengah-tengah. Diketahui bahwa ketika ukuran elemen byte meningkatkan daftar yang terhubung berkinerja lebih baik, karena ukuran daftar meningkat, sebuah array (daftar) yang berdekatan akan lebih baik. Yang paling penting, Anda melakukan .equals () pada string - yang bukan operasi yang murah. Jika Anda menggunakan bilangan bulat, saya pikir akan ada perbedaan.
Centril
2
"... lebih buruk dalam aplikasi volume besar ": Ini adalah kesalahpahaman. LinkedListmemiliki 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 elemen ArrayListadalah satu setengah kata, yang menghasilkan 6 byte, dan 8 byte dalam kasus terburuk.
Lii
1
Saya telah melakukan versi benchmark yang lebih baik di sini, dengan hasil - kinerja append-on-end untuk daftar array secara artifisial rendah untuk milik Anda, karena addAll memberikan array penyimpanan ukuran awal PERSIS, jadi insert pertama selalu memicu suatu arraycopy. Juga, ini termasuk siklus pemanasan untuk memungkinkan kompilasi JIT sebelum data dikumpulkan.
BobMcGee
4
@ BillK sejak Java 8, Anda dapat menggunakan removeIf(element -> condition)mana yang cocok, yang bisa secara signifikan lebih cepat untuk ArrayList, 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 daripada LinkedListtergantung pada skenario tertentu, seperti LinkedListO (1) dalam teori, tetapi menghapus hanya satu node memerlukan beberapa akses memori, yang dapat dengan mudah melebihi jumlah yang diperlukan untuk ArrayListsaat menghapus sejumlah besar elemen .
Holger
50

ArrayListpada dasarnya adalah sebuah array. LinkedListdiimplementasikan sebagai daftar yang ditautkan ganda.

The getcukup jelas. O (1) untuk ArrayList, karena ArrayListmemungkinkan akses acak dengan menggunakan indeks. O (n) untuk LinkedList, karena perlu mencari indeks terlebih dahulu. Catatan: ada beberapa versi adddan remove.

LinkedListlebih cepat dalam menambah dan menghapus, tetapi lebih lambat di dapatkan. Secara singkat, LinkedListsebaiknya lebih disukai jika:

  1. tidak ada sejumlah besar akses acak elemen
  2. ada sejumlah besar operasi add / remove

=== ArrayList ===

  • tambah (E e)
    • tambahkan di akhir ArrayList
    • membutuhkan biaya pengubahan ukuran memori.
    • O (n) terburuk, O (1) diamortisasi
  • tambah (indeks int, elemen E)
    • tambahkan ke posisi indeks tertentu
    • membutuhkan pengalihan & kemungkinan biaya pengubahan ukuran memori
    • Di)
  • hapus (indeks int)
    • hapus elemen yang ditentukan
    • membutuhkan pengalihan & kemungkinan biaya pengubahan ukuran memori
    • Di)
  • hapus (Objek o)
    • hapus kejadian pertama dari elemen yang ditentukan dari daftar ini
    • perlu mencari elemen terlebih dahulu, dan kemudian menggeser & kemungkinan mengubah ukuran memori
    • Di)

=== LinkedList ===

  • tambah (E e)

    • tambahkan ke akhir daftar
    • O (1)
  • tambah (indeks int, elemen E)

    • masukkan pada posisi yang ditentukan
    • perlu menemukan posisi terlebih dahulu
    • Di)
  • menghapus()
    • hapus elemen pertama dari daftar
    • O (1)
  • hapus (indeks int)
    • hapus elemen dengan indeks yang ditentukan
    • perlu menemukan elemen terlebih dahulu
    • Di)
  • hapus (Objek o)
    • menghapus kejadian pertama dari elemen yang ditentukan
    • perlu menemukan elemen terlebih dahulu
    • Di)

Berikut adalah gambar dari programcreek.com ( adddan removemerupakan tipe pertama, yaitu, tambahkan elemen di akhir daftar dan hapus elemen pada posisi yang ditentukan dalam daftar.):

masukkan deskripsi gambar di sini

Ryan
sumber
3
"LinkedList lebih cepat daripada menambah / menghapus". Salah, periksa jawaban di atas stackoverflow.com/a/7507740/638670
Nerrve
49

Joshua Bloch, penulis LinkedList:

Adakah yang benar-benar menggunakan LinkedList? Saya menulisnya, dan saya tidak pernah menggunakannya.

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.

Ruslan
sumber
34

ArrayListdiakses secara acak, sementara LinkedListsangat 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.

Dustin
sumber
15
LinkedList tidak murah untuk menambahkan elemen. Hampir selalu lebih cepat untuk menambahkan sejuta elemen ke ArrayList daripada menambahkannya ke LinkedList. Dan sebagian besar daftar dalam kode dunia nyata bahkan tidak memiliki sejuta elemen.
Porculus
10
Pada titik tertentu, Anda tahu biaya menambahkan item ke LinkedList Anda. ArrayList yang Anda tidak (secara umum). Menambahkan satu item ke ArrayList yang berisi sejuta item bisa memakan waktu yang sangat lama - ini adalah operasi O (n) plus menggandakan penyimpanan kecuali Anda tidak mengalokasikan ruang. Menambahkan item ke LinkedList adalah O (1). Pernyataan terakhir saya berdiri.
Dustin
4
Menambahkan satu item ke ArrayList adalah O (1) tidak peduli itu 1 juta atau 1 miliar. Menambahkan item ke LinkedList juga O (1). "Menambahkan" berarti MENAMBAHKAN AKHIR.
kachanov
Anda pasti sudah membaca implementasinya secara berbeda dari saya. Dalam pengalaman saya, menyalin 1 miliar elemen array membutuhkan waktu lebih lama daripada menyalin 1 juta elemen elemen.
Dustin
6
@kachanov Anda harus salah paham tentang Dustin. Kecuali jika Anda telah mendeklarasikan array yang terdiri dari 1 miliar item, Anda pada akhirnya perlu mengubah ukuran array Anda. Dalam hal ini Anda perlu menyalin semua elemen ke dalam array yang lebih besar sehingga terkadang Anda akan mendapatkan O (N) namun dengan daftar yang ditautkan Anda akan selalu dapatkan O (1)
Stan R.
29

TL; DR karena arsitektur komputer modern, ArrayListakan jauh lebih efisien untuk hampir semua kasus penggunaan yang mungkin - dan karenanya LinkedListharus 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 LinkedListbisa lebih baik daripada Cache-friendly ArrayList .

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):

masukkan deskripsi gambar di sini

Bekerja pada perangkat keras generasi selanjutnya (cache yang lebih besar, lebih efisien) - hasilnya bahkan lebih konklusif:

masukkan deskripsi gambar di sini

LinkedList membutuhkan lebih banyak waktu untuk menyelesaikan pekerjaan yang sama. kode sumber sumber

Ada dua alasan utama untuk ini:

  1. Terutama - bahwa node LinkedListtersebar 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. ArrayListelemen disimpan pada memori terus menerus - itulah yang dioptimalkan oleh arsitektur CPU modern.

  2. Sekunder LinkedList diperlukan untuk menahan pointer maju / mundur, yang berarti 3 kali pemakaian memori per nilai yang disimpan dibandingkan dengan ArrayList.

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:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

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, LinkedListharus benar-benar bersinar, dan ArrayListharus menyajikan hasil kasus yang buruk atau bahkan lebih buruk:

masukkan deskripsi gambar di sini

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/ Vectorjauh lebih efisien


Kredit: Semua tolok ukur yang diposting di sini dibuat oleh Kjell Hedström . Bahkan lebih banyak data dapat ditemukan di blog-nya

Lior Bar-On
sumber
Saya tidak akan memanggil antrian yang unik atau ekstrem! Antrian fifo lebih mudah diimplementasikan pada LinkedList daripada ArrayList. Sebenarnya ini adalah mimpi buruk di ArrayList karena Anda harus melacak awal Anda sendiri, berhenti dan melakukan realokasi Anda sendiri, Anda mungkin juga menggunakan array, tetapi Daftar Linked IS fifo. Saya tidak yakin tentang implementasi Java, tetapi LinkedList dapat melakukan O (1) untuk operasi antrian dan dequeue (Membutuhkan pointer khusus ke elemen ekor untuk menghapus, yang saya asumsikan java memiliki tetapi saya belum memeriksa ulang .)
Bill K
24

Jika kode Anda memiliki add(0)dan remove(0), gunakan a LinkedListdan itu lebih cantik addFirst()dan removeFirst()metode. Kalau tidak, gunakanArrayList .

Dan tentu saja, jambu 's ImmutableList adalah teman terbaik Anda.

Jesse Wilson
sumber
3
Untuk daftar kecil, ArrayList.add (0) masih akan selalu lebih cepat daripada LinkedList.addFirst ().
Porculus
1
@Porculus Saya selalu mendengar argumen ini bahwa untuk daftar kecil ArrayList.add (0) akan lebih cepat, sekecil ini, seberapa kecil? 10 elemen, 10 juta,?
garg10mungkin
1
@ garg10mungkin kecil kurang dari 10.
Jesse Wilson
@Porculus small berarti kurang dari kapasitas maks array internal yang mendasari ArrayList.
Janac Meena
21

Saya tahu ini adalah postingan lama, tapi jujur ​​saya tidak percaya tidak ada yang menyebutkan LinkedListimplementasinya Deque. Lihat saja metode di Deque(dan Queue); jika Anda ingin perbandingan yang adil, coba jalankan LinkedListmelawan ArrayDequedan lakukan perbandingan fitur-untuk-fitur.

Ajax
sumber
18

Berikut adalah notasi Big-O di keduanya ArrayListdan LinkedListdan juga CopyOnWrite-ArrayList:

ArrayList

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Berdasarkan ini, Anda harus memutuskan apa yang harus dipilih. :)

Rajith Delantha
sumber
9
>>>> ArrayList add -> O (1) <- not tru. Dalam beberapa kasus, ArrayList harus tumbuh untuk menambahkan satu elemen lagi
kachanov
1
Hapus LinkedList bukan O (1), perlu mencari elemen yang akan dihapus, oleh karena itu kasus terburuk O (n) dan rata-rata O (n / 2)
garg10may
Tidak juga LinkedList.add(), meskipun sebagian besar jawaban di sini mengatakan demikian.
Marquis of Lorne
18

Mari kita bandingkan parameter LinkedList dan ArrayList wrt di bawah ini:

1. Implementasi

ArrayList adalah implementasi array resizable dari antarmuka daftar, sementara

LinkedList adalah implementasi daftar yang tertaut ganda dari antarmuka daftar.


2. Kinerja

  • dapatkan (indeks int) atau operasi pencarian

    Operasi get ArrayList (int index) berjalan dalam waktu konstan yaitu O (1) sementara

    Waktu menjalankan operasi LinkedList dapatkan (int indeks) adalah O (n).

    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)

    Sisipan dalam LinkedList umumnya lebih cepat dibandingkan dengan ArrayList. Dalam LinkedList, penambahan atau penyisipan adalah operasi O (1).

    Sementara di ArrayList , jika array adalah kasus terburuk penuh yaitu, ada biaya tambahan mengubah ukuran array dan menyalin elemen ke array baru, yang membuat runtime operasi add di ArrayList O (n), kalau tidak itu adalah O (1) .

  • hapus operasi (int)

    Hapus operasi di LinkedList umumnya sama dengan ArrayList yaitu O (n).

    Di LinkedList , ada dua metode penghapusan yang kelebihan beban. satu adalah remove () tanpa parameter apa pun yang menghilangkan kepala daftar dan berjalan dalam waktu konstan O (1). Metode penghapusan kelebihan lainnya di LinkedList adalah remove (int) atau remove (Object) yang menghapus Object atau int yang dilewatkan sebagai parameter. Metode ini melintasi LinkedList sampai menemukan Obyek dan membatalkan tautannya dari daftar asli. Karenanya runtime metode ini adalah O (n).

    Sementara di ArrayList, menghapus (int) metode melibatkan menyalin elemen dari array lama ke array baru yang diperbarui, maka runtime-nya adalah O (n).


3. Reverse Iterator

LinkedList dapat di-iterasikan dalam arah terbalik menggunakan descendingIterator () sementara

tidak ada descendingIterator () di ArrayList , jadi kita perlu menulis kode kita sendiri untuk beralih ke ArrayList dalam arah sebaliknya.


4. Kapasitas awal

Jika konstruktor tidak kelebihan beban, maka ArrayList membuat daftar kosong kapasitas awal 10, sementara

LinkedList hanya membuat daftar kosong tanpa kapasitas awal.


5. Memory Overhead

Memori overhead dalam LinkedList lebih dibandingkan dengan ArrayList karena sebuah simpul dalam LinkedList perlu mempertahankan alamat dari node berikutnya dan sebelumnya. Sementara

Di ArrayList, setiap indeks hanya menampung objek (data) yang sebenarnya.


Sumber

Abhijeet Ashok Muneshwar
sumber
18

Saya biasanya menggunakan yang satu berdasarkan yang lain berdasarkan kompleksitas waktu dari operasi yang saya lakukan pada Daftar itu.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|
Gayan Weerakutti
sumber
ArrayDeque menyeimbangkan hal-hal sedikit lebih ke arah array karena menyisipkan / menghapus depan / belakang semuanya O (1) satu-satunya hal yang masih menangkan Daftar Tertaut adalah menambah / menghapus sambil melintasi (operasi Iterator).
Bill K
14

Selain argumen bagus lainnya di atas, Anda harus memperhatikan antarmuka ArrayListimplement RandomAccess, sementara LinkedListimplementQueue .

Jadi, entah bagaimana mereka mengatasi masalah yang sedikit berbeda, dengan perbedaan efisiensi dan perilaku (lihat daftar metode mereka).

PhiLho
sumber
10

Tergantung pada operasi apa yang akan Anda lakukan lebih banyak pada Daftar.

ArrayListlebih 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.

Matthew Schinckel
sumber
2
Untuk mengetahui lebih lanjut jangan baca, cukup tulis kodenya. dan Anda akan menemukan bahwa implementasi ArrayList lebih cepat daripada LinkedList dalam penyisipan dan penghapusan.
kachanov
8

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.

kemiller2002
sumber
8

Lihat Tutorial Java - Daftar Implementasi .

chharvey
sumber
2
Hai @chharvey, hanya tautan yang mendapat jawaban 6 Upvotes? Harap tambahkan beberapa poin yang dapat mendukung tautan. Bagaimana jika oracle mengubah tautannya?
7

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 LinkedListini tidak benar! Lihat Apakah ada metode concat cepat untuk daftar tertaut di Jawa?

Karussell
sumber
2
Bagaimana itu? Ini mungkin benar dengan struktur data daftar tertaut tetapi bukan objek Java LinkList. Anda tidak bisa hanya menunjuk nextdari satu daftar ke simpul pertama di daftar kedua. Satu-satunya cara adalah menggunakan addAll()yang menambahkan elemen secara berurutan, meskipun lebih baik daripada mengulang-ulang dan memanggil add()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.
Kevin Brock
ya benar. Saya mengedit jawabannya. tetapi lihat jawaban ini untuk 'bagaimana' melakukannya dengan LinkedList: stackoverflow.com/questions/2494031/…
Karussell
7

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.

Nesan Mano
sumber
6

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.

gaijinco
sumber
5

ArrayListdan LinkedListkeduanya 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: ArrayListoperasi pencarian cukup cepat dibandingkan dengan LinkedListoperasi pencarian. get(int index)di ArrayListberikan kinerja O(1)saat LinkedListkinerja O(n).

Reason: ArrayListmemelihara 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: LinkedListoperasi penghapusan memberikan O(1)kinerja sementara ArrayListmemberikan kinerja variabel: O(n)dalam kasus terburuk (saat menghapus elemen pertama) dan O(1)dalam kasus terbaik (Saat menghapus elemen terakhir).

Kesimpulan: penghapusan elemen LinkedList lebih cepat dibandingkan dengan ArrayList.

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: LinkedListmetode add memberikan O(1)kinerja sementara ArrayListmemberi O(n)dalam kasus terburuk. Alasannya sama seperti yang dijelaskan untuk dihapus.

4) Memory Overhead: ArrayListmemelihara indeks dan data elemen sementara LinkedListmempertahankan data elemen dan dua pointer untuk node tetangga

karenanya konsumsi memori dalam LinkedList tinggi.

Ada beberapa kesamaan antara kelas-kelas ini yaitu sebagai berikut:

  • ArrayList dan LinkedList adalah implementasi dari antarmuka Daftar.
  • Keduanya mempertahankan urutan penyisipan elemen yang berarti sambil menampilkan elemen ArrayList dan LinkedList, set hasil akan memiliki urutan yang sama di mana elemen dimasukkan ke dalam Daftar.
  • Kedua kelas ini tidak disinkronkan dan dapat dibuat disinkronkan secara eksplisit dengan menggunakan metode Collections.synchronizedList.
  • The iteratordan listIteratordikembalikan oleh kelas-kelas ini fail-fast(jika daftar dimodifikasi secara struktural kapan saja setelah iterator dibuat, dengan cara apa pun kecuali melalui metode iterator’shapus atau tambahkan sendiri, iterator akan throwa ConcurrentModificationException).

Kapan menggunakan LinkedList dan kapan menggunakan ArrayList?

  • Seperti dijelaskan di atas insert dan menghapus operasi memberikan kinerja yang baik (O(1))di LinkedListdibandingkan denganArrayList(O(n)) .

    Oleh karena itu jika ada persyaratan penambahan dan penghapusan yang sering dalam aplikasi maka LinkedList adalah pilihan terbaik.

  • get methodOperasi pencarian ( ) cepat Arraylist (O(1))tetapi tidak diLinkedList (O(n))

    jadi Jika ada lebih sedikit operasi tambah dan hapus dan lebih banyak persyaratan operasi pencarian, ArrayList akan menjadi taruhan terbaik Anda.

Real73
sumber
5

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.

Amitābha
sumber
5

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.

Anjali Suman
sumber
1
Saya pikir ini adalah jawaban terbaik dari seluruh kelompok di sini. Ini akurat dan informatif. Saya akan menyarankan mengubah baris terakhir - pada akhirnya tambahkan "selain dari antrian" yang merupakan struktur yang sangat penting yang benar-benar tidak masuk akal untuk daftar yang terhubung sama sekali.
Bill K
3

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 LinkedListkeluar lebih cepat, dengan LinkedListmasuk sekitar 50.000 NS dan ArrayListdatang di sekitar 90.000 NS ... memberi atau menerima. Lihat kode di bawah ini.

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}
Jose Martinez
sumber
2

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.

pietz
sumber
1

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) sedangkan linkedlist.get()O (n)
arraylist.add()adalah O (1) dan linkedlist.add()0 (1)
arraylist.contains()adalah O (n) dan linkedlist.contains()O (n)
arraylist.next()adalah O (1) dan linkedlist.next()O (1)
arraylist.remove()adalah O (n) sedangkan linkedlist.remove()O (1)
Dalam arraylist
iterator.remove()adalah O (n)
sedangkan In linkedlist
iterator.remove()adalah O (1)

Randhawa
sumber