W 2009 roku rzuciłem sobie wyzwanie, aby pisać jeden post na blogu tygodniowo przez cały rok. Czytałem, że najlepszym sposobem na zdobycie większego ruchu na blogu było pisanie postów konsekwentnie. Jeden post na tydzień wydawał się realistycznym celem ze względu na wszystkie pomysły na artykuły, które miałem, ale okazało się, że brakowało mi 52 pomysłów. Przekopałem się przez kilka w połowie napisanych rozdziałów, które ostatecznie miały stać się Profesjonalnym JavaScriptem i znalazłem wiele materiałów na klasyczne tematy z dziedziny informatyki, w tym struktury danych i algorytmy. Wziąłem ten materiał i przekształciłem go w kilka postów w 2009 i (i kilka w 2012), i otrzymałem wiele pozytywnych opinii na ich temat.

Teraz, w dziesięcioletnią rocznicę tych postów, postanowiłem zaktualizować, ponownie opublikować i rozwinąć je przy użyciu JavaScript w 2019 roku. To było interesujące, aby zobaczyć, co się zmieniło, a co nie, i mam nadzieję, że je polubisz.

Co to jest połączona lista?

Połączona lista jest strukturą danych, która przechowuje wiele wartości w sposób liniowy. Każda wartość w połączonej liście jest zawarta w swoim własnym węźle, obiekcie, który zawiera dane wraz z łączem do następnego węzła na liście. Łącze jest wskaźnikiem do innego obiektu węzła lub null, jeśli nie ma następnego węzła. Jeżeli każdy węzeł posiada tylko jeden wskaźnik do innego węzła (najczęściej nazywany next) to lista jest uważana za singly linked list (lub po prostu linked list) natomiast jeżeli każdy węzeł posiada dwa linki (zazwyczaj previous i next) to jest uważana za doublely linked list. W tym poście skupiam się na listach pojedynczo połączonych.

Dlaczego używać listy połączonej?

Podstawową zaletą list połączonych jest to, że mogą one zawierać dowolną liczbę wartości przy jednoczesnym użyciu tylko ilości pamięci niezbędnej dla tych wartości. Zachowanie pamięci było bardzo ważne na starszych komputerach, gdzie pamięć była rzadka. W tamtych czasach, wbudowana tablica w C wymagała określenia, ile elementów może zawierać tablica, a program rezerwował tę ilość pamięci. Zarezerwowanie tej pamięci oznaczało, że nie mogła być ona użyta przez resztę programu lub inne programy działające w tym samym czasie, nawet jeśli pamięć nigdy nie została zapełniona. Na maszynach ubogich w pamięć można było łatwo wyczerpać dostępną pamięć przy użyciu tablic. Listy połączone zostały stworzone, aby obejść ten problem.

Chociaż pierwotnie przeznaczone do lepszego zarządzania pamięcią, listy połączone stały się również popularne, gdy programiści nie wiedzieli, ile elementów tablica będzie ostatecznie zawierać. O wiele łatwiej było użyć listy połączonej i dodać wartości w razie potrzeby, niż dokładnie odgadnąć maksymalną liczbę wartości, które tablica może zawierać. Jako takie, połączone listy są często używane jako podstawa wbudowanych struktur danych w różnych językach programowania.

Wbudowany typ JavaScript Array nie jest zaimplementowany jako połączona lista, chociaż jego rozmiar jest dynamiczny i zawsze jest najlepszą opcją na początek. Możesz przejść całą swoją karierę bez potrzeby używania listy połączonej w JavaScript, ale listy połączone są nadal dobrym sposobem na naukę o tworzeniu własnych struktur danych.

Konstrukcja listy połączonej

Najważniejszą częścią listy połączonej jest jej struktura węzłów. Każdy węzeł musi zawierać pewne dane i wskaźnik do następnego węzła na liście. Oto prosta reprezentacja w JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; }}

W klasie LinkedListNode właściwość data zawiera wartość, którą powinien przechowywać element listy połączonej, a właściwość next jest wskaźnikiem do następnego elementu listy. Właściwość next zaczyna się jako null, ponieważ nie znasz jeszcze następnego węzła. Następnie można utworzyć listę połączoną za pomocą klasy LinkedListNode w następujący sposób:

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

Pierwszy węzeł na liście połączonej jest zwykle nazywany głową, więc identyfikator head w tym przykładzie reprezentuje pierwszy węzeł. Drugi węzeł jest tworzony i przypisywany do head.next, aby utworzyć listę z dwoma elementami. Trzeci węzeł jest dodawany przez przypisanie go do head.next.next, który jest wskaźnikiem next drugiego węzła na liście. Wskaźnikiem next trzeciego węzła na liście pozostaje null. Poniższy obrazek przedstawia wynikową strukturę danych.

Struktura listy połączonej pozwala na przemierzanie wszystkich danych poprzez śledzenie wskaźnika next na każdym węźle. Oto prosty przykład, w jaki sposób przemierzać połączoną listę i wypisywać każdą wartość na konsolę:

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

