Pertanyaan Kapan menggunakan LinkedList melalui ArrayList?


Saya selalu menjadi orang yang hanya menggunakan:

List<String> names = new ArrayList<>();

Saya menggunakan antarmuka sebagai nama jenis untuk portabilitas, sehingga ketika saya mengajukan pertanyaan seperti ini saya dapat mengerjakan ulang kode saya.

Kapan seharusnya LinkedList digunakan lebih ArrayList dan sebaliknya?


2565
2017-11-27 01:36


asal


Jawaban:


Ringkasan  ArrayList dengan ArrayDeque lebih disukai di banyak lebih banyak menggunakan-kasus daripada LinkedList. Tidak yakin - mulailah dengan ArrayList.


LinkedList dan ArrayList adalah dua implementasi berbeda dari antarmuka Daftar. LinkedList mengimplementasikannya dengan daftar terkait ganda. ArrayList mengimplementasikannya dengan array dinamis sizing ulang.

Seperti halnya daftar terhubung standar dan operasi array, berbagai metode akan memiliki runtime algoritme yang berbeda.

Untuk LinkedList<E>

  • get(int index) aku s Di) (dengan n / 4 langkah rata-rata)
  • add(E element) aku s O (1)
  • add(int index, E element) aku s Di) (dengan n / 4 langkah rata-rata), tapi O (1) kapan index = 0  <--- manfaat utama LinkedList<E>
  • remove(int index) aku s Di) (dengan n / 4 langkah rata-rata)
  • Iterator.remove() aku s O (1). <--- manfaat utama LinkedList<E>
  • ListIterator.add(E element) aku s O (1)  Ini adalah salah satu manfaat utama LinkedList<E>

Catatan: Banyak dari kebutuhan operasi n / 4 langkah rata-rata, konstan jumlah langkah dalam kasus terbaik (misalnya indeks = 0), dan n / 2 langkah-langkah dalam kasus terburuk (tengah daftar)

Untuk ArrayList<E>

  • get(int index) aku s O (1)  <--- manfaat utama ArrayList<E>
  • add(E element) aku s O (1) diamortisasi, tetapi Di) terburuk sejak array harus diubah ukurannya dan disalin
  • add(int index, E element) aku s Di) (dengan n / 2 langkah rata-rata)
  • remove(int index) aku s Di) (dengan n / 2 langkah rata-rata)
  • Iterator.remove() aku s Di) (dengan n / 2 langkah rata-rata)
  • ListIterator.add(E element) aku s Di) (dengan n / 2 langkah rata-rata)

Catatan: Banyak dari kebutuhan operasi n / 2 langkah rata-rata, konstan jumlah langkah dalam kasus terbaik (akhir daftar), n langkah-langkah dalam kasus terburuk (awal daftar)

LinkedList<E> memungkinkan penyisipan atau penghapusan secara terus menerus menggunakan iterator, tetapi hanya akses berurutan dari elemen. Dengan kata lain, Anda dapat berjalan daftar ke depan atau ke belakang, tetapi mencari posisi dalam daftar membutuhkan waktu sebanding dengan ukuran daftar. Kata Javadoc "Operasi yang indeks ke dalam daftar akan melintasi daftar dari awal atau akhir, mana yang lebih dekat", jadi metode itu Di) (n / 4 langkah) rata-rata, 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 menggeser semua elemen yang terakhir, baik untuk membuat pembukaan atau mengisi celah. Juga, jika Anda menambahkan lebih banyak elemen daripada kapasitas array yang mendasari, array baru (1,5 kali ukuran) dialokasikan, dan array lama disalin ke yang baru, sehingga menambah ArrayList aku s Di) dalam kasus terburuk tetapi konstan rata-rata.

Jadi tergantung pada operasi yang ingin Anda lakukan, Anda harus memilih implementasi yang sesuai. Iterasi atas kedua jenis Daftar hampir sama-sama murah. (Iterasi lebih dari satu ArrayList secara teknis lebih cepat, tetapi kecuali Anda melakukan sesuatu yang benar-benar peka terhadap kinerja, Anda tidak perlu khawatir tentang hal ini - keduanya sama-sama konstan.)

