Po omówieniu tablic w poprzedniej historii , tym razem przyjrzymy się drugiemu typowi struktury danych w naszej serii, czyli połączonym listom.

Listy połączone: koncepcje

# Co to jest wskaźnik?

Zanim przejdziemy do świata połączonych list, zrozumienie pojęcia wskaźników jest trywialne. Jeśli po raz pierwszy słyszysz o tym określeniu, nie daj się zastraszyć. Koncepcja jest bardzo prosta.

Mówiąc prościej, wskaźnik jest po prostu zmienną, która zawiera odniesienie do innej zmiennej. W rzeczywistości na poziomie pamięci wskaźnik przechowuje adres w pamięci maszyny do zmiennej.

# Co to są połączone listy?

Listy połączone nie różnią się od tablic sposobem ułożenia elementów. W rzeczywistości są one uważane za liniową strukturę danych. Jednak w przeciwieństwie do tablic, alokacja pamięci dla elementów na liście nie jest ciągła. Tak więc każdy element na liście niekoniecznie musi mieć sąsiadującą lokalizację pamięci z następnym.

Każdy element na liście jest nazywany „ węzłem ”. Węzeł zawiera pole danych i pole wskazujące na następny węzeł poprzez jego położenie w pamięci. W naszym przykładzie drugi węzeł przechowuje dane „ b ” i wskazuje następny węzeł w miejscu pamięci „ 7 ”.

Pierwszy węzeł na połączonej liście nazywany jest „ głową ” i służy jako punkt wejścia. Z drugiej strony ostatni węzeł wskazuje na wartość null i jest często nazywany „ ogonem ”.

# Listy pojedynczo vs podwójnie połączone

W powyższym przykładzie zilustrowaliśmy pojedynczo połączoną listę. Przechodzenie w tego rodzaju połączonej liście odbywa się w jeden sposób, ponieważ każdy węzeł ma tylko pole wskazujące następny węzeł.

Jednak w liście podwójnie połączonej każdy węzeł zawiera oprócz danych dwa wskaźniki, jeden dla następnego węzła, a drugi dla poprzedniego. Dlatego przechodzenie na liście podwójnie połączonej jest dwukierunkowe. Innymi słowy, z bieżącego węzła n można uzyskać dostęp do węzła n-1 (poprzedniego) i węzła n+1 (następnego).

# Dlaczego miałbyś używać połączonych list?

1. Wstawianie i usuwanie Stały czas…

Jeśli więc bardziej interesuje Cię wstawianie i usuwanie elementów w celu rozwiązania dowolnego problemu, prawdopodobnie możesz rozważyć użycie połączonych list.

2. Nigdy więcej marnowania pamięci…

Fakt, że lokalizacja pamięci dla połączonej listy odbywa się w sposób nieciągły, daje im przewagę nad tablicami. Pamięć jest przydzielana dynamicznie w razie potrzeby. Dlatego nie ma miejsca na marnowanie pamięci.

3. U podstaw innych struktur danych…

Połączone listy mogą służyć do konstruowania bardziej złożonych struktur danych, takich jak drzewa i wykresy.

Listy połączone: Implementacja w JavaScript

Niektóre języki programowania mają wbudowane połączone listy, inne nie. W JavaScript nie ma czegoś takiego jak połączone listy, więc musimy sami je zaimplementować.

Zróbmy to…

Jestem pewien, że nie będziesz potrzebować mojej pomocy, aby zrozumieć ten prosty fragment kodu — i tak skorzystaj z sekcji komentarzy, aby uzyskać pomoc. Zanim jednak zakończymy ten artykuł, chciałbym coś podkreślić…

Jeśli spojrzysz wstecz na wykres złożoności czasowej, który widzieliśmy tutaj wcześniej , zauważysz, że mówi on, że mówi się, że złożoność czasowa dla wstawiania i usuwania wynosi O(1) . Jeśli jednak spojrzysz na powyższy fragment kodu, zobaczysz, że złożoność czasowa insertAt() wynosi O(n) . Jak to się dzieje?

Należy wyraźnie zaznaczyć, że na wykresie oznaczają one samo wstawienie w zadany punkt (wskaźnik). Odpowiednikiem powyższej próbki kodu jest metoda insert() .

I tak! W przypadku tablic to inna historia, ponieważ wstawienie w danej pozycji może wymagać przesunięcia tablicy. Dlatego złożoność czasowa wstawiania i usuwania w tablicach wynosi O(n) .

Rozumiem? Chłodny.

Połączone listy: teraz Twoja kolej…

# Zadanie pierwsze

Użyj preferowanego języka programowania, aby zaimplementować brakującą metodę remove() w powyższym fragmencie kodu.

# Zadanie drugie

Potrzebujemy implementacji od podstaw list podwójnie połączonych w preferowanym przez Ciebie języku programowania. Czy możesz to dla nas zrobić?

Poczekaj chwilę, proszę! Zanim wyruszymy, jeśli chcesz, połączmy się…

• Na YouTubie
• Na Linkedinie
• na Twitterze