Ten kod używa zmiennej current jako wskaźnika, który porusza się po połączonej liście. Zmienna current jest inicjalizowana na nagłówek listy, a pętla while jest kontynuowana, dopóki current nie będzie null. Wewnątrz pętli wypisywana jest wartość przechowywana w węźle current, a następnie wskaźnik next jest śledzony do następnego węzła.

Większość operacji na listach połączonych używa tego algorytmu traversal lub czegoś podobnego, więc zrozumienie tego algorytmu jest ważne dla zrozumienia list połączonych w ogóle.

Klasa LinkedList

Gdybyś pisał listę połączoną w C, mógłbyś zatrzymać się w tym punkcie i uznać swoje zadanie za zakończone (chociaż używałbyś struct zamiast klasy do reprezentowania każdego węzła). Jednak w językach zorientowanych obiektowo, takich jak JavaScript, bardziej zwyczajowe jest tworzenie klasy w celu enkapsulacji tej funkcjonalności. Oto prosty przykład:

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

Klasa LinkedList reprezentuje listę połączoną i będzie zawierać metody do interakcji z danymi, które zawiera. Jedyną właściwością jest właściwość symbolu o nazwie head, która będzie zawierać wskaźnik do pierwszego węzła na liście. Właściwość symbol jest używana zamiast właściwości string, aby było jasne, że ta właściwość nie jest przeznaczona do modyfikowania poza klasą.

Dodawanie nowych danych do listy

Dodawanie elementu do listy połączonej wymaga przejścia przez strukturę w celu znalezienia właściwej lokalizacji, utworzenia nowego węzła i wstawienia go na miejsce. Jedynym szczególnym przypadkiem jest sytuacja, gdy lista jest pusta, w którym to przypadku po prostu tworzysz nowy węzeł i przypisujesz go do head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

Metoda add() przyjmuje pojedynczy argument, dowolny fragment danych, i dodaje go na koniec listy. Jeśli lista jest pusta (this jest null), to przypisujemy this równy nowemu węzłowi. Jeśli lista nie jest pusta, to musisz przemierzyć już istniejącą listę, aby znaleźć ostatni węzeł. Trawersowanie odbywa się w pętli while, która zaczyna się od this i podąża za next odnośnikami każdego węzła, aż do znalezienia ostatniego węzła. Ostatni węzeł ma właściwość next równą null, więc ważne jest, aby zatrzymać traversal w tym punkcie, a nie gdy current jest null (jak w poprzedniej sekcji). Następnie możesz przypisać nowy węzeł do tej next właściwości, aby dodać dane do listy.

Złożoność metody add() wynosi O(n), ponieważ musisz przemierzyć całą listę, aby znaleźć miejsce do wstawienia nowego węzła. Możesz zredukować tę złożoność do O(1), śledząc koniec listy (zwykle nazywany ogonem) oprócz głowy, co pozwala na natychmiastowe wstawienie nowego węzła w odpowiednim miejscu.

Pobieranie danych z listy

Listy połączone nie pozwalają na losowy dostęp do jej zawartości, ale nadal możesz pobierać dane w dowolnej pozycji, przemierzając listę i zwracając dane. Aby to zrobić, dodasz metodę get(), która akceptuje indeks zerowy danych do pobrania, jak poniżej:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

Metoda get() najpierw sprawdza, czy index jest wartością dodatnią, w przeciwnym razie zwraca undefined. Zmienna i jest używana do śledzenia, jak głęboko traversal wszedł na listę. Sama pętla jest tą samą podstawową operacją, którą widziałeś wcześniej, z dodanym warunkiem, że pętla powinna zakończyć się, gdy i jest równe index. Oznacza to, że istnieją dwa warunki, pod którymi pętla może wyjść:

1. current jest null, co oznacza, że lista jest krótsza niż index.
2. i jest równe index, co oznacza, że current jest węzłem na pozycji index.

Jeśli current jest null, to zwracane jest undefined, a w przeciwnym razie current.data. To sprawdzenie zapewnia, że get() nigdy nie wyrzuci błędu dla index, który nie jest znaleziony na liście (chociaż możesz zdecydować się na wyrzucenie błędu zamiast zwracania undefined).

Złożoność metody get() waha się od O(1) przy usuwaniu pierwszego węzła (nie jest potrzebna trawersacja) do O(n) przy usuwaniu ostatniego węzła (wymagane jest trawersowanie całej listy). Trudno jest zmniejszyć złożoność, ponieważ zawsze wymagane jest wyszukiwanie w celu zidentyfikowania poprawnej wartości do zwrócenia.

Usuwanie danych z połączonej listy

Usuwanie danych z połączonej listy jest nieco podstępne, ponieważ musisz zapewnić, że wszystkie next wskaźniki pozostają ważne po usunięciu węzła. Na przykład, jeśli chcesz usunąć drugi węzeł na liście z trzema węzłami, musisz upewnić się, że właściwość next pierwszego węzła wskazuje teraz na trzeci węzeł, a nie na drugi. Pominięcie drugiego węzła w ten sposób skutecznie usuwa go z listy.

