Jakie są konkretne zasady korzystania z listy połączonej zamiast tablicy?

18

Połączonej listy można użyć, gdy chcesz tanie wstawiania i usuwania elementów i gdy nie ma znaczenia, że ​​elementy nie są obok siebie w pamięci.

Jest to bardzo abstrakcyjne i chciałbym konkretne wyjaśnienie, dlaczego powinna być używana lista połączona, a nie tablica. Nie mam dużego doświadczenia w programowaniu, więc nie mam dużego doświadczenia (jeśli w ogóle) w świecie rzeczywistym.

data-structures linked-list po prawej stronie
źródło
3
Szczerze mówiąc, nie sądzę, że przykłady będą dla ciebie tak ważne, dopóki nie będziesz mieć doświadczenia w pisaniu czegoś, a potem w odczuciu wpływu zmiany struktur danych na kod. Spróbuj napisać coś, co Cię interesuje, i dowiedz się, które struktury danych i kontenery są najlepiej dopasowane, lub spójrz na istniejący kod i zastanów się, dlaczego każdy kontener został wybrany i jaki efekt miałaby jego zmiana.
Bezużyteczne
Po prostu nie sądzę, aby możliwe było komunikowanie kompromisów i skutków ubocznych wyboru struktury danych do (niedoświadczonego) PO bez znacznie dłuższego przykładu, niż jest to uzasadnione. Przykłady podane jako odpowiedzi są w porządku i odpowiadają na zadane pytanie, ale nie stanowią (jak czytam) dorozumianej prośby o rzeczywiste zrozumienie.
Bezużyteczne

Odpowiedzi:

37

Oto coś częściowo pomiędzy przykładem a analogią. Masz kilka spraw do załatwienia, więc weź kawałek papieru i napisz:

  • Bank
  • artykuły spożywcze
  • zostawić pranie chemiczne

Wtedy pamiętasz, że musisz też kupić znaczki. Ze względu na położenie geograficzne twojego miasta musisz to zrobić po banku. Możesz skopiować całą listę na nową kartkę papieru:

  • Bank
  • Znaczki
  • artykuły spożywcze
  • zostawić pranie chemiczne

lub możesz bazgroić na tym, który miałeś:

  • bank ....... STAMPS
  • artykuły spożywcze
  • zostawić pranie chemiczne

Myśląc o innych sprawach, możesz napisać je na dole listy, ale ze strzałkami przypominającymi sobie, w jakiej kolejności je wykonać. To jest lista połączona. Jest to szybsze i łatwiejsze niż kopiowanie całej listy za każdym razem, gdy coś dodajesz.

Potem telefon dzwoni, gdy jesteś w banku „hej, dostałem znaczki, nie odbieraj więcej”. Po prostu wykreślasz STAMPS z listy, nie przepisujesz zupełnie nowego bez STAMPS.

Teraz możesz faktycznie zaimplementować listę zleceń w kodzie (być może aplikacja, która porządkuje twoje zlecenia w oparciu o twoją geografię) i istnieje uzasadniona szansa, że ​​faktycznie użyjesz do tego listy połączonej w kodzie. Chcesz dodawać i usuwać wiele elementów, porządkować sprawy, ale nie chcesz kopiować całej listy po każdym wstawieniu lub usunięciu.

Kate Gregory
źródło
3
Według Bjarne Stroustrup kopiowanie całej listy przez LL może nie być tak szybkie i łatwe, jak myślisz .
Dennis
@Dennis tak, wiem dzięki semantyce ruchów. Jednak nie dotyczy to wszystkich języków, więc przykład jest ważny.
Kate Gregory
1
@KateGregory jest wystarczająco uczciwa, ale nadal warto zauważyć, że „podstawowe” struktury danych są często lepsze niż fajne struktury danych, o których dowiadujemy się w szkole (lub gdzie indziej). Nie chcę, aby nowe stopnie naukowe używały wszędzie LL, ponieważ jest to teoretycznie właściwe, a jednocześnie realistycznie może być złym wyborem. Korzystanie z odpowiedniej struktury danych jest ważne, a czasem ludzie ją komplikują. Nieco spokrewniony jest wykład Jonathana Blow'a (twórcy „Braid”) na temat struktur danych .
Dennis
1
@Ray: Powiązana lista może przewyższać strukturę drzewa, jeśli spodziewasz się, że będzie rzędu 4 elementów, a porównania są stosunkowo tanie. Nie wiem dokładnie, gdzie jest granica, gdzie tak nie jest. Również struktura drzewa wymaga sortowania danych, a struktura listy pozwala zachować porządek wstawiania (lub dowolną dowolną kolejność).
David Stone
2
Nie sądzę, że ta analogia jest bardzo dokładna. Jako ludzie możemy (przynajmniej dla tak krótkiej listy) znaleźć element w O (1). Ale jeśli chcesz wykonać losowe wstawianie na połączonej liście, będziesz musiał przejść średnio o połowę elementów, co kosztuje O (n) tylko, aby znaleźć pozycję, w której chcesz wstawić. Rzeczywista wstawka kosztuje wtedy tylko O ​​(1), ale w przypadku macierzy twój koszt to również „tylko” O (n). Powodem jest więc nie tylko semantyka ruchu, ale także algorytm. Stały czynnik ukryty przez big-O jest jednak znacznie większy dla listy polubionych, z powodu nieciągłego dostępu do pamięci.
5gon12eder
18
  • Tabele skrótów, które wykorzystują łańcuchy do rozwiązywania kolizji skrótów, zazwyczaj mają jedną połączoną listę dla każdego segmentu dla elementów w tym segmencie.
  • Proste alokatory pamięci używają wolnej listy nieużywanych regionów pamięci, w zasadzie połączonej listy ze wskaźnikiem listy w samej wolnej pamięci
  • W systemie plików FAT metadane dużego pliku są zorganizowane jako połączona lista wpisów FAT.
