Kiedy powinienem użyć listy vs LinkedList

Kiedy lepiej jest użyć Lista vs w LinkedList ?

Edytować

Przeczytaj komentarze do tej odpowiedzi. Ludzie twierdzą, że nie wykonałem odpowiednich testów. Zgadzam się, że nie powinna to być akceptowana odpowiedź. Kiedy się uczyłem, zrobiłem kilka testów i miałem ochotę je udostępnić.

Oryginalna odpowiedź ...

Znalazłem ciekawe wyniki:

// 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;
    }
}

Powiązana lista (3,9 sekundy)

        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;

Lista (2,4 sekundy)

        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;

Nawet jeśli uzyskujesz dostęp do danych w zasadzie, jest to znacznie wolniejsze !! Mówię, że nigdy nie używaj LinkedList.

Oto kolejne porównanie wykonujące wiele wstawek (planujemy wstawić element na środku listy)

Lista połączona (51 sekund)

        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;

Lista (7,26 sekund)

        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;

Lista połączona z odniesieniem do lokalizacji, w której należy wstawić (.04 sekundy)

        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;

Więc tylko jeśli planujesz wstawić kilka elementów, a także gdzieś masz odniesienie do miejsca, w którym planujesz wstawić element, użyj listy połączonej. Tylko dlatego, że musisz wstawić wiele elementów, nie przyspiesza to, ponieważ wyszukiwanie miejsca, w którym chcesz je wstawić, zajmuje dużo czasu.

W większości przypadków List<T>jest bardziej przydatny. LinkedList<T>będzie miał mniejszy koszt podczas dodawania / usuwania elementów na środku listy, podczas gdy List<T>może tylko tanio dodawać / usuwać na końcu listy.

LinkedList<T>jest najskuteczniejszy tylko wtedy, gdy uzyskujesz dostęp do danych sekwencyjnych (do przodu lub do tyłu) - dostęp losowy jest stosunkowo drogi, ponieważ za każdym razem musi przechodzić przez łańcuch (dlatego nie ma indeksatora). Ponieważ jednak List<T>jest w zasadzie tylko tablicą (z opakowaniem), dostęp losowy jest w porządku.

List<T>również oferuje wiele sposobów wsparcia - Find, ToArrayitp; są one jednak dostępne również w LinkedList<T>przypadku .NET 3.5 / C # 3.0 za pomocą metod rozszerzenia - więc jest to mniej istotny czynnik.

Myślenie o połączonej liście jako liście może być nieco mylące. To bardziej jak łańcuch. W rzeczywistości .NET LinkedList<T>nawet nie implementuje IList<T>. Na połączonej liście nie ma prawdziwej koncepcji indeksu, chociaż może się wydawać, że tak jest. Z pewnością żadna z metod podanych w klasie nie akceptuje indeksów.

Listy połączone mogą być połączone pojedynczo lub podwójnie. Odnosi się to do tego, czy każdy element w łańcuchu ma link tylko do następnego (pojedynczo połączony) czy do obu poprzednich / następnych elementów (podwójnie połączony). LinkedList<T>jest podwójnie powiązany.

Wewnętrznie List<T>jest wspierany przez tablicę. Zapewnia to bardzo zwartą reprezentację w pamięci. I odwrotnie, LinkedList<T>wymaga dodatkowej pamięci do przechowywania dwukierunkowych połączeń między kolejnymi elementami. Tak więc ślad pamięci a LinkedList<T>będzie na ogół większy niż dla List<T>(z zastrzeżeniem, że List<T>może mieć nieużywane elementy wewnętrznej tablicy w celu poprawy wydajności podczas operacji dołączania).

Mają też różne parametry wydajnościowe:

Dodać

• LinkedList<T>.AddLast(item) stały czas
• List<T>.Add(item) zamortyzowany stały czas, najgorszy przypadek liniowy

Przygotuj

• LinkedList<T>.AddFirst(item) stały czas
• List<T>.Insert(0, item) czas liniowy

Wprowadzenie

• LinkedList<T>.AddBefore(node, item) stały czas
• LinkedList<T>.AddAfter(node, item) stały czas
• List<T>.Insert(index, item) czas liniowy

Usuwanie

• LinkedList<T>.Remove(item) czas liniowy
• LinkedList<T>.Remove(node) stały czas
• List<T>.Remove(item) czas liniowy
• List<T>.RemoveAt(index) czas liniowy

Liczyć

• LinkedList<T>.Count stały czas
• List<T>.Count stały czas

Zawiera

• LinkedList<T>.Contains(item) czas liniowy
• List<T>.Contains(item) czas liniowy

Jasny

• LinkedList<T>.Clear() czas liniowy
• List<T>.Clear() czas liniowy

Jak widać, są one w większości równoważne. W praktyce interfejs APILinkedList<T> jest trudniejszy w użyciu, a szczegóły jego wewnętrznych potrzeb rozlewają się do twojego kodu.

Jeśli jednak musisz wykonać wiele operacji wstawiania / usuwania z listy, oferuje ona stały czas. List<T>oferuje czas liniowy, ponieważ dodatkowe elementy na liście muszą zostać przetasowane po wstawieniu / usunięciu.

