Mengapa ArrayDeque lebih baik daripada LinkedList

161

Saya mencoba untuk memahami mengapa Java ArrayDeque lebih baik daripada Java LinkedList karena keduanya mengimplementasikan antarmuka Deque.

Saya jarang melihat seseorang menggunakan ArrayDeque dalam kode mereka. Jika seseorang memberi lebih banyak penjelasan tentang bagaimana ArrayDeque diimplementasikan, itu akan sangat membantu.

Jika saya memahaminya, saya akan lebih percaya diri menggunakannya. Saya tidak dapat dengan jelas memahami implementasi JDK mengenai cara mengelola referensi kepala dan ekor.

Kejam
sumber
5
Lihatlah jawaban dalam pertanyaan ini yang saya lakukan beberapa hari yang lalu: stackoverflow.com/questions/6129805/…
Renato Dinhani
1
Di folder, di mana Anda memiliki jdk Anda diinstal, ada file src.zip. Ini adalah arsip dengan kode sumber kelas java. Saya sangat merekomendasikan untuk mempelajari struktur kelas ini dan internal untuk mendapatkan pemahaman yang lebih baik bagaimana cara kerja kelas java.

Jawaban:

155

Struktur yang ditautkan mungkin merupakan struktur terburuk yang harus diulang dengan cache miss pada setiap elemen. Di atas itu mereka mengkonsumsi lebih banyak memori.

Jika Anda perlu menambah / menghapus kedua ujungnya, ArrayDeque secara signifikan lebih baik daripada daftar yang ditautkan. Akses acak setiap elemen juga O (1) untuk antrian siklik.

Satu-satunya operasi yang lebih baik dari daftar tertaut adalah menghapus elemen saat ini selama iterasi.

bestsss
sumber
57
Perbedaan lain yang perlu diingat: LinkedList mendukung elemen nol, sedangkan ArrayDeque tidak.
Luke Usherwood
15
Kerugian kecil lainnya (untuk aplikasi waktu nyata) adalah bahwa pada operasi push / add, dibutuhkan sedikit lebih banyak ketika array internal ArrayDeque penuh, karena harus menggandakan ukuran dan menyalin semua data.
Andrei I
4
@AndreiI, ini hanya satu sisi cerita. Bahkan jika Anda mengecualikan biaya iterasi untuk aplikasi waktu nyata dan kemampuan untuk merealokasi kapasitas yang dibutuhkan, GC mungkin perlu mengulangi seluruh LinkedList. Pada dasarnya Anda memindahkan biaya (yang lebih tinggi untuk boot) ke dalam GC.
bestsss
3
@ DavidT. b / c itu melibatkan biaya GC dari node yang dibebaskan, menugaskan kepala juga mungkin memerlukan penandaan kartu (untuk GC lagi, jika LinkedList sudah dalam gen bertenor) ... dan itu di atas tipuan ekstra (cache- miss) untuk mengembalikan elemen dan menghubungkan kembali.
bestsss
1
Juga, LinkedListmengimplementasikan Listsementara ArrayDequetidak. Ini berarti bahwa LinkedListmemiliki metode seperti indexOfatau remove(int)sementara ArrayDequebelum. Terkadang itu penting.
ZhekaKozlov
60

Saya percaya bahwa bottleneck kinerja utama LinkedListadalah kenyataan bahwa setiap kali Anda mendorong ke ujung deque, di balik layar implementasi mengalokasikan node daftar terkait baru, yang pada dasarnya melibatkan JVM / OS, dan itu mahal. Juga, setiap kali Anda muncul dari mana saja, node internal LinkedListmenjadi memenuhi syarat untuk pengumpulan sampah dan itu lebih banyak pekerjaan di belakang layar. Juga, karena node daftar tertaut dialokasikan di sana-sini, penggunaan cache CPU tidak akan memberikan banyak manfaat.

Jika mungkin menarik, saya punya bukti yang menambahkan (menambahkan) elemen ke ArrayListatau ArrayDequeberjalan dalam waktu konstan diamortisasi; lihat ini .

coderodde
sumber
26

