W jakich okolicznościach listy połączone są przydatne?

W większości przypadków ludzie próbują korzystać z list połączonych, wydaje mi się to kiepskim (lub bardzo złym) wyborem. Być może warto byłoby zbadać okoliczności, w których połączona lista jest dobrym wyborem struktury danych lub nie.

Idealnie byłoby, gdyby odpowiedzi wyjaśniały kryteria, które należy stosować przy wyborze struktury danych, oraz które struktury danych prawdopodobnie będą działać najlepiej w określonych okolicznościach.

Edycja: Muszę powiedzieć, że jestem pod wrażeniem nie tylko liczby, ale i jakości odpowiedzi. Mogę zaakceptować tylko jedną, ale są jeszcze dwie lub trzy, które muszę powiedzieć, że warto by było zaakceptować, gdyby nie było czegoś lepszego. Tylko kilka osób (zwłaszcza ta, którą ostatecznie zaakceptowałem) wskazało na sytuacje, w których lista połączona zapewniała realną przewagę. Myślę, że Steve Jessop zasługuje na jakąś honorową wzmiankę za wymyślenie nie tylko jednej, ale trzech różnych odpowiedzi, z których wszystkie wydały mi się imponujące. Oczywiście, mimo że został opublikowany tylko jako komentarz, a nie odpowiedź, myślę, że wpis na blogu Neila również jest wart przeczytania - nie tylko pouczający, ale także dość zabawny.

Mogą być przydatne w przypadku współbieżnych struktur danych. (Poniżej znajduje się przykład nierównoczesnego użycia w świecie rzeczywistym - nie byłoby go, gdyby @Neil nie wspomniał o FORTRANIE ;-)

Na przykład ConcurrentDictionary<TKey, TValue>w .NET 4.0 RC użyj połączonych list do łączenia elementów, które mają skrót do tego samego zasobnika.

Podstawową strukturą danych dla ConcurrentStack<T>jest również połączona lista.

ConcurrentStack<T>jest jedną ze struktur danych, które służą jako podstawa nowej puli wątków (z lokalnymi „kolejkami” zaimplementowanymi zasadniczo jako stosy). (Druga główna konstrukcja nośna to ConcurrentQueue<T>.)

Nowa pula wątków z kolei stanowi podstawę do planowania pracy nowej biblioteki równoległej zadań .

Z pewnością mogą się więc przydać - połączona lista jest obecnie jedną z głównych struktur wspierających co najmniej jedną wielką nową technologię.

(Lista pojedynczo połączona stanowi w tych przypadkach przekonujący wybór bez blokad - ale nie bez czekania - ponieważ główne operacje można wykonać za pomocą jednego CAS (+ ponownych prób). Java i .NET - problemu ABA można łatwo uniknąć. Po prostu zawiń elementy, które dodajesz do nowo utworzonych węzłów i nie używaj ponownie tych węzłów - pozwól GC wykonać swoją pracę. Strona dotycząca problemu ABA zapewnia również implementację blokady wolny stos - który faktycznie działa w .Net (& Java) z węzłem (GC-ed) przechowującym elementy.)

Edycja : @Neil: właściwie to, o czym wspomniałeś o FORTRANIE, przypomniało mi, że ten sam rodzaj połączonych list można znaleźć w prawdopodobnie najczęściej używanej i nadużywanej strukturze danych w .NET: zwykłym generycznym .NET Dictionary<TKey, TValue>.

Nie jedna, ale wiele połączonych list jest przechowywanych w tablicy.

• Unika wykonywania wielu małych (de) alokacji przy wstawianiu / usuwaniu.
• Początkowe ładowanie tablicy haszującej jest dość szybkie, ponieważ tablica jest wypełniana sekwencyjnie (gra bardzo dobrze z pamięcią podręczną procesora).
• Nie wspominając już o tym, że łańcuchowa tablica mieszająca jest droga pod względem pamięci - a ta „sztuczka” zmniejsza „rozmiary wskaźnika” o połowę na x64.

Zasadniczo wiele połączonych list jest przechowywanych w tablicy. (po jednym dla każdego użytego zasobnika). Wolna lista węzłów wielokrotnego użytku jest „przeplatana” między nimi (jeśli zostały usunięte). Tablica jest przydzielana na początku / przy ponownym haszowaniu i przechowywane są w niej węzły łańcuchów. Istnieje również wolny wskaźnik - indeks tablicy - który następuje po usunięciach. ;-) A więc - wierz lub nie - technika FORTRAN wciąż istnieje. (... i nigdzie indziej niż w jednej z najczęściej używanych struktur danych .NET ;-).