Listy połączone zapewniają bardzo szybkie wstawianie lub usuwanie członka listy. Każdy członek na połączonej liście zawiera wskaźnik do następnego członka na liście, aby wstawić członka w pozycji i:

• zaktualizuj wskaźnik w elemencie i-1, aby wskazywał na nowego członka
• ustaw wskaźnik w nowym elemencie, aby wskazywał na element i

Wadą połączonej listy jest to, że losowy dostęp nie jest możliwy. Dostęp do członka wymaga przemierzania listy aż do znalezienia żądanego członka.

Moja poprzednia odpowiedź nie była wystarczająco dokładna. Naprawdę było to okropne: D Ale teraz mogę opublikować o wiele bardziej przydatną i poprawną odpowiedź.

Zrobiłem kilka dodatkowych testów. Możesz znaleźć jego źródło, klikając poniższy link i ponownie sprawdź go w swoim środowisku: https://github.com/ukushu/DataStructuresTestsAndOther.git

Krótkie wyniki:

• Tablica musi używać:

  • Tak często jak to możliwe. Jest szybki i zajmuje najmniejszy zakres pamięci RAM dla tej samej ilości informacji.
  • Jeśli znasz dokładną liczbę potrzebnych komórek
  • Jeśli dane zapisane w tablicy <85000 b (85000/32 = 2656 elementów dla danych całkowitych)
  • W razie potrzeby wysoka prędkość dostępu losowego

• Lista musi użyć:

  • W razie potrzeby dodaj komórki na końcu listy (często)
  • W razie potrzeby dodaj komórki na początku / w środku listy (NIE CZĘSTO)
  • Jeśli dane zapisane w tablicy <85000 b (85000/32 = 2656 elementów dla danych całkowitych)
  • W razie potrzeby wysoka prędkość dostępu losowego

• LinkedList musi użyć:

  • W razie potrzeby dodaj komórki na początku / środku / końcu listy (często)
  • W razie potrzeby tylko dostęp sekwencyjny (do przodu / do tyłu)
  • Jeśli chcesz zapisać DUŻE przedmioty, ale liczba przedmiotów jest niska.
  • Lepiej nie używaj do dużej ilości przedmiotów, ponieważ używa to dodatkowej pamięci na linki.

Więcej szczegółów:

Ciekawe wiedzieć:

1. LinkedList<T>wewnętrznie nie jest listą w .NET. To nawet nie implementuje IList<T>. I dlatego nie ma indeksów i metod związanych z indeksami.

2. LinkedList<T>to kolekcja oparta na wskaźnikach węzłów. W .NET jest w podwójnie powiązanej implementacji. Oznacza to, że poprzednie / następne elementy mają link do bieżącego elementu. Dane są pofragmentowane - różne obiekty listy mogą znajdować się w różnych miejscach pamięci RAM. Będzie także wykorzystywana większa pamięć LinkedList<T>niż dla List<T>lub dla macierzy.

3. List<T>w .Net jest alternatywą Java dla ArrayList<T>. Oznacza to, że jest to opakowanie tablicy. Jest więc przydzielany w pamięci jako jeden ciągły blok danych. Jeśli przydzielony rozmiar danych przekracza 85000 bajtów, zostanie przeniesiony do sterty dużych obiektów. W zależności od wielkości może to prowadzić do fragmentacji sterty (łagodna forma wycieku pamięci). Ale w tym samym czasie, jeśli rozmiar <85000 bajtów - zapewnia bardzo kompaktową i szybką reprezentację w pamięci.

4. Pojedynczy ciągły blok jest preferowany dla wydajności dostępu losowego i zużycia pamięci, ale w kolekcjach, które muszą regularnie zmieniać rozmiar, struktura taka jak tablica zazwyczaj musi zostać skopiowana do nowej lokalizacji, podczas gdy połączona lista musi zarządzać pamięcią tylko dla nowo wstawionego / usunięte węzły.

Różnica między List a LinkedList polega na ich podstawowej implementacji. Lista jest kolekcją opartą na tablicy (ArrayList). LinkedList to kolekcja oparta na wskaźnikach węzłów (LinkedListNode). Na poziomie interfejsu API oba są prawie takie same, ponieważ oba implementują ten sam zestaw interfejsów, takich jak ICollection, IEnumerable itp.

Kluczowa różnica pojawia się, gdy liczy się wydajność. Na przykład, jeśli implementujesz listę, która ma ciężką operację „WSTAW”, LinkedList przewyższa Listę. Ponieważ LinkedList może to zrobić w czasie O (1), jednak List może wymagać rozszerzenia rozmiaru podstawowej tablicy. Aby uzyskać więcej informacji / szczegółów, możesz przeczytać o różnicy algorytmicznej między LinkedList a strukturami tablicowymi. http://en.wikipedia.org/wiki/Linked_list and Array

Mam nadzieję, że to pomoże,

Podstawową zaletą list połączonych w porównaniu z tablicami jest to, że linki zapewniają nam możliwość efektywnego rozmieszczania elementów. Sedgewick, p. 91