Michael Borgwardt
źródło
12

„Stos wywołań” w języku C jest zaimplementowany jako lista połączona w binarnych interfejsach API x86 (i większości innych).

Oznacza to, że wywoływanie procedur w języku C odbywa się zgodnie z dyscypliną „pierwszy na wejściu”. Wynik wykonywania (ewentualnie rekurencyjnych) wywołań funkcji jest nazywany „stosem wywołań”, a czasem nawet „stosem”.

CALLInstrukcji x86 kończy się implmenting połączonej listy przy użyciu „stosu wywołań”. CALLInstrukcja wypycha zawartość% EIP rejestru, adres instrukcji po tym CALLna pamięć stosu. Prolog nazywany fukcją wypycha zawartość rejestru% EBP, najniższego adresu zmiennych lokalnych w funkcji wywołującej, do pamięci stosu. Następnie wywoływany prolog funkcji ustawia% EBP na podstawie stosu bieżącej funkcji.

Oznacza to, że% EBP jest wskaźnikiem do miejsca w pamięci, które przechowuje adres wartości% EBP funkcji wywołującej. To nic innego jak połączona lista, zaimplementowana częściowo w sprzęcie poprzez CALL.

O ile jest to dobre, procesory x86 implementują wywołania funkcji, zwłaszcza wywołania funkcji, w których funkcja ma własną kopię argumentów i zmienne lokalne dla funkcji. Każde wywołanie funkcji przesuwa pewne informacje na „stosie wywołań”, który pozwala procesorowi wybrać miejsce, w którym zostało przerwane w funkcji wywołującej, bez ingerencji wywołanej funkcji lub funkcji wywołującej.

Bruce Ediger
źródło
3

Połączonej listy można użyć do zaimplementowania kolejki komunikatów.

Kolejka komunikatów to struktura, w której przechowujemy informacje o zdarzeniach do późniejszego przetworzenia. Na przykład, gdy użytkownik naciska klawisz lub porusza myszą, jest to zdarzenie. Aplikacja może być zajęta w momencie wystąpienia zdarzenia, więc nie można oczekiwać, że przetworzy to zdarzenie dokładnie w momencie jego wystąpienia. Tak więc zdarzenie jest umieszczane w kolejce komunikatów (informacja o tym, który klawisz został naciśnięty lub gdzie mysz się poruszyła), a gdy aplikacja ma trochę czasu, sprawdza kolejkę komunikatów, pobiera z niej zdarzenia i przetwarza im. (Dzieje się tak w ciągu milisekund, więc nie jest to zauważalne).

Ze scenariusza użytkowania, który właśnie opisałem, powinno być oczywiste, że nigdy nie zależy nam na losowym dostępie do zdarzeń przechowywanych w kolejce komunikatów; zależy nam tylko na tym, aby móc przechowywać w nim wiadomości i je odzyskiwać. Dlatego sensowne jest użycie połączonej listy, która zapewnia optymalny czas wstawiania / usuwania.

(Nie wtrącaj się, aby wskazać, że kolejka komunikatów jest prawdopodobnie, lub bardziej prawdopodobna lub prawie tak samo prawdopodobna, zaimplementowana przy użyciu okrągłej listy tablic; jest to szczegół techniczny i ma ograniczenie: możesz tylko przechowywać ograniczona liczba wiadomości w nim).

Mike Nakis
źródło