Manfaat utama menggunakan LinkedList muncul ketika Anda menggunakan kembali iterators yang ada untuk memasukkan dan menghapus elemen. Operasi ini kemudian dapat dilakukan di O (1) dengan mengubah daftar hanya secara lokal. Dalam daftar susunan, sisa array perlu terharu (mis. disalin). Di sisi lain, mencari di LinkedList berarti mengikuti tautan di Di) (n / 2 langkah) untuk kasus terburuk, sedangkan di ArrayList posisi yang diinginkan dapat dihitung secara matematis dan diakses di O (1).

Manfaat lain menggunakan LinkedList muncul ketika Anda menambahkan atau menghapus dari kepala daftar, karena operasi tersebut O (1), sementara mereka Di) untuk ArrayList. Perhatikan itu ArrayDeque mungkin alternatif yang baik untuk LinkedList untuk menambahkan dan menghapus dari kepala, tetapi itu bukan List.

Juga, jika Anda memiliki daftar besar, perlu diingat bahwa penggunaan memori juga berbeda. Setiap elemen dari a LinkedList memiliki lebih banyak overhead sejak pointer ke elemen berikutnya dan sebelumnya juga disimpan. ArrayLists tidak memiliki overhead ini. Namun, ArrayLists mengambil sebanyak memori yang dialokasikan untuk kapasitas, terlepas dari apakah elemen sebenarnya telah ditambahkan.

Kapasitas awal default dari sebuah ArrayList cukup kecil (10 dari Java 1.4 - 1.8). Tapi karena implementasi yang mendasari adalah sebuah array, array harus diubah ukurannya jika Anda menambahkan banyak elemen. Untuk menghindari biaya tinggi mengubah ukuran ketika Anda tahu Anda akan menambahkan banyak elemen, membangun ArrayList dengan kapasitas awal yang lebih tinggi.


2845
2017-10-06 06:46



Sejauh ini, tampaknya tidak ada yang membahas jejak memori dari masing-masing daftar ini selain konsensus umum bahwa a LinkedList adalah "lebih banyak" daripada ArrayList jadi saya melakukan beberapa angka untuk menunjukkan dengan tepat berapa banyak kedua daftar mengambil untuk referensi N nol.

Karena referensi adalah 32 atau 64 bit (bahkan ketika nol) pada sistem relatif mereka, saya telah menyertakan 4 set data untuk 32 dan 64 bit LinkedLists dan ArrayLists.

catatan: Ukuran yang ditunjukkan untuk ArrayList garis untuk daftar yang dipangkas - Dalam prakteknya, kapasitas dari backing array dalam suatu ArrayList umumnya lebih besar dari jumlah elemen saat ini.

Catatan 2:  (terima kasih BeeOnRope) Karena CompressedOops default dari pertengahan JDK6 ke atas, nilai di bawah untuk mesin 64-bit pada dasarnya akan cocok dengan rekan 32-bit mereka, kecuali tentu saja Anda secara khusus mematikannya.


Graph of LinkedList and ArrayList No. of Elements x Bytes


Hasilnya jelas menunjukkan itu LinkedList jauh lebih banyak daripada ArrayList, terutama dengan jumlah elemen yang sangat tinggi. Jika memori adalah faktor, jauhi LinkedLists.

Rumus yang saya gunakan mengikuti, beri tahu saya jika saya telah melakukan sesuatu yang salah dan saya akan memperbaikinya. 'b' dapat berupa 4 atau 8 untuk sistem 32 atau 64 bit, dan 'n' adalah jumlah elemen. Perhatikan alasan untuk mod adalah karena semua objek di java akan mengambil kelipatan dari 8 byte ruang terlepas dari apakah itu semua digunakan atau tidak.

ArrayList:

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)

534
2017-11-27 14:20