Typowa okoliczność korzystania z LinkedList wygląda następująco:

Załóżmy, że chcesz usunąć wiele określonych ciągów z listy ciągów o dużym rozmiarze, powiedzmy 100 000. Ciągi do usunięcia można sprawdzić w HashSet dic, a lista ciągów zawiera od 30 000 do 60 000 takich ciągów do usunięcia.

Jaki jest zatem najlepszy rodzaj Listy do przechowywania 100 000 Ciągów? Odpowiedź to LinkedList. Jeśli są one przechowywane w ArrayList, iteracja nad nim i usuwanie dopasowanych ciągów może zająć miliardy operacji, podczas gdy zajmie to około 100 000 operacji za pomocą iteratora i metody 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();
}

Gdy potrzebujesz wbudowanego dostępu do indeksowania, sortowania (i po tym wyszukiwaniu binarnym) oraz metody „ToArray ()”, powinieneś użyć List.

Zasadniczo, List<>w .NET to opakowanie na tablicę . A LinkedList<> jest połączoną listą . Pytanie sprowadza się więc do tego, jaka jest różnica między tablicą a listą połączoną i kiedy należy użyć tablicy zamiast listy połączonej. Prawdopodobnie dwa najważniejsze czynniki, które należy podjąć, to:

• Listy połączone mają znacznie lepszą wydajność wstawiania / usuwania, o ile wstawiania / usuwania nie znajdują się na ostatnim elemencie w kolekcji. Wynika to z faktu, że tablica musi przesunąć wszystkie pozostałe elementy, które występują po punkcie wstawiania / usuwania. Jeśli wstawianie / usuwanie znajduje się na końcu listy, to przesunięcie nie jest potrzebne (chociaż może zajść potrzeba zmiany rozmiaru tablicy, jeśli jej pojemność zostanie przekroczona).
• Tablice mają znacznie lepsze możliwości dostępu. Tablice można indeksować bezpośrednio (w stałym czasie). Listy połączone muszą być przeglądane (czas liniowy).

Jest to dostosowane z zaakceptowanej odpowiedzi Tono Nam korygującej kilka błędnych pomiarów.

Test:

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

I kod:

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

Możesz zobaczyć, że wyniki są zgodne z wynikami teoretycznymi, które inni tu udokumentowali. Całkiem jasne - LinkedList<T>zyskuje dużo czasu w przypadku wstawek. Nie testowałem usunięcia ze środka listy, ale wynik powinien być taki sam. Oczywiście List<T>ma inne obszary, w których działa o wiele lepiej, jak losowy dostęp O (1).

Użyj LinkedList<>kiedy

1. Nie wiesz, ile obiektów przechodzi przez bramę powodziową. Na przykład Token Stream.
2. Gdy TYLKO chcesz usunąć \ wstaw na końcach.

Do wszystkiego innego lepiej jest użyć List<>.

Zgadzam się z większością powyższych uwag. Zgadzam się również, że Lista w większości przypadków wydaje się bardziej oczywistym wyborem.

Ale chcę tylko dodać, że istnieje wiele przypadków, w których LinkedList jest znacznie lepszym wyborem niż List dla lepszej wydajności.

1. Załóżmy, że przemierzasz elementy i chcesz wykonać wiele operacji wstawiania / usuwania; LinkedList robi to w liniowym czasie O (n), podczas gdy List robi to w kwadratowym czasie O (n ^ 2).
2. Załóżmy, że chcesz ciągle uzyskiwać dostęp do większych obiektów, LinkedList staje się bardzo przydatny.
3. Deque () i queue () są lepiej implementowane za pomocą LinkedList.
4. Zwiększenie rozmiaru LinkedList jest znacznie łatwiejsze i lepsze, gdy masz do czynienia z wieloma i większymi obiektami.

Mam nadzieję, że ktoś uzna te komentarze za przydatne.

Tak wiele średnich odpowiedzi tutaj ...

Niektóre implementacje połączonych list używają podstawowych bloków wstępnie przydzielonych węzłów. Jeśli tego nie zrobią, czas stały / liniowy jest mniej istotny, ponieważ wydajność pamięci będzie niska, a wydajność pamięci podręcznej nawet gorsza.

Użyj połączonych list, kiedy

1) Chcesz bezpieczeństwa wątków. Możesz budować lepsze, bezpieczne dla wątków algorytmy. Koszty blokowania będą dominować na liście współbieżnych stylów.

2) Jeśli masz duże kolejki, takie jak struktury i chcesz usunąć lub dodać gdziekolwiek poza końcem przez cały czas. > Listy 100 000 istnieją, ale nie są tak powszechne.

Zadałem podobne pytanie związane z wydajnością kolekcji LinkedList i odkryłem, że implementacja Deque Stevena Cleary'ego w C # była rozwiązaniem. W przeciwieństwie do kolekcji Queue, Deque umożliwia przenoszenie przedmiotów z przodu iz tyłu. Jest podobny do listy połączonej, ale ma lepszą wydajność.