Operacja usuwania to tak naprawdę dwie operacje:

1. Znajdź podany indeks (ten sam algorytm co w metodzie get())
2. Usuń węzeł o tym indeksie

Znalezienie podanego indeksu jest takie samo jak w metodzie get(), ale w tej pętli musisz również śledzić węzeł, który znajduje się przed current, ponieważ będziesz musiał zmodyfikować next wskaźnik poprzedniego węzła.

Istnieją również cztery specjalne przypadki do rozważenia:

1. Lista jest pusta (brak możliwości traversal)
2. Indeks jest mniejszy od zera
3. Indeks jest większy od liczby elementów na liście
4. Indeks jest równy zero (usunięcie głowy)

W pierwszych trzech przypadkach operacja usunięcia nie może zostać zakończona, a więc sensowne jest rzucenie błędu; czwarty przypadek specjalny wymaga przepisania właściwości this. Oto jak wygląda implementacja metody remove():

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

Metoda remove() najpierw sprawdza dwa przypadki specjalne, pustą listę (this jest null) oraz index, która jest mniejsza od zera. W obu przypadkach wyrzucany jest błąd.

Kolejnym przypadkiem specjalnym jest sytuacja, gdy index jest 0, co oznacza, że usuwasz nagłówek listy. Nowy nagłówek listy powinien być drugim węzłem na liście, więc możesz ustawić this równe this.next. Nie ma znaczenia, czy jest tylko jeden węzeł na liście, ponieważ this będzie równy null, co oznacza, że lista jest pusta po usunięciu. Jedynym haczykiem jest przechowywanie danych z oryginalnej głowy w zmiennej lokalnej, data, aby można je było zwrócić.

Zaopiekowawszy się trzema z czterech specjalnych przypadków, możesz teraz przejść do traversalu podobnego do tego, który znajduje się w metodzie get(). Jak wspomniano wcześniej, ta pętla różni się nieco tym, że zmienna previous jest używana do śledzenia węzła, który pojawia się tuż przed current, ponieważ ta informacja jest niezbędna do prawidłowego usunięcia węzła. Podobnie jak w przypadku get(), po wyjściu z pętli current może być null, wskazując, że indeks nie został znaleziony. Jeśli tak się stanie, to wyrzucany jest błąd, w przeciwnym razie previous.next jest ustawiany na current.next, efektywnie usuwając current z listy. Dane przechowywane na current są zwracane jako ostatni krok.

Złożoność metody remove() jest taka sama jak get() i waha się od O(1) przy usuwaniu pierwszego węzła do O(n) przy usuwaniu ostatniego węzła.

Uczynienie listy iterowalną

Aby można było jej używać z pętlą JavaScript for-of i destrukcją tablicową, kolekcje danych muszą być iterowalne. Wbudowane kolekcje JavaScript takie jak Array i Set są domyślnie iterowalne, i można uczynić własne klasy iterowalnymi przez określenie metody generatora Symbol.iterator na klasie. Wolę najpierw zaimplementować metodę generatora values() (aby dopasować metodę znalezioną na wbudowanych klasach kolekcji), a następnie kazać Symbol.iterator wywołać values() bezpośrednio.

Metoda values() musi tylko wykonać podstawowe przejście przez listę i yield dane, które zawiera każdy węzeł:

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

Metoda values() jest oznaczona gwiazdką (*), aby wskazać, że jest to metoda generatora. Metoda ta przemierza listę, używając yield do zwrócenia każdego napotkanego fragmentu danych. (Zauważ, że metoda Symbol.iterator nie jest oznaczona jako generator, ponieważ zwraca iterator z metody generatora values().)

Używanie klasy

Po ukończeniu możesz użyć implementacji listy połączonej w ten sposób:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

Tę podstawową implementację listy połączonej można uzupełnić właściwością size do zliczania liczby węzłów na liście oraz innymi znanymi metodami, takimi jak indexOf(). Pełny kod źródłowy jest dostępny na GitHubie w moim projekcie Computer Science in JavaScript.

Wnioski

Listy połączone nie są czymś, czego prawdopodobnie będziesz używał codziennie, ale są one podstawową strukturą danych w informatyce. Koncepcja używania węzłów, które wskazują na siebie nawzajem jest używana w wielu innych strukturach danych są wbudowane w wiele języków programowania wyższego poziomu. Dobre zrozumienie, jak działają listy połączone, jest ważne dla dobrego ogólnego zrozumienia, jak tworzyć i używać innych struktur danych.

Dla programowania w JavaScript, prawie zawsze lepiej jest używać wbudowanych klas kolekcji, takich jak Array, niż tworzyć własne. Wbudowane klasy kolekcji zostały już zoptymalizowane do użytku produkcyjnego i są dobrze obsługiwane w różnych środowiskach wykonawczych.