ArrayList adalah apa yang kamu inginkan. LinkedList hampir selalu bug (kinerja).

Mengapa LinkedList menyebalkan:

  • Menggunakan banyak objek memori kecil, dan karena itu berdampak pada kinerja di seluruh proses.
  • Banyak benda-benda kecil yang buruk untuk-lokalitas cache.
  • Setiap operasi yang diindeks memerlukan traversal, yaitu memiliki O (n) kinerja. 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 performa big-O sama dengan ArrayList, itu mungkin akan secara signifikan lebih lambat pula.
  • Sangat menggelikan untuk dilihat LinkedList dalam sumber karena mungkin adalah pilihan yang salah.

190
2018-01-01 20:23



Sebagai seseorang yang telah melakukan rekayasa kinerja operasional pada layanan web SOA berskala sangat besar selama sekitar satu dekade, saya lebih memilih perilaku LinkedList daripada ArrayList. Sementara throughput steady-state dari LinkedList lebih buruk dan karena itu mungkin mengarah untuk membeli lebih banyak perangkat keras - perilaku ArrayList di bawah tekanan dapat menyebabkan aplikasi di cluster memperluas array mereka di dekat sinkronisitas dan untuk ukuran array besar dapat menyebabkan kurangnya responsif dalam aplikasi dan pemadaman, saat berada di bawah tekanan, yang merupakan perilaku malapetaka.

Demikian pula, Anda bisa mendapatkan throughput yang lebih baik dalam aplikasi dari throughput pengumpul sampah standar, tetapi setelah Anda mendapatkan aplikasi java dengan tumpukan 10GB Anda dapat mengakhiri penguncian aplikasi selama 25 detik selama Full GCs yang menyebabkan timeout dan kegagalan dalam aplikasi SOA dan meniup SLA Anda jika terlalu sering terjadi. Meskipun kolektor CMS mengambil 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 kasus terburuk.


125
2018-04-08 20:33



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 Big-Oh

ArrayLists baik untuk menulis sekali baca banyak atau appender, tetapi buruk pada penambahan / penghapusan dari depan atau tengah.


111
2018-05-19 11:21



Ya, saya tahu, ini adalah pertanyaan kuno, tapi saya akan melempar dua sen saya:

LinkedList adalah hampir selalu pilihan yang salah, kinerja-bijaksana. Ada beberapa algoritme yang sangat spesifik di mana LinkedList dipanggil, tetapi mereka sangat, sangat jarang dan algoritme biasanya akan secara khusus bergantung pada kemampuan LinkedList untuk memasukkan dan menghapus elemen di tengah daftar relatif cepat, setelah Anda menavigasi ke sana. dengan ListIterator.

Ada satu kasus penggunaan umum di mana LinkedList mengungguli ArrayList: yaitu antrean. Namun, jika tujuan Anda adalah kinerja, alih-alih LinkedList Anda juga harus mempertimbangkan menggunakan ArrayBlockingQueue (jika Anda dapat menentukan batas atas pada ukuran antrian Anda sebelumnya, dan dapat mengalokasikan semua memori di depan), atau ini Implementasi CircularArrayList. (Ya, ini dari tahun 2001, jadi Anda harus membesarkannya, tetapi saya mendapat rasio kinerja yang sebanding dengan apa yang dikutip dalam artikel baru-baru ini di JVM baru-baru ini)


92
2017-11-27 01:39



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 ditambahkan ke salah satu ujung, dan terutama lambat untuk menghapus di tengah.

Array vs ArrayList vs LinkedList vs Vectorlebih mendalam, seperti halnya Daftar Tertaut.


50
2017-09-21 22:59



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

Sunting / Hapus lebih cepat masuk LinkedList dari ArrayList.

ArrayList, didukung oleh Array, yang perlu digandakan ukurannya, lebih buruk dalam aplikasi volume besar.

Di bawah ini adalah hasil tes unit untuk setiap operasi. Timing diberikan dalam Nanoseconds.


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

Begini 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);
    }
}

49
2018-04-21 00:03