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

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