Połączone listy są bardzo przydatne, gdy musisz wykonać wiele wstawień i usunięć, ale niezbyt wiele wyszukiwania, na liście o dowolnej (nieznanej w czasie kompilacji) długości.

Dzielenie i łączenie list (połączonych dwukierunkowo) jest bardzo wydajne.

Można również łączyć listy połączone - np. Struktury drzewiaste mogą być implementowane jako listy połączone „pionowe” (relacje rodzic / potomek) łączące ze sobą listy połączone w poziomie (rodzeństwo).

Używanie listy opartej na tablicach do tych celów ma poważne ograniczenia:

• Dodanie nowego elementu oznacza, że ​​tablica musi zostać ponownie przydzielona (lub musisz przydzielić więcej miejsca niż potrzebujesz, aby umożliwić przyszły rozwój i zmniejszyć liczbę ponownych alokacji)
• Usunięcie elementów powoduje marnowanie miejsca lub wymaga ponownego przydziału
• wstawianie elementów w dowolnym miejscu poza końcem wiąże się z (prawdopodobnie ponownym przydzieleniem i) skopiowaniem wielu danych w górę o jedną pozycję

Listy połączone są bardzo elastyczne: modyfikując jeden wskaźnik, można dokonać ogromnej zmiany, w przypadku której ta sama operacja byłaby bardzo nieefektywna na liście tablic.

Tablice to struktury danych, z którymi zwykle porównuje się listy połączone.

Zwykle połączone listy są przydatne, gdy trzeba dokonać wielu modyfikacji w samej liście, podczas gdy tablice działają lepiej niż listy przy bezpośrednim dostępie do elementów.

Oto lista operacji, które można wykonać na listach i tablicach, w porównaniu z relatywnym kosztem operacji (n = długość listy / tablicy):

• Dodawanie elementu:
  • na listach wystarczy przydzielić pamięć dla nowego elementu i przekierować wskaźniki. O (1)
  • w przypadku tablic musisz przenieść tablicę. Na)
• Usuwanie elementu
  • na listach po prostu przekierowujesz wskaźniki. O (1).
  • na tablicach spędzasz O (n) czasu na przemieszczanie tablicy, jeśli element do usunięcia nie jest pierwszym lub ostatnim elementem tablicy; w przeciwnym razie możesz po prostu przenieść wskaźnik na początek tablicy lub zmniejszyć długość tablicy
• Uzyskanie elementu na znanej pozycji:
  • na listach musisz przejść listę od pierwszego elementu do elementu na określonej pozycji. Najgorszy przypadek: O (n)
  • w tablicach można uzyskać natychmiastowy dostęp do elementu. O (1)

Jest to porównanie tych dwóch popularnych i podstawowych struktur danych na bardzo niskim poziomie i widać, że listy działają lepiej w sytuacjach, w których trzeba samodzielnie dokonać wielu modyfikacji listy (usunięcie lub dodanie elementów). Z drugiej strony tablice działają lepiej niż listy, gdy musisz uzyskać bezpośredni dostęp do elementów tablicy.

Z punktu widzenia alokacji pamięci listy są lepsze, ponieważ nie ma potrzeby umieszczania wszystkich elementów obok siebie. Z drugiej strony istnieje (mały) narzut związany z przechowywaniem wskaźników do następnego (lub nawet do poprzedniego) elementu.

Znajomość tych różnic jest ważna dla programistów, aby mogli wybierać między listami i tablicami w swoich implementacjach.

Zauważ, że jest to porównanie list i tablic. Istnieją dobre rozwiązania zgłoszonych tutaj problemów (np .: SkipLists, Dynamic Arrays itp.). W tej odpowiedzi uwzględniłem podstawową strukturę danych, o której powinien wiedzieć każdy programista.

Lista pojedynczo połączona jest dobrym wyborem dla listy swobodnej w alokatorze komórek lub puli obiektów:

1. Potrzebujesz tylko stosu, więc lista połączona pojedynczo jest wystarczająca.
2. Wszystko jest już podzielone na węzły. Nie ma narzutu alokacji dla natrętnego węzła listy, pod warunkiem, że komórki są wystarczająco duże, aby zawierać wskaźnik.
3. Wektor lub deque nakładałby narzut jednego wskaźnika na blok. Jest to istotne, biorąc pod uwagę, że przy pierwszym tworzeniu sterty wszystkie komórki są wolne, więc jest to koszt początkowy. W najgorszym przypadku podwaja zapotrzebowanie na pamięć na komórkę.

