Kiedy powinienem użyć listy vs LinkedList

392

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

Jonathan Allen
źródło
3
Java q , nie powinna być zupełnie inna.
nawfal
1
@ jonathan-allen, Proszę rozważyć zmianę zaakceptowanej odpowiedzi. Obecny jest niedokładny i bardzo mylący.
Xpleria,

Odpowiedzi:

107

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.

Tono Nam
źródło
99
Jest jedna zaleta LinkedList w porównaniu z Listą (jest to specyficzne dla .net): ponieważ List jest wspierany przez wewnętrzną tablicę, jest on przydzielany w jednym ciągłym bloku. Jeśli ten przydzielony blok przekroczy rozmiar 85000 bajtów, zostanie przydzielony na stosie dużych obiektów, generacji, której nie można kompaktować. W zależności od wielkości może to prowadzić do fragmentacji sterty, łagodnej formy wycieku pamięci.
JerKimball
35
Zauważ, że jeśli dużo przygotowujesz (tak jak to robisz w ostatnim przykładzie) lub usuwasz pierwszy wpis, połączona lista prawie zawsze będzie znacznie szybsza, ponieważ nie ma potrzeby wyszukiwania ani przenoszenia / kopiowania. Lista wymagałaby przesunięcia wszystkiego w górę o miejsce, aby pomieścić nowy element, dzięki czemu można było wykonać operację O (N).
cHao
6
Dlaczego pętla list.AddLast(a);w dwóch ostatnich przykładach LinkedList? Robię to raz przed pętlą, jak list.AddLast(new Temp(1,1,1,1));w przypadku następnej do ostatniej LinkedList, ale wygląda (dla mnie), jakbyś dodawał dwa razy więcej obiektów Temp w samych pętlach. (A kiedy sprawdzę się dwukrotnie za pomocą aplikacji testowej , to na pewno dwa razy więcej na LinkedList.)
ruffin
7
Głosowałem za odpowiedzią w tej sprawie. 1) Twoja ogólna rada I say never use a linkedList.jest wadliwa, jak ujawnia twój późniejszy post. Możesz go edytować. 2) Jaki masz czas? Tworzenie instancji, dodawanie i wyliczanie łącznie w jednym kroku? Przeważnie tworzenie instancji i wyliczanie nie są tym, czym martwi się ppl, są to jednorazowe kroki. Dokładniej mówiąc, wstawianie i dodawanie wstawek w czasie dałoby lepszy pomysł. 3) Co najważniejsze, dodajesz więcej niż to wymagane do listy połączonej. To jest złe porównanie. Rozpowszechnia błędne wyobrażenie o linkowanej liście.
nawfal
47
Przepraszam, ale ta odpowiedź jest naprawdę zła. NIE słuchaj tej odpowiedzi. Powód w skrócie: błędem jest sądzić, że implementacje list wspierane przez tablicę są na tyle głupie, że zmieniają rozmiar tablicy przy każdym wstawieniu. Listy połączone są naturalnie wolniejsze niż listy wspierane przez tablicę podczas przechodzenia, a także podczas wstawiania na obu końcach, ponieważ tylko one muszą tworzyć nowe obiekty, podczas gdy listy wspierane przez tablicę używają bufora (oczywiście w obu kierunkach). (Słabo wykonane) testy porównawcze dokładnie to wskazują. Odpowiedź całkowicie nie sprawdza przypadków, w których preferowane są listy połączone!
mafu
277

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.

Marc Gravell
źródło
4
Jedną z zalet List <> vs. LinkedList <>, o której nigdy nie myślałem, jest to, jak mikroprocesory implementują buforowanie pamięci. Chociaż nie rozumiem tego całkowicie, autor tego artykułu na blogu dużo mówi o „lokalizacji odniesienia”, co sprawia, że ​​przemierzanie tablicy jest znacznie szybsze niż przeglądanie połączonej listy, przynajmniej jeśli lista połączona została nieco rozproszona w pamięci . kjellkod.wordpress.com/2012/02/25/…
RenniePet
@RenniePet List jest implementowany z dynamiczną tablicą, a tablice są ciągłymi blokami pamięci.
Casey,
2
Ponieważ List jest dynamiczną tablicą, dlatego czasami dobrze jest określić pojemność Listy w konstruktorze, jeśli ją znasz.
Cardin Lee JH
Czy to możliwe, że implementacja C # wszystkich, tablic, List <T> i LinkedList <T> jest nieco nieoptymalna dla jednego bardzo ważnego przypadku: Potrzebujesz bardzo dużej listy, dołącz (AddLast) i sekwencyjnego przechodzenia (w jednym kierunku) całkowicie w porządku: nie chcę zmieniać rozmiaru tablicy, aby uzyskać ciągłe bloki (czy jest to gwarantowane dla każdej tablicy, nawet macierzy 20 GB?) i nie znam z góry rozmiaru, ale mogę z góry zgadnąć rozmiar bloku, np. 100 MB, aby zarezerwować za każdym razem z góry. To byłoby dobre wdrożenie. A może tablica / lista jest podobna do tego i nie zauważyłem żadnego punktu?
Philm,
1
@Film to taki scenariusz, w którym piszesz własny podkład nad wybraną strategią blokowania; List<T>i T[]nie powiedzie się, że jest zbyt gruby (wszystkie płyty), LinkedList<T>będzie lamentować, że jest zbyt ziarnisty (płyta na element).
Marc Gravell
212

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.

