Kiedy powinienem używać listy a listy LinkedList

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

LinkedList<T> jest tylko najbardziej wydajny, jeśli uzyskujesz dostęp do danych sekwencyjnych ( do przodu lub do tyłu) - dostęp losowy jest stosunkowo drogi, ponieważ musi chodzić po łańcuchu za każdym razem (stąd dlaczego nie ma indeksatora). Jednak, ponieważ List<T> jest w zasadzie tylko tablicą (z wrapper) przypadkowy dostęp jest w porządku.

List<T> oferuje również wiele metod wsparcia- Find, ToArray, jednak są one również dostępne dla LinkedList<T> Z. NET 3.5/C # 3.0 za pomocą metod rozszerzeń - więc jest to mniejszy czynnik.

Myślenie o powiązanej liście jako liście może być nieco mylące. To bardziej jak łańcuch. W rzeczywistości, w.NET, LinkedList<T> nawet nie implementuje IList<T>. Nie ma prawdziwego pojęcia indeksu na liście linkowanej, chociaż może się wydawać, że istnieje. Z pewnością żadna z metod podanych na 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 ogniwo tylko do następnego (pojedynczo połączone) lub zarówno do poprzedniego / następnego elementy (podwójnie połączone). {[0] } jest podwójnie połączone.

Wewnętrznie, List<T> jest wspierane przez tablicę. Zapewnia to bardzo zwartą reprezentację w pamięci. Odwrotnie, LinkedList<T> zawiera dodatkową pamięć do przechowywania dwukierunkowych powiązań między kolejnymi elementami. Tak więc rozmiar pamięci LinkedList<T> będzie na ogół większy niż dla List<T> (z zastrzeżeniem, że List<T> może mieć nieużywane wewnętrzne elementy tablicy, aby poprawić wydajność podczas operacji dołączania.)

Mają różne charakterystyka wydajności też:

Append

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

Prepend

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

Wstawianie

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

Usunięcie

• 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

Count

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

Zawiera

• LinkedList<T>.Contains(item) / align = " left czas
• List<T>.Contains(item) czas liniowy

Wyczyść

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

Jak widzisz, są w większości równoważne. W praktyce API LinkedList<T> jest bardziej kłopotliwe w użyciu, a szczegóły jego wewnętrznych potrzeb rozlewają się w Twoim kodzie.

Jednakże, jeśli musisz wykonać wiele wstawiania/usuwania z listy, oferuje ona stały czas. List<T> oferuje czas liniowy, jako dodatkowe elementy na liście muszą być tasowane 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 na pozycję i:

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

Wadą połączonej listy jest to, że dostęp losowy nie jest możliwy. Dostęp do członka wymaga przechodzenia przez Listę, aż do żądanego członek został znaleziony.

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

Kluczowa różnica pojawia się, gdy wydajność ma znaczenie. Na przykład, jeśli implementujesz listę z ciężką operacją "Wstaw", LinkedList / align = "left" / Ponieważ LinkedList może to zrobić w czasie O( 1), ale List może wymagać rozszerzenia rozmiaru bazowej tablicy. Aby uzyskać więcej informacji / szczegółów, warto przeczytać o algorytmicznej różnicy między strukturami danych LinkedList i array. http://en.wikipedia.org/wiki/Linked_list and Array

Hope this help,

Podstawową zaletą list linkowanych nad tablicami jest to, że linki dają nam możliwość efektywnego przestawiania elementów. Sedgewick, str. 91

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

Krótkie wyniki:

• Array need to use:

  Tak często, jak to tylko możliwe. Jest szybki i zajmuje najmniejsze Zakres RAM dla tej samej ilości informacji.
• jeśli znasz dokładną liczbę potrzebnych komórek
• jeśli dane zapisane w tablicy
• w razie potrzeby wysoka prędkość dostępu losowego

Więcej szczegółów:

interesujące wiedzieć:

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

2. LinkedList<T> jest zbiorem opartym na wskaźniku węzła. W. NET jest to implementacja podwójnie powiązana. Oznacza to, że poprzednie/następne elementy mają łącze do bieżącego elementu. A dane są fragmentaryczne-różne obiekty listy mogą znajdować się w różnych miejscach pamięci RAM. Będzie też więcej pamięci for LinkedList<T> niż for List<T> lub Array.

3. List<T> W. Net jest alternatywą Javy ArraList<T>. Oznacza to, że jest to wrapper tablicy. Więc jest alokowany w menory jako jeden ciągły blok danych. Jeśli wielkość przydzielonych danych przekracza 85000 bajtów, zostanie ona przydzielona iside sterty dużych obiektów. W zależności od wielkości może to prowadzić do fragmentacji sterty, łagodnej formy wycieku pamięci. Ale w tym samym czasie, jeśli rozmiar