Lista podwójnie połączona jest dobrym wyborem do zdefiniowania kolejności haszmapy, która również definiuje kolejność elementów (LinkedHashMap w Javie), zwłaszcza gdy są uporządkowane według ostatniego dostępu:

1. Większy narzut pamięci niż skojarzony wektor lub deque (2 wskaźniki zamiast 1), ale lepsza wydajność wstawiania / usuwania.
2. Brak narzutu alokacji, ponieważ i tak potrzebujesz węzła dla wpisu skrótu.
3. Lokalność odniesienia nie jest dodatkowym problemem w porównaniu z wektorem lub deque wskaźników, ponieważ każdy obiekt musiałby zostać wciągnięty do pamięci tak czy inaczej.

Jasne, możesz spierać się o to, czy pamięć podręczna LRU jest dobrym pomysłem w porównaniu z czymś bardziej wyrafinowanym i dostrajalnym, ale jeśli masz taką, jest to całkiem przyzwoita implementacja. Nie chcesz wykonywać operacji usuwania ze środka i dodawania na końcu na wektorze lub deque przy każdym dostępie do odczytu, ale przeniesienie węzła do końca jest zwykle w porządku.

Listy połączone są jednym z naturalnych wyborów, gdy nie możesz kontrolować miejsca przechowywania danych, ale nadal musisz w jakiś sposób przechodzić z jednego obiektu do drugiego.

Na przykład podczas implementowania śledzenia pamięci w C ++ (zastępowanie nowych / usuwanych) albo potrzebujesz jakiejś struktury danych kontrolnych, która śledzi, które wskaźniki zostały zwolnione, co musisz w pełni zaimplementować samodzielnie. Alternatywą jest nadmierna alokacja i dodanie połączonej listy na początku każdego fragmentu danych.

Ponieważ zawsze od razu wiesz, gdzie jesteś na liście, gdy wywoływana jest funkcja delete, możesz łatwo zrezygnować z pamięci w O (1). Również dodanie nowego kawałka, który właśnie został pobrany, znajduje się w O (1). Spacerowanie po liście jest bardzo rzadko potrzebne w tym przypadku, więc koszt O (n) nie stanowi tutaj problemu (chodzenie po strukturze i tak wynosi O (n)).

Są przydatne, gdy potrzebujesz szybkiego pchania, popychania i obracania, i nie ma nic przeciwko indeksowaniu O (n).

Listy połączone pojedynczo są oczywistą implementacją wspólnego typu danych „lista” w funkcjonalnych językach programowania:

1. Dodawanie do głowy jest szybkie (append (list x) (L))i (append (list y) (L))może udostępniać prawie wszystkie dane. Nie ma potrzeby kopiowania przy zapisie w języku bez zapisu. Programiści funkcyjni wiedzą, jak to wykorzystać.
2. Dodawanie do końca jest niestety powolne, ale tak samo byłoby z każdą inną implementacją.

Dla porównania, wektor lub deque zazwyczaj byłby powolny do dodania na każdym końcu, wymagając (przynajmniej w moim przykładzie dwóch odrębnych dołączeń), aby skopiować całą listę (wektor) lub blok indeksu i blok danych dołączane do (deque). Właściwie może być tam coś do powiedzenia na temat deque na dużych listach, które z jakiegoś powodu muszą być dodawane na końcu, nie jestem wystarczająco poinformowany o programowaniu funkcjonalnym, aby to ocenić.

Jednym z przykładów dobrego użycia połączonej listy jest sytuacja, w której elementy listy są bardzo duże, tj. na tyle duże, że tylko jeden lub dwa mogą zmieścić się w pamięci podręcznej procesora w tym samym czasie. W tym momencie korzyść, jaką mają ciągłe kontenery blokowe, takie jak wektory lub tablice dla iteracji, jest mniej lub bardziej niwelowana, a przewaga wydajności może być możliwa, jeśli wiele wstawień i usunięć ma miejsce w czasie rzeczywistym.

