Dziś ‚struktury danych w JavaScripcie – Lista’, czyli powrót do serii artykułów o strukturach danych. Listy to tak naprawdę jedna z najczęściej używanych struktur. W JavaScripcie świetnie symuluje ją zwykła tablica. Mimo to w ramach treningu/nauki zbuduję własną klasę tak jak zrobiłem to ze stosem oraz kolejką. Nie będzie to duże wyzwanie, zachowanie listy jest dość proste. Jednak dobre zrozumienie działania tej struktury danych będzie świetnym wstępem do bardziej wymagających wersji, list jedno i dwukierunkowych.
Lista to zestaw danych ułożonych w konkretnej kolejności. Każdy element ma konkretne położenie w liście. Struktura ta ma możliwość dodania nowego elementu w każdym miejscu listy. Lista może też zwracać informacje ile zawiera elementów, oraz czy nie jest pusta. Oprócz tego można oczywiście usuwać konkretne elementy listy oraz całkowicie ją opróżnić.
Lista daje też możliwość wyświetlenia wszystkich swoich elementów, oraz elementu który znajduje się na aktualnej pozycji. Po liście, można poruszać się w przód oraz w tył. Można też przeskoczyć do elementu na konkretnej pozycji.
Jak widać, lista posiada wiele cech podobnych do tych, które domyślnie znajdują się już w JavaScriptowej tablicy. Jednak, nie wszystkie języki programowania od razu mają wbudowane takie możliwości. Na szczęście struktura ta jest dość prosta w implementacji. Przejdźmy do kodu.
Struktury danych w JavaScripcie – Lista. 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 |
function List() { this.listElements = []; this.listSize = 0; this.pos = 0; this.append = function(element){ this.listElements[this.listSize++] = element; }; this.find = function(element){ for (var i = 0; i < this.listElements.length; i++) { if(this.listElements[i] == element){ return i; } } return -1; }; this.remove = function(element){ var elemPos = this.find(element) if(elemPos > -1){ this.listElements.splice(elemPos,1); this.listSize--; } }; this.length = function(){ return this.listSize; }; this.view = function(){ return this.listElements; }; this.insert = function(element, after){ var afterPos = this.find(after); if(afterPos > -1){ this.listElements.splice(afterPos+1,0,element); this.listSize++; } }; this.contains = function(element){ var elemPos = this.find(element); if(elemPos > -1) { return true; } else { return false; } }; this.moveTo = function(position){ this.pos = position }; this.getElem = function(){ return this.listElements[this.pos]; }; this.previous = function(){ return this.listElements[--this.pos]; }; this.next = function(){ return this.listElements[this.pos++]; }; this.front = function(){ this.pos = 0; } this.end = function(){ this.pos = this.listSize-1; } } |
Jeśli chodzi o pola klasy to nie ma za bardzo o czym pisać. listElements to tablica, która przechowywać będzie wszystkie dane listy. listSize, która początkowo wynosi zero, to informacja o wielkości listy, czyli liczbie jej elementów. Ostatnie pole pos reprezentuje miejsce w liście, na którym aktualnie znajduje się użytkownik. Jeżeli znaczenie ostatniego pola, wydaje się być teraz niejasne, spokojnie. Wszystko powinno się wyklarować gdy wyjaśnię działanie konkretnych metod.
A skoro już o tym mowa, przejdę do metod.
- append – Ta metoda dodaje przekazany w argumencie element do tablicy listElements. Pozycja nowego elementu to wartość pola listSize. Wartość ta jest od razu inkrementowana. Ten kod gwarantuje, że element przekazany metodzie append zawsze będzie dodawany na końcu tablicy.
- find – Ta metoda, nie jest wykorzystywana bezpośrednio, ale wspomaga parę innych metod. Jej działanie jest bardzo podobne do indexOf. Pętla for przeszukuje tablicę listElements i sprawdza czy któryś element jest równy temu, który został przekazany metodzie jako argument. Jeżeli metoda znajdzie ten element w tablicy, zwraca jego indeks. Jeżeli pętla przejdzie przez całą tablicę i nie zostanie ona przerwana przez return, metoda zwraca wartość -1
- remove – Ta metoda wykorzystuje opisaną wcześniej metodę find, aby znaleźć przekazany w argumencie element. Jeżeli zostanie on znaleziony, metoda usuwa go z tablicy listElements przy pomocy splice. Wartość pola listSize jest zmniejszana o jeden.
- length – Ta metoda zwraca po prostu aktualną wartość pola listSize.
- view – Ta metoda zwraca całą tablicę listElements
- insert – Ta metoda przyjmuje dwa argumenty. Pierwszy to element, który ma zostać dodany do list. Drugi to element, którym ma być dodany nowy element. Znów wykorzystana jest metoda find aby odnaleźć indeks elementu za którym pojawi się nowy. Jeżeli element ten zostanie odnaleziony, nowy element dodawany jest na odpowiednią pozycję przy pomocy splice.
- contains – Ta metoda przy pomocy find odnajduje indeks przekazanego jako argument elementu w tablicy listElements. Jeżeli indeks jest większy od -1 zwracane jest true. W innym wypadku metoda zwraca false.
- moveTo – Ta metoda zmienia wartość pola pos na wartość przekazaną w argumencie.
- getElem – Ta metoda zwraca element znajdujący się w tablicy listElements pod indeksem równym obecnej wartości pola pos.
- previous – Ta metoda najpierw obniżą wartość pola pos o jeden a następnie zwraca element tablicy listElements pod indeksem równym obecnej wartości pola pos.
- next – Ta metoda najpierw zwraca element tablicy listElements pod indeksem równym obecnej wartości pola pos, a następnie podnosi jego wartość o jeden. Ta i poprzednia metoda, mogą początkowo wydawać się trochę dziwne. Chodzi w nich o to, aby metoda previous, zwróciła ten sam element, który został zwrócony w wyniku wcześniej wywołanej metody next. Warto poświęcić trochę czasu na zrozumienie co tu się dzieje, szczególnie w kontekście całej klasy List
- front – Ta metoda po prostu zwraca element znajdujący się na początku listy.
- end – Ta metoda z kolei zwraca element znajdujący się na końcu listy.
I to cała klasa. Tak jak pisałem na początku, nie jest specjalnie skomplikowana. Na koniec przeprowadzę jeszcze parę testów, które sprawdzą czy wszystko działa jak należy. Mogą to być proste wywołania w stylu kodu poniżej.
|
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 |
var list = new List; console.log(list.view()); list.append("maja"); console.log(list.view()); console.log(list.length()); list.append("miluś"); list.append("dżeki"); list.append("kudłacz"); list.append("bobek"); list.append("rambo"); console.log(list.view()); console.log(list.length()); list.remove("kudłacz"); console.log(list.view()); console.log(list.length()); list.insert("kudłacz", "miluś"); console.log(list.view()); console.log(list.length()); console.log(list.contains("puszek")); console.log(list.contains("maja")); console.log(list.pos); console.log(list.moveTo(3)); console.log(list.pos); console.log(list.next()); console.log(list.pos); console.log(list.previous()); console.log(list.pos); console.log(list.next()); console.log(list.next()); console.log(list.pos); |
Najpierw tworzę instancję klasy List a następnie bawię się nią, dodając i usuwając elementy. Gdy mam pewność że wszystko gra, mogę zabrać się za dalszą pracę.
Jednak na ten post to wszystko, chociaż to dopiero początek tematu list. W kolejnych postać o tej strukturze przedstawię wersje jedno i dwukierunkową. Na koniec nie zabraknie przykładowych aplikacji wykorzystujących te struktury danych.
Jeśli chcesz być na bieżąco, nie zapomnij polubić mojej strony na Facebooku. Wszystkie informacje o nowych i nadchodzących postach są tam na bieżąco zamieszczane.