Kapan saya harus menggunakan Daftar vs LinkedList

Kapan lebih baik menggunakan Daftar vs LinkedList ?

Edit

Silakan baca komentar untuk jawaban ini. Orang mengklaim saya tidak melakukan tes yang tepat. Saya setuju ini seharusnya bukan jawaban yang diterima. Ketika saya belajar saya melakukan beberapa tes dan merasa ingin membagikannya.

Jawaban asli ...

Saya menemukan hasil yang menarik:

// Temporary class to show the example
class Temp
{
    public decimal A, B, C, D;

    public Temp(decimal a, decimal b, decimal c, decimal d)
    {
        A = a;            B = b;            C = c;            D = d;
    }
}

Daftar tertaut (3,9 detik)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.AddLast(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Daftar (2,4 detik)

        List<Temp> list = new List<Temp>(); // 2.4 seconds

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.Add(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Bahkan jika Anda hanya mengakses data pada dasarnya itu jauh lebih lambat !! Saya katakan tidak pernah menggunakan LinkedList.

Berikut adalah perbandingan lain yang melakukan banyak sisipan (kami berencana untuk memasukkan item di tengah daftar)

Daftar Tertaut (51 detik)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            var curNode = list.First;

            for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
                curNode = curNode.Next;

            list.AddAfter(curNode, a); // Insert it after
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Daftar (7,26 detik)

        List<Temp> list = new List<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.Insert(i / 2, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Daftar Tertaut memiliki referensi lokasi tempat memasukkan (0,04 detik)

        list.AddLast(new Temp(1,1,1,1));
        var referenceNode = list.First;

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            list.AddBefore(referenceNode, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Jadi hanya jika Anda berencana untuk memasukkan beberapa item dan Anda juga di suatu tempat memiliki referensi di mana Anda berencana untuk memasukkan item kemudian gunakan daftar tertaut. Hanya karena Anda harus memasukkan banyak item, itu tidak membuatnya lebih cepat karena mencari lokasi di mana Anda ingin memasukkannya membutuhkan waktu.

Dalam kebanyakan kasus, List<T>ini lebih bermanfaat. LinkedList<T>akan memiliki biaya lebih sedikit ketika menambahkan / menghapus item di tengah daftar, sedangkan List<T>hanya dapat menambahkan / menghapus dengan murah di akhir daftar.

LinkedList<T>hanya itu yang paling efisien jika Anda mengakses data berurutan (baik maju atau mundur) - akses acak relatif mahal karena harus berjalan di rantai setiap kali (karenanya mengapa tidak memiliki pengindeks). Namun, karena a List<T>pada dasarnya hanyalah sebuah array (dengan pembungkus) akses acak baik-baik saja.

List<T>juga menawarkan banyak metode dukungan - Find, ToArray, dll; Namun, ini juga tersedia untuk LinkedList<T>dengan .NET 3.5 / C # 3.0 melalui metode ekstensi - sehingga kurang dari faktor.

Memikirkan daftar tertaut sebagai daftar bisa sedikit menyesatkan. Ini lebih seperti sebuah rantai. Bahkan, dalam. NET, LinkedList<T>bahkan tidak diimplementasikan IList<T>. Tidak ada konsep indeks yang nyata dalam daftar tertaut, meskipun tampaknya ada. Tentu saja tidak ada metode yang disediakan di kelas menerima indeks.

Daftar tertaut dapat ditautkan secara tunggal, atau ditautkan secara ganda. Ini mengacu pada apakah setiap elemen dalam rantai hanya memiliki tautan ke yang berikutnya (ditautkan sendiri) atau ke kedua elemen sebelumnya / berikutnya (ditautkan dua kali). LinkedList<T>terkait dua kali lipat.

Secara internal, List<T>didukung oleh sebuah array. Ini memberikan representasi yang sangat kompak dalam memori. Sebaliknya, LinkedList<T>melibatkan memori tambahan untuk menyimpan tautan dua arah antara elemen yang berurutan. Jadi jejak memori a LinkedList<T>umumnya akan lebih besar daripada untuk List<T>(dengan peringatan yang List<T>dapat memiliki elemen array internal yang tidak digunakan untuk meningkatkan kinerja selama operasi penambahan.)

Mereka memiliki karakteristik kinerja yang berbeda juga:

Menambahkan

• LinkedList<T>.AddLast(item) waktu yang konstan
• List<T>.Add(item) waktu konstan diamortisasi, kasus terburuk linier

Tergantung

• LinkedList<T>.AddFirst(item) waktu yang konstan
• List<T>.Insert(0, item) waktu linier

Insersi

• LinkedList<T>.AddBefore(node, item) waktu yang konstan
• LinkedList<T>.AddAfter(node, item) waktu yang konstan
• List<T>.Insert(index, item) waktu linier

Pemindahan

• LinkedList<T>.Remove(item) waktu linier
• LinkedList<T>.Remove(node) waktu yang konstan
• List<T>.Remove(item) waktu linier
• List<T>.RemoveAt(index) waktu linier

Menghitung

• LinkedList<T>.Count waktu yang konstan
• List<T>.Count waktu yang konstan

Mengandung

• LinkedList<T>.Contains(item) waktu linier
• List<T>.Contains(item) waktu linier

Bersih

• LinkedList<T>.Clear() waktu linier
• List<T>.Clear() waktu linier

Seperti yang Anda lihat, mereka kebanyakan setara. Dalam praktiknya, API dariLinkedList<T> lebih rumit untuk digunakan, dan rincian kebutuhan internalnya mencurahkan ke dalam kode Anda.

Namun, jika Anda perlu melakukan banyak penyisipan / pemindahan dari dalam daftar, ia menawarkan waktu yang konstan. List<T>menawarkan waktu linier, karena item tambahan dalam daftar harus dikocok setelah penyisipan / penghapusan.

Daftar tertaut menyediakan penyisipan atau penghapusan anggota daftar yang sangat cepat. Setiap anggota dalam daftar tertaut berisi pointer ke anggota berikutnya dalam daftar sehingga untuk memasukkan anggota pada posisi i:

• perbarui pointer di anggota i-1 untuk menunjuk ke anggota baru
• atur pointer di anggota baru untuk menunjuk ke anggota i

Kerugian dari daftar tertaut adalah akses acak tidak dimungkinkan. Mengakses anggota memerlukan melintasi daftar sampai anggota yang diinginkan ditemukan.

Jawaban saya sebelumnya tidak cukup akurat. Benar-benar mengerikan: D Tetapi sekarang saya dapat memposting jawaban yang jauh lebih berguna dan benar.

Saya melakukan beberapa tes tambahan. Anda dapat menemukan sumbernya dengan tautan berikut dan periksa kembali di lingkungan Anda sendiri: https://github.com/ukushu/DataStructuresTestsAndOther.git

Hasil singkat:

• Array perlu digunakan:

  • Sesering mungkin. Cepat dan membutuhkan rentang RAM terkecil untuk informasi jumlah yang sama.
  • Jika Anda tahu jumlah pasti sel yang dibutuhkan
  • Jika data disimpan dalam array <85000 b (85000/32 = 2656 elemen untuk data integer)
  • Jika diperlukan kecepatan Akses Acak tinggi

• Daftar harus digunakan:

  • Jika perlu menambahkan sel ke akhir daftar (sering)
  • Jika perlu menambahkan sel di awal / tengah daftar (BUKAN SERING)
  • Jika data disimpan dalam array <85000 b (85000/32 = 2656 elemen untuk data integer)
  • Jika diperlukan kecepatan Akses Acak tinggi

• LinkedList perlu menggunakan:

  • Jika perlu menambahkan sel di awal / tengah / akhir daftar (sering)
  • Jika diperlukan hanya akses sekuensial (maju / mundur)
  • Jika Anda perlu menyimpan item BESAR, tetapi jumlah item rendah.
  • Lebih baik tidak menggunakan item dalam jumlah besar, karena menggunakan memori tambahan untuk tautan.

Keterangan lebih lanjut:

Menarik untuk diketahui:

1. LinkedList<T>secara internal bukan Daftar di .NET. Itu bahkan tidak diimplementasikan IList<T>. Dan itu sebabnya ada indeks dan metode yang tidak ada terkait dengan indeks.

2. LinkedList<T>adalah koleksi berbasis simpul-pointer. Dalam. NET itu dalam implementasi terkait dua kali lipat. Ini berarti bahwa elemen sebelum / berikutnya memiliki tautan ke elemen saat ini. Dan data terfragmentasi - objek daftar yang berbeda dapat ditemukan di berbagai tempat RAM. Juga akan ada lebih banyak memori yang digunakan LinkedList<T>daripada untuk List<T>atau Array.

3. List<T>di .Net adalah alternatif Java dari ArrayList<T>. Ini berarti bahwa ini adalah pembungkus array. Jadi itu dialokasikan dalam memori sebagai satu blok data yang berdekatan. Jika ukuran data yang dialokasikan melebihi 85000 byte, itu akan dipindahkan ke Tumpukan Objek Besar. Tergantung pada ukuran, ini dapat menyebabkan tumpukan tumpukan (bentuk kebocoran memori ringan). Tetapi dalam waktu yang sama jika ukuran <85000 byte - ini memberikan representasi yang sangat ringkas dan akses cepat dalam memori.

4. Blok bersebelahan tunggal lebih disukai untuk kinerja akses acak dan konsumsi memori tetapi untuk koleksi yang perlu mengubah ukuran secara teratur struktur seperti Array umumnya perlu disalin ke lokasi baru sedangkan daftar tertaut hanya perlu mengelola memori untuk yang baru dimasukkan / menghapus node.

Perbedaan antara Daftar dan LinkedList terletak pada implementasi yang mendasarinya. Daftar adalah koleksi berbasis array (ArrayList). LinkedList adalah koleksi berbasis simpul-pointer (LinkedListNode). Pada penggunaan level API, keduanya hampir sama karena keduanya mengimplementasikan set antarmuka yang sama seperti ICollection, IEnumerable, dll.

Perbedaan utama muncul ketika masalah kinerja. Misalnya, jika Anda menerapkan daftar yang memiliki operasi "INSERT" berat, LinkedList mengungguli Daftar. Karena LinkedList dapat melakukannya dalam waktu O (1), tetapi Daftar mungkin perlu memperluas ukuran array yang mendasarinya. Untuk informasi lebih lanjut / detail Anda mungkin ingin membaca tentang perbedaan algoritmik antara LinkedList dan struktur data array. http://en.wikipedia.org/wiki/Linked_list dan Array

Semoga bantuan ini,

Keuntungan utama daftar yang ditautkan daripada array adalah bahwa tautan tersebut memberi kami kemampuan untuk mengatur ulang item secara efisien. Sedgewick, hlm. 91

Keadaan umum untuk menggunakan LinkedList adalah seperti ini:

Misalkan Anda ingin menghapus banyak string tertentu dari daftar string dengan ukuran besar, katakanlah 100.000. String yang akan dihapus dapat dicari di HashSet dic, dan daftar string diyakini mengandung antara 30.000 hingga 60.000 string yang harus dihapus.

Lalu apa jenis Daftar terbaik untuk menyimpan 100.000 Strings? Jawabannya adalah LinkedList. Jika mereka disimpan dalam ArrayList, maka iterasi di atasnya dan menghapus Strings yang cocok akan membutuhkan milyaran operasi, sementara itu hanya membutuhkan sekitar 100.000 operasi dengan menggunakan iterator dan metode remove ().

LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
    String string = iterator.next();
    if (dic.contains(string))
    iterator.remove();
}

Ketika Anda membutuhkan akses indeks bawaan, pengurutan (dan setelah pencarian biner ini), dan metode "ToArray ()", Anda harus menggunakan Daftar.

Pada dasarnya, List<>dalam. NET adalah pembungkus array . A LinkedList<> adalah daftar tertaut . Jadi pertanyaannya adalah, apa perbedaan antara array dan daftar yang ditautkan, dan kapan seharusnya sebuah array digunakan daripada daftar yang ditautkan. Mungkin dua faktor terpenting dalam keputusan Anda yang akan digunakan adalah:

• Daftar yang ditautkan memiliki kinerja penyisipan / penghilangan yang jauh lebih baik, asalkan penyisipan / pemindahan tidak pada elemen terakhir dalam koleksi. Ini karena array harus menggeser semua elemen yang tersisa setelah titik penyisipan / penghapusan. Namun, jika penyisipan / pemindahan berada di ujung ekor daftar, pergeseran ini tidak diperlukan (meskipun array mungkin perlu diubah ukurannya, jika kapasitasnya terlampaui).
• Array memiliki kemampuan mengakses yang jauh lebih baik. Array dapat diindeks menjadi langsung (dalam waktu konstan). Daftar tertaut harus dilalui (waktu linier).

Ini diadaptasi dari jawaban yang diterima Tono Nam yang mengoreksi beberapa pengukuran yang salah di dalamnya.

Ujian:

static void Main()
{
    LinkedListPerformance.AddFirst_List(); // 12028 ms
    LinkedListPerformance.AddFirst_LinkedList(); // 33 ms

    LinkedListPerformance.AddLast_List(); // 33 ms
    LinkedListPerformance.AddLast_LinkedList(); // 32 ms

    LinkedListPerformance.Enumerate_List(); // 1.08 ms
    LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms

    //I tried below as fun exercise - not very meaningful, see code
    //sort of equivalent to insertion when having the reference to middle node

    LinkedListPerformance.AddMiddle_List(); // 5724 ms
    LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
    LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
    LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms

    Environment.Exit(-1);
}

Dan kodenya:

using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace stackoverflow
{
    static class LinkedListPerformance
    {
        class Temp
        {
            public decimal A, B, C, D;

            public Temp(decimal a, decimal b, decimal c, decimal d)
            {
                A = a; B = b; C = c; D = d;
            }
        }



        static readonly int start = 0;
        static readonly int end = 123456;
        static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);

        static Temp temp(int i)
        {
            return new Temp(i, i, i, i);
        }

        static void StopAndPrint(this Stopwatch watch)
        {
            watch.Stop();
            Console.WriteLine(watch.Elapsed.TotalMilliseconds);
        }

        public static void AddFirst_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(0, temp(i));

            watch.StopAndPrint();
        }

        public static void AddFirst_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddFirst(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Add(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        public static void Enumerate_List()
        {
            var list = new List<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        public static void Enumerate_LinkedList()
        {
            var list = new LinkedList<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        //for the fun of it, I tried to time inserting to the middle of 
        //linked list - this is by no means a realistic scenario! or may be 
        //these make sense if you assume you have the reference to middle node

        //insertion to the middle of list
        public static void AddMiddle_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(list.Count / 2, temp(i));

            watch.StopAndPrint();
        }

        //insertion in linked list in such a fashion that 
        //it has the same effect as inserting into the middle of list
        public static void AddMiddle_LinkedList1()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            LinkedListNode<Temp> evenNode = null, oddNode = null;
            for (int i = start; i < end; i++)
            {
                if (list.Count == 0)
                    oddNode = evenNode = list.AddLast(temp(i));
                else
                    if (list.Count % 2 == 1)
                        oddNode = list.AddBefore(evenNode, temp(i));
                    else
                        evenNode = list.AddAfter(oddNode, temp(i));
            }

            watch.StopAndPrint();
        }

        //another hacky way
        public static void AddMiddle_LinkedList2()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start + 1; i < end; i += 2)
                list.AddLast(temp(i));
            for (int i = end - 2; i >= 0; i -= 2)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        //OP's original more sensible approach, but I tried to filter out
        //the intermediate iteration cost in finding the middle node.
        public static void AddMiddle_LinkedList3()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
            {
                if (list.Count == 0)
                    list.AddLast(temp(i));
                else
                {
                    watch.Stop();
                    var curNode = list.First;
                    for (var j = 0; j < list.Count / 2; j++)
                        curNode = curNode.Next;
                    watch.Start();

                    list.AddBefore(curNode, temp(i));
                }
            }

            watch.StopAndPrint();
        }
    }
}

Anda dapat melihat hasilnya sesuai dengan kinerja teoritis yang telah didokumentasikan orang lain di sini. Cukup jelas - LinkedList<T>mendapatkan waktu besar jika dimasukkan. Saya belum menguji penghapusan dari bagian tengah daftar, tetapi hasilnya harus sama. Tentu saja List<T>memiliki area lain di mana ia berkinerja lebih baik seperti O (1) akses acak.

Gunakan LinkedList<>kapan

1. Anda tidak tahu berapa banyak benda yang melewati gerbang banjir. Sebagai contoh Token Stream,.
2. Ketika Anda HANYA ingin menghapus \ masukkan di ujungnya.

Untuk yang lainnya, lebih baik digunakan List<>.

Saya setuju dengan sebagian besar poin di atas. Dan saya juga setuju bahwa Daftar terlihat seperti pilihan yang lebih jelas dalam sebagian besar kasus.

Tapi, saya hanya ingin menambahkan bahwa ada banyak contoh di mana LinkedList adalah pilihan yang jauh lebih baik daripada Daftar untuk efisiensi yang lebih baik.

1. Misalkan Anda melintasi elemen-elemen dan Anda ingin melakukan banyak penyisipan / penghapusan; LinkedList melakukannya dalam waktu O (n) linear, sedangkan Daftar melakukannya dalam kuadrat O (n ^ 2) waktu.
2. Misalkan Anda ingin mengakses objek yang lebih besar lagi dan lagi, LinkedList menjadi sangat berguna.
3. Deque () dan antrian () lebih baik diimplementasikan menggunakan LinkedList.
4. Meningkatkan ukuran LinkedList jauh lebih mudah dan lebih baik setelah Anda berurusan dengan banyak objek yang lebih besar.

Semoga seseorang akan menemukan komentar ini bermanfaat.

Begitu banyak jawaban rata-rata di sini ...

Beberapa implementasi daftar tertaut menggunakan blok yang mendasari node yang dialokasikan sebelumnya. Jika mereka tidak melakukan ini daripada waktu konstan / waktu linier kurang relevan karena kinerja memori akan buruk dan kinerja cache lebih buruk.

Gunakan daftar tertaut saat

1) Anda menginginkan keamanan utas. Anda dapat membangun algo yang lebih aman. Biaya penguncian akan mendominasi daftar gaya bersamaan.

2) Jika Anda memiliki struktur seperti antrian besar dan ingin menghapus atau menambahkan di mana saja tetapi akhirnya sepanjang waktu. > Daftar 100K ada tetapi tidak umum.

Saya mengajukan pertanyaan serupa terkait dengan kinerja koleksi LinkedList , dan menemukan penerapan Cque karya Steven Cleary dari Deque adalah solusinya. Berbeda dengan koleksi Antrian, Deque memungkinkan barang bergerak on / off depan dan belakang. Ini mirip dengan daftar tertaut, tetapi dengan peningkatan kinerja.