Z mojego doświadczenia, wdrażam rzadkie matryce i stosy fibonacciego. Listy połączone zapewniają większą kontrolę nad ogólną strukturą takich struktur danych. Chociaż nie jestem pewien, czy rzadkie macierze najlepiej zaimplementować za pomocą połączonych list - prawdopodobnie jest lepszy sposób, ale naprawdę pomogło to poznać tajniki rzadkich macierzy przy użyciu połączonych list w undergrad CS :)

Istnieją dwie komplementarne operacje, które są trywialnie O (1) na listach i bardzo trudne do zaimplementowania w O (1) w innych strukturach danych - usuwanie i wstawianie elementu z dowolnej pozycji, przy założeniu, że musisz zachować kolejność elementów.

Mapy skrótów mogą oczywiście wykonywać wstawianie i usuwanie w O (1), ale wtedy nie można iterować po elementach w kolejności.

Biorąc pod uwagę powyższy fakt, mapę skrótów można połączyć z połączoną listą, aby utworzyć sprytną pamięć podręczną LRU: Mapa, która przechowuje stałą liczbę par klucz-wartość i usuwa ostatnio używany klucz, aby zrobić miejsce na nowe.

Wpisy na mapie skrótów muszą mieć wskaźniki do połączonych węzłów list. Podczas uzyskiwania dostępu do mapy skrótów węzeł połączonej listy jest odłączany od swojej bieżącej pozycji i przenoszony na początek listy (O (1), tak dla list połączonych!). Gdy zachodzi potrzeba usunięcia ostatnio używanego elementu, element z końca listy musi zostać usunięty (ponownie O (1) zakładając, że trzymasz wskaźnik do węzła końcowego) wraz z powiązanym wpisem mapy skrótu (więc linki zwrotne z lista do mapy skrótów jest konieczna).

Należy wziąć pod uwagę, że lista połączona może być bardzo przydatna w implementacji stylu opartego na projektowaniu opartym na domenie systemu, który zawiera części, które są powiązane z powtórzeniami.

Przykładem, który przychodzi na myśl, może być modelowanie wiszącego łańcucha. Jeśli chcesz wiedzieć, jakie było napięcie w jakimś konkretnym łączu, twój interfejs mógłby zawierać getter dla „pozornej” wagi. Wdrożenie którego obejmowałoby łącze z pytaniem o jego pozorną wagę, a następnie dodanie jego własnej wagi do wyniku. W ten sposób cała długość do samego dołu byłaby oceniana jednym wywołaniem od klienta sieci.

Będąc zwolennikiem kodu, który czyta się jak język naturalny, podoba mi się, jak pozwoliłoby to programistom zapytać ogniwo łańcucha, ile ma on wagi. Zachowuje również zainteresowanie obliczaniem tych dzieci właściwości w granicach implementacji łącza, eliminując potrzebę korzystania z usługi obliczania wagi łańcucha ”.

Jednym z najbardziej przydatnych przypadków, które znajduję w przypadku list połączonych działających w dziedzinach o krytycznym znaczeniu dla wydajności, takich jak przetwarzanie siatki i obrazów, silniki fizyczne i śledzenie promieni, jest użycie list połączonych, które faktycznie poprawia lokalność odniesienia i zmniejsza alokacje sterty, a czasami nawet zmniejsza użycie pamięci w porównaniu z proste alternatywy.

To może wydawać się kompletnym oksymoronem, który połączone listy mogą zrobić wszystko, ponieważ są znane z tego, że często robią coś przeciwnego, ale mają unikalną właściwość, ponieważ każdy węzeł listy ma ustalony rozmiar i wymagania dotyczące wyrównania, które możemy wykorzystać, aby umożliwić były przechowywane w sposób ciągły i usuwane w stałym czasie w sposób, w jaki rzeczy o zmiennej wielkości nie mogą.

W rezultacie weźmy przypadek, w którym chcemy zrobić analogiczny odpowiednik przechowywania sekwencji o zmiennej długości, która zawiera milion zagnieżdżonych podsekwencji o zmiennej długości. Konkretnym przykładem jest indeksowana siatka przechowująca milion wielokątów (niektóre trójkąty, niektóre czworokąty, niektóre pięciokąty, niektóre sześciokąty itp.), A czasami wielokąty są usuwane z dowolnego miejsca w siatce, a czasami są przebudowywane, aby wstawić wierzchołek do istniejącego wielokąta lub usuń jeden. W takim przypadku, jeśli przechowujemy milion malutkich std::vectors, w końcu mamy do czynienia z alokacją sterty dla każdego pojedynczego wektora, a także z potencjalnie wybuchowym użyciem pamięci. Milion malutkichSmallVectors może nie cierpieć z powodu tego problemu tak bardzo w typowych przypadkach, ale wtedy ich wstępnie przydzielony bufor, który nie jest oddzielnie przydzielany na stertę, może nadal powodować gwałtowne zużycie pamięci.