Drew Noakes
źródło
2
Czy liczba połączonych list jest stała? Myślałem, że to będzie liniowe?
Iain Ballard,
10
@Ilość jest buforowana w obu klasach list.
Drew Noakes,
3
Napisałeś, że „Lista <T> .Dodaj (logarytmiczny czas)”, jednak tak naprawdę „Stała”, jeśli pojemność listy może pomieścić nowy element, i „Liniowa”, jeśli lista nie ma wystarczającej ilości miejsca i nowa zostać przeniesionym.
aStranger,
@ aStranger, oczywiście masz rację. Nie jestem pewien, co myślałem powyżej - być może, że zamortyzowany normalny czas sprawy jest logarytmiczny, a tak nie jest. W rzeczywistości zamortyzowany czas jest stały. Nie wdałem się w najlepszy / najgorszy przypadek operacji, mając na celu proste porównanie. Myślę jednak, że operacja dodawania jest wystarczająco znacząca, aby podać ten szczegół. Zmieni odpowiedź. Dzięki.
Drew Noakes,
1
@Film, prawdopodobnie powinieneś zacząć nowe pytanie i nie mówisz, jak będziesz korzystać z tej struktury danych po zbudowaniu, ale jeśli mówisz milion wierszy, możesz polubić hybrydę (połączona lista fragmenty macierzy lub podobne), aby zmniejszyć fragmentację sterty, zmniejszyć obciążenie pamięci i uniknąć pojedynczego dużego obiektu w LOH.
Drew Noakes,
118

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.

b3.
źródło
6
Dodałbym, że listy połączone mają narzut na element przechowywany sugerowany powyżej za pośrednictwem LinkedListNode, który odwołuje się do poprzedniego i następnego węzła. Wypłata tego jest ciągły blok pamięci nie jest wymagane do przechowywania listy, w przeciwieństwie do listy opartej na tablicy.
paulecoyote
3
Czy zwykle nie przypisuje się ciągłego bloku pamięci?
Jonathan Allen
7
Tak, 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 tylko zarządzać pamięcią dla nowo wstawione / usunięte węzły.
jpierson
6
Jeśli kiedykolwiek musiałeś pracować z bardzo dużymi tablicami lub listami (lista po prostu zawija tablicę), zaczniesz napotykać problemy z pamięcią, nawet jeśli na twoim komputerze jest dużo pamięci. Lista stosuje strategię podwajania, gdy przydziela nowe miejsce w swojej podstawowej tablicy. Tak więc pełna tablica 1000000, która jest pełna, zostanie skopiowana do nowej tablicy zawierającej 2000000 elementów. Tę nową tablicę należy utworzyć w ciągłej przestrzeni pamięci, która jest wystarczająco duża, aby ją pomieścić.
Andrew
1
Miałem konkretny przypadek, w którym wszystko, co zrobiłem, to dodawanie i usuwanie oraz zapętlanie jeden po drugim ... tutaj połączona lista była znacznie lepsza niż zwykła lista ...
Peter
26

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.

Andrzej
źródło
1
Pytanie: Przez „dane zapisane w tablicy <lub> 85 000 bajtów” masz na myśli dane według tablicy / listy ELEMENT, prawda? Można zrozumieć, że masz na myśli rozmiar danych całej tablicy ...
Philm
Układa elementy umieszczone sekwencyjnie w pamięci. Tak na tablicę. Wiem o pomyłce w tabeli, później ją naprawię :) (mam nadzieję ...)
Andrew
Przy listach powolnych przy wstawianiu, jeśli lista ma dużo zmian (wiele wstawień / usunięć), pamięć jest zajmowana przez usunięte miejsce, a jeśli tak, to czy to sprawia, że ​​wstawianie „ponownie” jest szybsze?
Rob
18

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,