ArrayDeque baru dengan Java 6, itulah sebabnya banyak kode (terutama proyek yang mencoba kompatibel dengan versi Java sebelumnya) tidak menggunakannya.

Ini "lebih baik" dalam beberapa kasus karena Anda tidak mengalokasikan node untuk setiap item untuk dimasukkan; alih-alih semua elemen disimpan dalam array raksasa, yang diubah ukurannya jika sudah penuh.

Chris Jester-Young
sumber
17

Semua orang mengkritik LinkedList, pikirkan tentang setiap lelaki lain yang telah menggunakan Listdi Jawa mungkin menggunakan ArrayListdan LinkedListsebagian besar waktu karena mereka telah sebelum Java 6 dan karena mereka yang diajarkan sebagai awal di sebagian besar buku.

Tapi, itu tidak berarti, saya akan memihak LinkedListatau membabi buta ArrayDeque. Jika Anda ingin tahu, lihat benchmark di bawah ini yang dilakukan oleh Brian .

Pengaturan pengujian mempertimbangkan:

  • Setiap objek uji adalah String 500 karakter. Setiap String adalah objek yang berbeda dalam memori.
  • Ukuran larik tes akan bervariasi selama pengujian.
  • Untuk setiap ukuran array / kombinasi implementasi antrian, 100 tes dijalankan dan rata-rata waktu-per-tes dihitung.
  • Setiap tes terdiri dari mengisi setiap antrian dengan semua objek, lalu menghapus semuanya.
  • Ukur waktu dalam milidetik.

Hasil tes:

  • Di bawah 10.000 elemen, tes LinkedList dan ArrayDeque rata-rata pada level sub 1 ms.
  • Ketika set data semakin besar, perbedaan antara waktu pengujian rata-rata ArrayDeque dan LinkedList menjadi lebih besar.
  • Pada ukuran pengujian 9.900.000 elemen, pendekatan LinkedList membutuhkan ~ 165% lebih lama dari pendekatan ArrayDeque.

Grafik:

masukkan deskripsi gambar di sini

Bawa pulang:

  • Jika kebutuhan Anda menyimpan 100 atau 200 elemen, itu tidak akan membuat banyak perbedaan menggunakan salah satu Antrian.
  • Namun, jika Anda mengembangkan di ponsel, Anda mungkin ingin menggunakan ArrayListatau ArrayDequedengan perkiraan kapasitas maksimum yang baik karena daftar tersebut mungkin diperlukan karena kendala memori yang ketat.
  • Ada banyak kode, ditulis menggunakan LinkedListtapak hati-hati ketika memutuskan untuk menggunakan ArrayDequeterutama karena TIDAK mengimplementasikan Listantarmuka (saya pikir itu alasannya cukup besar). Mungkin basis kode Anda berbicara ke antarmuka Daftar secara luas, kemungkinan besar dan Anda memutuskan untuk menggunakannya ArrayDeque. Menggunakannya untuk implementasi internal mungkin ide yang bagus ...
Manish Kumar Sharma
sumber
Bagaimana tolok ukur ini menangkap waktu GC yang disebabkan oleh sampah daftar tertaut?
0xbe5077ed
3

ArrayDeque dan LinkedList menerapkan antarmuka Deque tetapi implementasinya berbeda.

Perbedaan utama:

  1. Kelas ArrayDeque adalah implementasi array resizable dari antarmuka Deque dan kelas LinkedList adalah implementasi daftar

  2. Elemen NULL dapat ditambahkan ke LinkedList tetapi tidak di ArrayDeque

  3. ArrayDeque lebih efisien daripada LinkedList untuk menambah dan menghapus operasi di kedua ujungnya dan implementasi LinkedList efisien untuk menghilangkan elemen saat ini selama iterasi

  4. The LinkedList pelaksanaan mengkonsumsi memori lebih dari ArrayDeque

Jadi, jika Anda tidak harus mendukung elemen NULL && mencari lebih sedikit memori & & efisiensi menambah / menghapus elemen di kedua ujungnya, ArrayDeque adalah yang terbaik