Problem polega na tym, że milion std::vectorinstancji próbowałoby przechowywać milion rzeczy o zmiennej długości. Rzeczy o zmiennej długości zwykle wymagają alokacji sterty, ponieważ nie mogą być bardzo efektywnie przechowywane w sposób ciągły i usuwane w stałym czasie (przynajmniej w prosty sposób bez bardzo złożonego alokatora), jeśli nie przechowują swojej zawartości gdzie indziej na stercie.

Jeśli zamiast tego zrobimy to:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

... następnie radykalnie zmniejszyliśmy liczbę alokacji sterty i chybień w pamięci podręcznej. Zamiast wymagać alokacji sterty i potencjalnie obowiązkowych błędów pamięci podręcznej dla każdego pojedynczego wielokąta, do którego mamy dostęp, teraz wymagamy alokacji sterty tylko wtedy, gdy jeden z dwóch wektorów przechowywanych w całej siatce przekracza ich pojemność (zamortyzowany koszt). I chociaż krok w kierunku przejścia z jednego wierzchołka do następnego może nadal powodować udział chybień w pamięci podręcznej, wciąż jest to mniejszy niż w przypadku, gdy każdy pojedynczy wielokąt przechowuje oddzielną tablicę dynamiczną, ponieważ węzły są przechowywane w sposób ciągły i istnieje prawdopodobieństwo, że sąsiedni wierzchołek może być dostępne przed eksmisją (zwłaszcza biorąc pod uwagę, że wiele wielokątów doda swoje wierzchołki jednocześnie, co sprawia, że ​​lwia część wierzchołków wielokątów jest idealnie przylegająca).

Oto kolejny przykład:

... gdzie komórki siatki są wykorzystywane do przyspieszania zderzeń cząstek-cząsteczek, powiedzmy, 16 milionów cząstek poruszających się w każdej klatce. W tym przykładzie z siatką cząstek, używając połączonych list, możemy przenieść cząstkę z jednej komórki siatki do drugiej, zmieniając tylko 3 wskaźniki. Wymazywanie z wektora i przesuwanie z powrotem do innego może być znacznie droższe i wprowadzić więcej alokacji sterty. Połączone listy również zmniejszają pamięć komórki do 32 bitów. Wektor, w zależności od implementacji, może wstępnie przydzielić swoją tablicę dynamiczną do punktu, w którym może zająć 32 bajty dla pustego wektora. Jeśli mamy około miliona komórek siatki, to spora różnica.

... i tutaj uważam, że listy z linkami są obecnie najbardziej przydatne, a szczególnie uważam, że odmiana "indeksowanych list połączonych" jest przydatna, ponieważ indeksy 32-bitowe zmniejszają o połowę wymagania dotyczące pamięci łączy na maszynach 64-bitowych i sugerują, że węzły są przechowywane w postaci ciągłej w tablicy.

Często łączę je również z indeksowanymi bezpłatnymi listami, aby umożliwić ciągłe usuwanie i wstawianie w dowolnym miejscu:

W takim przypadku nextindeks wskazuje następny wolny indeks, jeśli węzeł został usunięty, lub następny używany indeks, jeśli węzeł nie został usunięty.

I to jest najważniejszy przypadek użycia, jaki znajduję w przypadku list połączonych w dzisiejszych czasach. Kiedy chcemy przechowywać, powiedzmy, milion pod-sekwencji o zmiennej długości, średnio 4 elementy każda (ale czasami elementy są usuwane i dodawane do jednej z tych sekwencji), połączona lista pozwala nam przechowywać 4 miliony połączone węzły list sąsiadująco zamiast 1 miliona kontenerów, z których każdy jest indywidualnie przydzielony na stertę: jeden gigantyczny wektor, tj. nie milion małych.

W przeszłości korzystałem z list połączonych (nawet list podwójnie połączonych) w aplikacji C / C ++. To było przed .NET, a nawet STL.

Prawdopodobnie nie użyłbym teraz połączonej listy w języku .NET, ponieważ cały potrzebny kod przechodzenia jest dostarczany za pośrednictwem metod rozszerzenia Linq.