użytkownik23117
źródło
4
Lista <T> jest oparta na tablicy (T []), a nie na tablicy ArrayList. Wstaw ponownie: zmiana rozmiaru tablicy nie jest problemem (algorytm dublowania oznacza, że ​​przez większość czasu nie musi tego robić): problem polega na tym, że musi najpierw zablokować skopiowanie wszystkich istniejących danych, co zajmuje trochę czas.
Marc Gravell
2
@Marc, „algorytm dublowania” sprawia, że ​​jest to tylko O ​​(logN), ale wciąż jest gorsze niż O (1)
Ilya Ryzhenkov
2
Chodziło mi o to, że to nie zmiana rozmiaru powoduje ból - to kłopot. W najgorszym przypadku, jeśli dodajemy pierwszy (zerowy) element za każdym razem, blit musi za każdym razem przesuwać wszystko.
Marc Gravell
@IlyaRyzhenkov - myślisz o przypadku, w którym Addzawsze znajduje się na końcu istniejącej tablicy. Listjest w tym „wystarczająco dobry”, nawet jeśli nie O (1). Poważny problem występuje, jeśli potrzebujesz wielu Add, które nie są na końcu. Marc podkreśla, że ​​potrzeba przenoszenia istniejących danych za każdym razem, gdy wstawiasz (nie tylko wtedy, gdy konieczna jest zmiana rozmiaru), jest bardziej znaczącym kosztem wydajności List.
ToolmakerSteve,
Problem polega na tym, że teoretyczne notacje Big O nie opowiadają całej historii. W informatyce jest wszystkim, na czym zawsze zależy, ale w prawdziwym świecie jest o wiele więcej powodów do zmartwień.
MattE
11

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

Dr Alrawi
źródło
1
IMO to powinna być odpowiedź. LinkedList są używane, gdy ważne jest zamówienie gwarantowane.
RBaarda
1
@RBaarda: Nie zgadzam się. To zależy od poziomu, o którym mówimy. Poziom algorytmu jest inny niż poziom implementacji maszyny. Do rozważenia prędkości potrzebujesz również tego drugiego. Jak wskazano, tablice są implementowane jako „jedna porcja” pamięci, co jest ograniczeniem, ponieważ może to prowadzić do zmiany rozmiaru i reorganizacji pamięci, szczególnie w przypadku bardzo dużych tablic. Po krótkiej chwili zastanowienia się nad specjalną własną strukturą danych, połączoną listą tablic byłby jeden pomysł na lepszą kontrolę szybkości liniowego wypełniania i uzyskiwania dostępu do bardzo dużych struktur danych.
Philm,
1
@ Philm - Głosowałem za twoim komentarzem, ale chciałbym zauważyć, że opisujesz inny wymóg. Odpowiedź brzmi: lista połączona ma przewagę wydajności w przypadku algorytmów, które wymagają dużej liczby zmian układu elementów. Biorąc to pod uwagę, interpretuję komentarz RBaarda jako odnoszący się do potrzeby dodawania / usuwania elementów przy ciągłym utrzymywaniu danego zamówienia (kryteria sortowania). Więc nie tylko „liniowe wypełnienie”. Biorąc to pod uwagę, Lista przegrywa, ponieważ indeksy są bezużyteczne (zmieniają się za każdym razem, gdy dodasz element gdziekolwiek, ale na końcu).
ToolmakerSteve,
4

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();
}
Tomek
źródło
6
Możesz po prostu użyć, RemoveAllaby usunąć elementy Listbez przenoszenia wielu elementów lub użyć WhereLINQ, aby utworzyć drugą listę. Używanie LinkedListtutaj kończy się jednak znacznie większym zużyciem pamięci niż inne typy kolekcji, a utrata lokalizacji pamięci oznacza, że ​​iteracja będzie zauważalnie wolniejsza, co czyni go nieco gorszym niż a List.
Servy
@Servy, pamiętaj, że odpowiedź @ Tom używa Java. Nie jestem pewien, czy jest RemoveAllodpowiednik w Javie.
Arturo Torres Sánchez
3
@ ArturoTorresSánchez Cóż, pytanie wyraźnie mówi, że chodzi o platformę .NET, dzięki czemu odpowiedź jest o wiele mniej odpowiednia.
Servy
@Servy, powinieneś o tym wspomnieć od samego początku.
Arturo Torres Sánchez
Jeśli RemoveAllnie jest dostępny List, możesz wykonać algorytm „zagęszczania”, który wyglądałby jak pętla Toma, ale z dwoma indeksami i potrzebą przenoszenia elementów, aby były przechowywane pojedynczo w dół w wewnętrznej tablicy listy. Wydajność wynosi O (n), tak samo jak algorytm Toma LinkedList. W obu wersjach dominuje czas na obliczenie klucza HashSet dla łańcuchów. To nie jest dobry przykład zastosowania LinkedList.
ToolmakerSteve,
2

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

