Kolejny post z serii struktury danych w JavaScripcie – lista jednokierunkowa. Podstawy działania listy omówiłem ostatnim razem. Teraz kolej na bardziej rozbudowaną wersję tej struktury danych – listę jednokierunkową.
Elementy listy jednokierunkowej, zwane również węzłami, zawierają dwie informacje. Pierwsza to faktyczne dane elementu a druga to w jakiej pozycji się znajdują. W odróżnieniu do zwykłych list czy tablic, informacja o lokacji, to nie indeks. W liście jednokierunkowej, elementy nie mają ponumerowanych pozycji. Są ułożone względem siebie. Każdy węzeł zawiera informacje, który węzeł jest następny. Ta struktura, daje możliwość wykonywania prostych i szybkich operacji na danych.
Oto ilustracja listy jednokierunkowej, zawierającej 3 elementy:
Każdy węzeł składa się z dwóch pól. Jedno to dane elementu, a drugie to wskaźnik na kolejny węzeł. Strzałki pokazują gdzie kieruje odpowiedni wskaźnik. Wyraźnie widać tu jak tego typu struktura buduje coś w rodzaju łańcucha. Węzły nie posiadają numeru indeksu, ale dzięki relacją między nimi można łatwo zlokalizować każdy z nich.
Poniżej schemat ilustrujący jak dodawać elementy do listy jednokierunkowej:
Tak jak pisałem wcześniej, operowanie danymi znajdującymi się w liście jednokierunkowej jest bardzo łatwe. Aby dodać nowy węzeł pomiędzy dwa już istniejące, wystarczy wskaźnik pierwszego z nich skierować na nowy element. Następnie wskaźnik nowego elementu ustawić tak aby wskazywał element przed którym go umieszczamy. Na ilustracji widać, jak nowy element ‚wpinany’ jest pomiędzy istniejące. To tak jak dodanie nowego ogniwa do łańcucha.
Schemat ilustrujący usuwanie elementów z listy jednokierunkowej:
Usuwanie elementów jest jeszcze prostsze. Wystarczy wskaźnik węzła znajdującego się przed usuwanym elementem, zmienić tak aby wskazywał na węzeł znajdujący się po usuwanym elemencie. W ten sposób jeden z elementów przestaje być częścią łańcucha. Element, na który nie wskazuje nic w programie zostanie usunięty z pamięci przez JavaScriptowy kolektor śmieci.
struktury danych w JavaScripcie – lista jednokierunkowa. Kod.
Skoro teoria działania listy jednokierunkowej jest już jasna, pora abym przedstawił implementację JavaScriptową. Jak zwykle będzie to obiekt, zawierający zarówno dane listy jak i metody ułatwiające pracę nad nią. Ta implementacja nie będzie zawierała wiele metod. Tak naprawdę potrzebne są tylko metody do dodawania elementów (ja zaimplementowałem dwie, jedna wstawia element na koniec listy, druga na wybranej pozycji) oraz ich usuwania. Do tego dodałem również metodę która wyświetla całą listę.
W tej implementacji znalazła się też metoda wyświetlająca element na konkretnej pozycji (licząc od początku). Jest to metoda mająca pomóc użytkownikowi zlokalizować element, który chce usunąć. Pisałem wcześniej że listy jednokierunkowe nie wymagają indeksów. Jednak dla człowieka najlepszym sposobem na usuwanie lub dodawanie elementów na konkretnej pozycji. Ta informacja jest unikatowa dla każdego węzła. Istnieją implementacje tej struktury danych, których metody szukają węzłów po ich zawartości i usuwają/dodają elementy przed lub za nimi. Problem z tym podejściem zaczyna się w momencie kiedy w liście znajduje się dwa lub więcej identycznych węzłów. Dlatego ja zdecydowałem się na ‚wyliczanie’ elementów.
Skoro to już wyjaśnione, czas na kod.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
var LinkedList = function(){ this.Node = function(element){ this.element = element; this.next = null; } this.head = null; this.size = 0; this.append = function(element) { var node = new this.Node(element); if(this.head === null) { this.head = node; } else { var current = this.head; while(current.next) { current = current.next; } current.next = node; } this.size++; }; this.view = function(){ var current = this.head; var string = ''; while(current) { string+= (current.element+", "); current = current.next; } if(string === '') { return "list is empty"; } else { return string; } }; this.insert = function(position, element){ if (position>= 0 && position<= this.size){ var node = new this.Node(element); var current = this.head; var index = 0; var previous; if(position === 0) { node.next = current; this.head = node; } else { while(index < position) { previous = current; current = current.next; index++; } node.next = current; previous.next = node; } this.size++; return true; } else { return false } }; this.viewAt = function(position) { if (position>= 0 && position<= this.size-1){ var current = this.head; var index = 0; while(position > index) { current = current.next; index++; } return current.element; } else { return "no such position on list" } } this.removeAt = function(position) { if (position>= 0 && position<= this.size-1){ var current = this.head; var index = 0; var previous; if(position === 0) { this.head = current.next } else if (position === this.size-1){ while (position > index) { previous = current; current = current.next; index++; } previous.next = null; } else { while (position > index) { previous = current; current = current.next; index++; } previous.next = current.next; } this.size--; return true; } else { return false; } } }; |
Na początku konstruktora znajduje się metoda Node oraz dwa pola head oraz size.
Node to tak naprawdę klasa/konstruktor. Służy ona do budowania nowych węzłów. Zawiera dwa pola, element czyli faktyczną zawartość węzła oraz next, czyli wskaźnik na kolejny węzeł.
head to bardzo ważne pole. Będzie ono zawierać pierwszy węzeł listy jednokierunkowej. Listy jednokierunkowe można wyobrazić sobie jako pociągi. head to lokomotywa.
size to pole, które zawierać będzie ilość wszystkich elementów w liście. Wykorzystuje je jedynie do tego aby sprawdzać, czy użytkownik nie próbuje dodać lub usunąć węzłów z nieistniejących pozycji.
Pierwsza metoda to append. Służy do dodania nowego węzła na końcu listy. Przyjmuje jeden parametr – dane, które węzeł ma przechowywać. Pierwszą rzeczą, która tu się dzieje to stworzenie zmiennej node do której przypisywana jest nowa instancja klasy Node. Jako parametr, przekazywany jest parametr podany metodzie. W ten sposób powstaje nowy węzeł o wartości przekazanej w parametrze i polu next równym (póki co) null. Teraz trzeba ten węzeł gdzieś dołączyć. Są dwie możliwości. Pierwsza to taka, że lista jest pusta. Wtedy zadanie jest proste, do pola head głównej klasy wystarczy przypisać zmienną node. Drugi scenariusz jest taki, że lista zawiera już jakieś elementy. Jeżeli tak jest, tworzę zmienną pomocniczą current. Do current przypisuję pole head, czyli pierwszy element listy. następnie przy pomocy pętli while, przypisuje do current wartość tego co zawiera on w swoim polu next. Pętla wykonuje się dopóki next zawiera jakąś wartość. Jeśli jest równe null, oznacza to, że jest to ostatni węzeł. Już poza pętlą do pola next węzła wskazywanego przez zmienną current przypisywana jest wartość zmiennej node. I tak na koniec listy dodany jest nowy element. Ostatnia operacja to zwiększenie wartości pola size o jeden. Działanie tej metody może wydawać się na początku skomplikowane, ale naprawdę nie jest. Po prostu od samego początku wykorzystuję wszystkie właściwości tej struktury danych. Warto poświęcić trochę czasu na przyjrzenie się treści kodu. Gwarantuje, że po zrozumieniu tej części, reszta będzie już prosta. Jeżeli wszystko jest już zrozumiałe pora na kolejną metodę.
Metoda view ma dość prostolinijne działanie. Podobnie do poprzedniej metody, przy pomocy pętli while, przechodzi przez wszystkie elementy listy. Pętla zaczyna od pola head. Przy każdej iteracji, dodaje element węzła do łańcucha znaków i przechodzi do kolejnego węzła poprzez pole next aktualnego. Po zakończeniu pętli, pełny łańcuch znaków jest zwracany. Jeżeli po przebiegu pętli łańcuch znaków jest wciąż pusty, oznacza to, że lista nie zawiera elementów. W takim wypadku zwracany jest odpowiedni komunikat.
Kolejna metoda to insert. Służy ona do dodawania węzła do list na konkretną pozycję. Metoda przyjmuje dwa argumenty, pierwszy z nich to pozycja, na którą ma być dodany nowy węzeł a druga to wartość nowo tworzonego elementu. Podobnie jak w metodzie append tworzona jest nowa instancja klasy Node. Konstruktor otrzymuje odpowiedni argument a wynik wywołania konstruktora przypisany jest do zmiennej node. Zmienna current, do której przypisuję wartość pola head, będzie pomagać w iteracji przez elementy listy. W tym samym celu tworzę też zmienną index. Ostatnia zmienna, która z kolei potrzebna będzie przy dodawaniu elementu jest previous, początkowo jest pusta.
Zanim metoda zacznie cokolwiek dodawać, sprawdza czy podana pozycja jest prawidłowa dla danej listy, czyli czy nie jest mniejsza od zera i czy nie jest większa od wartości pola size. Mój sposób indeksowania liczy tradycyjnie od zera, więc jeżeli użytkownik poda pozycje równą size, element zostanie dodany na koniec listy. Jeśli początkowy warunek jest spełniony, metoda przechodzi do wykonywania dalszych operacji.
W wypadku dodawania węzła na konkretnej pozycji istnieją dwie możliwości. Pierwsza z nich to dodanie elementu na początku listy, czyli na pozycji zero. Jest to prostszy przypadek. Wtedy to na co wskazuje zmienna current wystarczy przypisać do pola next zmiennej node, czyli nowo utworzonego węzła. Następnie węzeł ten przypisać do pola head, głównej klasy.
Druga możliwość to dodanie węzła na późniejszej pozycji. W takim wypadku, metoda iteruje przez elementy, dopóki indeks jest mniejszy od podanej pozycji. Podczas każdego obiegu pętli, do zmiennej previous przypisywana jest wartość current a do current to na co wskazue current.next. W ten sposób metoda ma dostęp nie tylko do aktualnego elementu ale też do poprzedniego. Na koniec obiegu, oczywiście inkrementuję indeks. Pętla zakończy się gdy indeks dojdzie do odpowiedniej pozycji. Wtedy do pola next elementu na który wskazuje zmienna previous przypisuję nowy element znajdujący się zmiennej node. Następnie do pola next nowego węzła przypisuję element, na który wskazuje zmienna current. W ten sposób pomiędzy dwa istniejące węzły wciśnięty zostaje nowy, dokładnie tak jak na drugim schemacie obrazkowym, które pokazywałem wcześniej.
Oczywiście po udanym dodaniu nowego elementu pole size jest inkrementowane.
Kolejna metoda to viewAt. Służy ona do wyświetlania elementu na konkretnej pozycji. Dzięki temu przed usunięciem czegoś jest możliwość upewnienia się co na danej pozycji się znajduję.
Metoda przyjmuje jeden argument, pozycję elementu który ma być wyświetlony. Jeżeli podana pozycja nie znajduje się w dopuszczalnym przedziale, metoda zwraca komunikat, iż dany element nie może być wyświetlony. W innym wypadku, tworzone są dwie zmienne current oraz index. Iteracja przez elementy występuje tak samo jak w poprzedniej metodzie. W momencie zatrzymania pętli, current wskazuje na węzeł znajdujący się na odpowiedniej pozycji. Metoda zwraca zawartość pola element danego węzła.
Ostatnia metoda, removeAt, służy do usuwania elementów z listy. Ta metoda przyjmuje tylko jeden argument, pozycję elementu, który ma zostać usunięty. Tradycyjnie na początku sprawdzam, czy podana pozycja jest poprawna. Jeżeli tak, tworzone są zmienne pomocnicze: current, previous oraz index. Podczas usuwania elementu, istnieją trzy możliwe scenariusze.
Pierwszy to taki, że usuwany element to pierwszy element (pozycja równa zero). W takim wypadku, do head przypisuję po prostu wartość jego pola next. W ten sposób pierwszy element ‚znika’ z listy.
Drugi możliwy scenariusz wydarzy się, gdy do usunięcia jest ostatni element (pozycja równa size minus jeden). Iteruję wtedy przez całą listę, cały czas aktualizując zmienne current oraz previous. Gdy pętla się zatrzyma wystarczy w obiekcie wskazywanym przez zmienną previous ustawić polę next na null. I tak ostatni element zostanie usunięty z listy.
Trzeci scenariusz to wszystkie inne przypadki, czyli gdy węzeł do usunięcia znajduje się wewnątrz listy. Poszukujemy go używając pętli while, która trwa do momentu aż index (inkrementowany co obieg) równy będzie pozycji. Gdy to się stanie, zmieniamy pole next obiektu aktualnie wskazywanego przez previous tak aby wskazywało na to na co wskazuje pole next obiektu aktualnie wskazywanego przez current. W ten sposób element znajdujący się na odpowiedniej pozycji zostanie ‚wyłączony’ z ‚łańcucha’, zupełnie jak na trzecim obrazku, które pokazywałem powyżej.
Wyszedł długi post, ponieważ chciałem w miarę dokładnie wytłumaczyć działanie klasy reprezentującej tę strukturę danych. Oczywiście jest ona bardziej skomplikowana niż stos czy kolejka, ale myślę, że mimo to nie jest trudna do zrozumienia. Jeżeli coś jest niejasne, chętnie odpowiem na wszelkie pytania. Można zadawać je w komentarzach pod tym postem lub na mojej stronie na facebooku. (Stronę, którą swoją drogą gorąco zachęcam abyście polubili 🙂 )