4. Pojedynczy sąsiadujący blok jest preferowany dla wydajności dostępu losowego i zużycia pamięci, ale w przypadku kolekcji, które muszą regularnie zmieniać rozmiar, struktura, taka jak tablica, zazwyczaj musi być skopiowana do nowej lokalizacji, podczas gdy powiązana lista musi zarządzać pamięcią tylko dla nowo wstawionych / usuniętych węzłów.

Typowa okoliczność użycia LinkedList jest taka:

Załóżmy, że chcesz usunąć wiele pewnych 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.

Więc jaki jest najlepszy typ Listy Do Przechowywania 100 000 ciągów? Odpowiedź jest LinkedList. Jeśli są one przechowywane w ArrayList, to iterację nad nim i usuwanie dopasowanych strun, które mogłyby zająć do miliardăłw operacji, podczas gdy zajmuje to tylko okoĹ ' o 100 000 operacji przy uĹźyciu 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();
}

Jeśli potrzebujesz wbudowanego dostępu indeksowanego, sortowania (i po tym przeszukiwaniu binarnym) oraz metody" ToArray ()", powinieneś użyć List.

Jest to zaadaptowane z tono Nam 's zaakceptowanej odpowiedzi korygującej kilka błędnych pomiarów w nim.

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żna zobaczyć wyniki są zgodne z teoretyczną wydajność inni udokumentowane tutaj. Całkiem jasne- LinkedList<T> zyskuje duży czas w przypadku wstawek. Nie testowałem usuwania 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 o (1) dostęp losowy.

Zasadniczo, List<> W. NET jest opakowaniem nad 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 powinna być używana Tablica zamiast listy połączonej. Prawdopodobnie dwa najważniejsze czynniki w twojej decyzji, którego użyć, sprowadzą się do:

• listy połączone mają znacznie lepszą wydajność wstawiania/usuwania, o ile wstawiania/usuwania nie są na ostatnim elemencie w kolekcja. Dzieje się tak dlatego, że tablica musi przesunąć wszystkie pozostałe elementy, które pojawiają się po punkcie wstawiania/usuwania. Jeśli jednak wstawianie/usuwanie znajduje się na końcu listy, przesunięcie to nie jest potrzebne (chociaż tablica może wymagać zmiany rozmiaru, jeśli jej pojemność zostanie przekroczona).
• Macierze mają znacznie lepsze możliwości dostępu. Tablice mogą być indeksowane bezpośrednio (w stałym czasie). Listy połączone muszą być przemieszczane (czas liniowy).

Użyj LinkedList<> Kiedy

Nie wiesz, ile obiektów przechodzi przez wrota przeciwpowodziowe. Na przykład Token Stream.
1. gdy chciałeś tylko usunąć \ insert na końcach.

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

Tyle przeciętnych odpowiedzi tutaj...

Niektóre implementacje list linkowanych używają bazowych bloków wcześniej przydzielonych węzłów. Jeśli tego nie zrobią, stały czas / czas liniowy jest mniej istotny, ponieważ wydajność pamięci będzie słaba, a wydajność pamięci podręcznej jeszcze gorsza.

Użyj list połączonych, gdy

1) chcesz bezpieczeństwa wątku. Możesz zbudować lepszy thread safe algos. Koszty blokowania będą dominować na liście stylów współbieżnych.

2) Jeśli masz dużą kolejkę jak struktury i chcesz usunąć lub dodać gdziekolwiek, ale koniec cały czas . > Listy 100K istnieją, ale nie są tak powszechne.

Zadałem podobne pytanie związane z wydajnością kolekcji LinkedList i odkryłemimplementację języka deque w języku C# Stevena Cleary ' ego. W przeciwieństwie do kolekcji Queue, deque umożliwia włączanie/wyłączanie przedmiotów z przodu iz tyłu. Jest podobny do linked list, ale z lepszą wydajnością.

Zgadzam się z większością powyższych punktów. Zgadzam się też, że lista wygląda na bardziej oczywisty wybór w większości przypadków.

Ale chcę tylko dodać, że istnieje wiele przypadków, w których LinkedList są znacznie lepszym Wyborem niż Lista dla lepszej wydajności.

1. Załóżmy, że przechodzisz przez elementy i chcesz wykonać wiele wstawiania/usuwania; LinkedList robi to w czasie liniowym O( n), podczas gdy List robi to w czasie kwadratowym O(N^2).
2. przypuśćmy, że chcesz uzyskać dostęp do większych obiektów raz za razem, LinkedList stają się bardzo przydatne.
3. Deque () i queue() są lepiej zaimplementowane przy użyciu 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.