Michael Damatov
źródło
2

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).
iliketocode
źródło
1

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).

nawfal
źródło
0

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<>.

Antony Thomas
źródło
6
Nie rozumiem, dlaczego punkt 2 ma sens. Listy połączone są świetne, gdy wykonujesz wiele operacji wstawiania / usuwania na całej liście.
Drew Noakes,
Z uwagi na fakt, że LinkedLists nie są oparte na indeksie, naprawdę musisz przeskanować całą listę w celu wstawienia lub usunięcia, co wiąże się z karą O (n). Z drugiej strony, lista <> cierpi z powodu zmiany rozmiaru tablicy, ale IMO jest lepszą opcją w porównaniu do LinkedLists.
Antony Thomas
1
Nie musisz skanować listy w poszukiwaniu wstawek / usunięć, jeśli śledzisz LinkedListNode<T>obiekty w kodzie. Jeśli możesz to zrobić, jest to o wiele lepsze niż używanie List<T>, szczególnie w przypadku bardzo długich list, w których często występują wstawienia / usunięcia.
Drew Noakes,
Masz na myśli hashtable? W takim przypadku byłby to typowy kompromis czasoprzestrzenny, że każdy programista powinien dokonać wyboru w oparciu o domenę problemową :) Ale tak, to by przyspieszyło.
Antony Thomas
1
@AntonyThomas - Nie, ma na myśli przekazywanie odniesień do węzłów zamiast przekazywania odniesień do elementów . Jeśli wszystko, co masz, to element , zarówno List, jak i LinkedList mają słabą wydajność, ponieważ musisz wyszukiwać. Jeśli myślisz „ale z Listą mogę po prostu przekazać indeks”: jest to ważne tylko wtedy, gdy nigdy nie wstawisz nowego elementu na środku Listy. LinkedList nie ma tego ograniczenia, jeśli trzymasz się węzła (i używasz, node.Valuekiedy chcesz oryginalny element). Więc przepisujesz algorytm do pracy z węzłami, a nie surowymi wartościami.
ToolmakerSteve,
0

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.

Abhishek Kumar Singh
źródło
Pamiętaj, że ta porada dotyczy platformy .NET, a nie Java. W implementacji połączonej listy Java nie masz pojęcia „bieżącego węzła”, więc musisz przeglądać listę dla każdej wstawki.
Jonathan Allen,
Ta odpowiedź jest tylko częściowo poprawna: 2) jeśli elementy są duże, należy uczynić typ elementu Klasą, a nie Strukturą, aby List po prostu zawierał odwołanie. Wtedy rozmiar elementu staje się nieistotny. 3) Deque i kolejka mogą być efektywnie wykonywane na liście, jeśli używasz listy jako „bufora cyklicznego”, zamiast wstawiania lub usuwania na początku. StephenCleary's Deque . 4) częściowo prawdziwe: gdy wiele obiektów, pro LL nie potrzebuje dużej ciągłej pamięci; minusem jest dodatkowa pamięć dla wskaźników węzłów.
ToolmakerSteve,
-2

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.

użytkownik1496062
źródło
3
To pytanie dotyczyło dwóch implementacji języka C #, a nie połączonych list w ogóle.
Jonathan Allen
To samo w każdym języku
użytkownik1496062,
-2

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ść.

Adam Cox
źródło
1
Re oświadczenie, które Dequejest „podobne do listy połączonej, ale z lepszą wydajnością” . Proszę określić, że oświadczenie: Dequejest lepiej niż wydajność LinkedList, dla kodu specyficznego . Po twoim linku widzę, że dwa dni później dowiedziałeś się od Ivana Stoeva, że ​​nie była to nieefektywność LinkedList, ale nieefektywność twojego kodu. (I nawet jeśli byłaby to nieskuteczność LinkedList, nie uzasadniałoby to ogólnego stwierdzenia, że ​​Deque jest bardziej wydajny; tylko w szczególnych przypadkach.)
ToolmakerSteve