Lihat dokumentasi untuk lebih jelasnya.

Ravindra babu
sumber
13
"Di daftar Tertaut, akan diperlukan O (N) untuk menemukan elemen terakhir." tidak sepenuhnya benar. LinkedList diimplementasikan sebagai daftar tertaut ganda sehingga Anda tidak perlu melintasi daftar untuk mendapatkan elemen terakhir ( header.previous.element). Klaim "efisiensi memori" juga dapat ditantang karena array backing selalu diubah ukurannya menjadi kekuatan berikutnya dari 2.
Clément MATHIEU
5
"Butuh O (N) untuk menemukan elemen terakhir" adalah SALAH. Daftar Linked menyimpan referensi ke node terakhir dan LinkedList.descendingIterator () get's node itu. Jadi kami mendapatkan kinerja O (1). Lihat: coffeeorientedprogramming.wordpress.com/2018/04/23/… (dengan demikian downvoting).
Leo Ufimtsev
1
Saat Anda menggunakan a Iteratoruntuk mengakses elemen terakhir, operasinya adalah O (N) untuk kedua kelas. Saat Anda menggunakan Dequeantarmuka umum , mengakses elemen terakhir adalah O (1) untuk kedua kelas. Terlepas dari sudut pandang mana Anda mengambil, menghubungkan O (1) ke ArrayDequedan O (N) LinkedListpada saat yang sama, salah.
Holger
Semua saran Anda diambil dan diperbaiki isinya
Ravindra babu
1

walaupun ArrayDeque<E>dan LinkedList<E>keduanya telah mengimplementasikan Deque<E>Interface, tetapi ArrayDeque pada dasarnya menggunakan array Object E[]untuk menjaga elemen-elemen di dalam Object-nya, sehingga umumnya menggunakan indeks untuk menemukan elemen head dan tail.

Singkatnya, ini hanya berfungsi seperti Deque (dengan semua metode Deque), namun menggunakan struktur data array. Mengenai mana yang lebih baik, tergantung pada bagaimana dan di mana Anda menggunakannya.

rekinyz
sumber
-1

Itu tidak selalu terjadi.

Misalnya, dalam kasus di bawah ini linkedlistmemiliki kinerja yang lebih baik daripada ArrayDequesesuai dengan leetcode 103.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rs=new ArrayList<>();
        if(root==null)
            return rs;
        // 👇 here ,linkedlist works better
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        boolean left2right=true;
        while(!queue.isEmpty())
        {
            int size=queue.size();
            LinkedList<Integer> t=new LinkedList<>();
            while(size-->0)
            {
                TreeNode tree=queue.remove();
                if(left2right)  
                    t.add(tree.val);
                else
                    t.addFirst(tree.val);
                if(tree.left!=null)
                {
                    queue.add(tree.left);
                }
                if(tree.right!=null)
                {
                    queue.add(tree.right);
                }
            }
            rs.add(t);
            left2right=!left2right;
        }
        return rs;
    }
}
Merah
sumber
-5

Kompleksitas waktu untuk ArrayDeque untuk mengakses elemen adalah O (1) dan untuk LinkList adalah O (N) untuk mengakses elemen terakhir. ArrayDeque bukan thread aman sehingga sinkronisasi secara manual diperlukan sehingga Anda dapat mengaksesnya melalui beberapa utas dan sehingga lebih cepat.

Piyush Yawalkar
sumber
3
Jika Anda merujuk LinkedListpada Java Collection, itu terhubung dua kali lipat dan memiliki akses cepat ke kepala dan ekor, sehingga akses ke elemen terakhir juga membutuhkan O (1).
Maurice
Mengakses elemen terakhir di LinkedList bukanlah O (N). Jika Anda menggunakan descendingIterator (), itu dilakukan di O (1). Lihat coffeeorientedprogramming.wordpress.com/2018/04/23/… (jadi downvote).
Leo Ufimtsev
1
Kedua kelas tidak aman untuk thread. Dan tidak ada hubungan antara awal kalimat "sinkronisasi secara manual diperlukan" dan akhirnya "mereka lebih cepat".
Holger