LinkedListNr #2 Linked List zwana także listą jednokierunkową jest zbiorem powiązanych ze sobą węzłów tak, aby każdy węzeł wskazywał na następnym element na liście. Każdy węzeł ma wartość, jak i referencję/wskaźnik do następnego węzła.
Istnieje także lista dwu kierunkowa, taka lista także wskazuje do węzła poprzedniego. Lista dwu kierunkowa lepiej się sprawdza do usuwania elementów z listy, gdyż dzięki tej dodatkowej informacji o poprzednim węźle łatwiej Ci będzie namierzyć element potrzebny do usunięcia.
W tym wpisie będzie tylko lista jedno-kierunkowa, ale miej świadomość, że taka też istnieje.
Stosuje też strategię "last in first out" czyli pierwszy element, który wszedł do listy z niej także wyjdzie.
Do znalezienia konkretny węzeł musisz zeskanować całą listę. Zaczynasz od "head node" czyli od pierwszego węzła na liście, aż trafisz na węzeł, który nie ma następnego elementu.
Jakie metody będą nam potrzebne, aby taką listę utworzyć:
- push : Doda element do listy
- pop : usunie element z listy
- get(index) : zwraca element w danym indeksie, ale go nie usuwa
- delete(index) : kasuje element w danym indeksie
- isEmpty() : zwraca wartość logiczną określającą czy dana lista jest pusta
Zbudujmy więc LinkedList w JavaScript. Zacznijmy od klasy definiującą sam węzeł. Węzeł będzie przechowywał wartość jak wskaźnik do następnego węzła. Domyślnie powinien on być null.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}Teraz możemy stworzyć klasę reprezentującą samą listę jednokierunkową. Konstruktor musi przypilnować trzech rzeczy:
- head : Gdzie znajduje się początek naszej listy, czyli gdzie jest pierwszy element
- tail : Gdzie jest ostatni element naszej listy, który będzie wskazywał na null
- length : Ilość węzłów w naszej liście
Na początku nasza lista nie ma żadnych elementów więc głowa i ogon są puste.
class LinkedList {
construktor() {
this.head = null;
this.tail = null;
this.length = 0;
}
isEmpty() {
return this.length === 0;
}
}Dodatkowo mamy już implementację naszej metody IsEmpty()
Jak dodawać węzły do listy? Wszystko zależy od tego, w jakim stanie obecnie jest nasza lista. Najpierw obsłużmy sytuacje, w której dodamy nasz pierwszy węzeł.
Gdy dodajemy pierwszy element staje się on głową, jak i ogonem całej listy
push(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
}
}A co się staje, gdy lista ma przynajmniej jeden element? Musimy ustawić następny węzeł do poprzedniego węzła.
Musimy też zaktualizować wielkość naszej listy oraz nasz ogon.
push(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
}Jak wyjmować elementy z listy? Podobnie jak wcześniej musimy wziąć pod uwagę pewne scenariusze.
pop() {
if (this.isEmpty()) {
return null;
}
}Gdy lista jest pusta zwracamy null. Gdy na liście jest tylko jeden element to resetujemy ogon i głowę listę do wartości NULL zmniejszamy wielkość tej listy do zera. Jak sprawdzić, czy lista ma tylko jeden element? Możesz sprawdzić poprzez właściwość length lub poprzez sprawdzenie, czy ogon i głowa referują się do tego samego elementu
pop() {
if (this.isEmpty()) {
return null;
} else if (this.length === 1) {
const nodeToRemove = this.head;
this.head = null;
this.tail = null;
this.length--;
return nodeToRemove;
}
}A co jeżeli jest więcej niż jeden element na liście? LinkedList ogranicza nas i nie możemy bezpośrednio odwołać się konkretnego elementu z listy.
Przykładowo, jeśli chcesz wyjąc element, który jest na ogonie listy to najpierw musisz znaleźć węzeł, który wskazuję na ten element.
Gdy znajdziemy przedostatni węzeł to też musimy go zaktualizować tak by później on był tym ostatnim elementem i wskazywał na null.
Gdy znajdziemy przedostatni węzeł to zmieniamy jego wskaźnik do następnego elementu
Na końcu musimy także zaktualizować ogon listy, gdyż mamy nowy ostatni element listy
pop() {
if (this.isEmpty()) {
return null;
} else if (this.length === 1) {
const nodeToRemove = this.head;
this.head = null;
this.tail = null;
this.length--;
return nodeToRemove;
} else {
let currentNode = this.head;
const nodetoRemove = this.tail;
let secondToLastNode;
while(currentNode) {
if (currentNode.next === this.tail) {
secondToLastNode = currentNode;
break;
}
currentNode = currentNode.next;
}
secondToLastNode.next = null;
this.tail = secondToLastNode;
this.length--;
return nodeToRemove();
}
}Stwórzmy teraz metodę, która będzie zwracać element w danym miejscu w indeksie. Trzeba obsłużyć trzy przypadki :
- indeks wykracza poza przestrzeń listy
- lista jest pusta
- pytamy o ostatni lub pierwszy element
Najpierw obsłużmy fakt, że możemy dostać nieprawidłowy indeks do naszej listy
get(index) {
if (index < 0 || index > this.length || this.isEmpty()){
return null;
}
}
Gdy pytamy o pierwszy lub ostatni element musimy tylko zwrócić ogon, lub głowę listy
get(index) {
if (index < 0 || index > this.length || this.isEmpty()){
return null;
}
if (index === 0){
return this.head;
}
if (index === this.length - 1) {
return this.tail;
}
}
Zapytanie o dowolny inny element wymaga iteracji listy.
get(index) {
if (index < 0 || index > this.length || this.isEmpty()){
return null;
}
if (index === 0){
return this.head;
}
if (index === this.length - 1) {
return this.tail;
}
let currentNode = this.head;
let iterator = 0;
while(iterator < index) {
iterator++;
currentNode = currentNode.next;
}
return currentNode;
}
