Doubly Linked List
V minulé části jsme si ukázali Singly Linked List. V této části se podíváme na Doubly Linked List, který má narozdíl od Singly Linked Listu propojené nodes oběma směry.
Co je to Doubly Linked List
Doubly Linked List je stejná datová struktura jako Singly Linked List. Narozdíl od něj je ale Doubly Linked List složen z nodes, které jsou propojeny oběma směry. Takže každá node obsahuje vlastnosti, které odkazují na další i předchozí node v linked listu. Díky tomu může doubly linked list provádět některé operace rychleji, ale zabere více paměti, protože se v nodes musí ukládat také odkaz na jejich předchozí node.
Vytvoření základu Doubly Linked Listu
Stejně jako pro Singly Linked List si vytvoříme třídu i pro Doubly Linked List. Konstruktor Doubly Linked Listu bude úplně stejný jako ten pro Singly Linked List. Změna bude jen v tom, že node bude uchovávat také vlastnost prev, ve které se bude ukládat odkaz na předchozí node.
// třída pro node
class Node {
constructor(value) {
this.value = value;
this.next = null;
// v Doubly Linked Listu node uchovává odkaz
// také na předchozí node v linked listu
this.prev = null;
}
}
// třída pro Doubly Linked List
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
// vytvoření doubly linked listu
const list = new DoublyLinkedList();
// PŘIDÁNÍ POLOŽEK (později si na to vytvoříme metodu)
// přidání první položky
list.head = new Node(5);
// přidání druhé položky
list.head.next = new Node(true);
list.head.next.prev = list.head;
// přidání třetí položky
list.tail = new Node("list");
list.head.next.next = list.tail;
list.tail.prev = list.head.next;
// linked list obsahuje 3 položky
list.length = 3;Stejně jako v minulé části, předchozí ukázka ukazuje vytvoření linked listu a přidání položek zatím složitější cestou. Později si na to vytvoříme metodu. Ve zbytku části si do naší Doubly Linked List třídy postupně přidáme stejné metody, které jsme si vytvářeli pro Singly Linked List.
Metoda push
Jako první si do naší DoublyLinkedList třídy přidáme metodu push. S její pomocí budeme na konec linked listu moci přidat novou hodnotu. Bude stejná jako ta pro Singly Linked List, akorát bude mít jeden řádek navíc, který bude nastavovat vlastnost prev nově přidané node na předchozí node.
class DoublyLinkedList {
/* ... */
// metoda pro přidání položky na konec linked listu
push(value) {
// vytvoření nové node
const newNode = new Node(value);
if (!this.head) {
// pokud je linked list prázdný, tak se nová node nastaví jako head
this.head = newNode;
// protože má linked list jen jednu položku, tail bude odkazovat na stejnou node jako head
this.tail = newNode;
} else {
// pokud linked list není prázdný, tak se nastaví vlastnost prev nové node na tail linked listu
newNode.prev = this.tail;
// pro node na kterou ukazuje tail se nastaví vlastnost next na novou node
this.tail.next = newNode;
// nová node se nastaví jako tail
this.tail = newNode;
}
// zvýšení počtu položek v linked listu
this.length++;
// po provedení metody se linked list vrátí (abychom mohli třeba řetězit další metody)
return this;
}
}
const list = new DoublyLinkedList();
// přidání položek na konec linked listu pomocí metody push
list.push(3);
list.push(true);
list.push(12);Metoda pop
Jako další metodu si pro náš Doubly Linked List vytvoříme metodu pop, která bude sloužit k odstranění a získání poslední položky v linked listu. Narozdíl od Singly Linked Listu bude jednodušší, protože máme u každé node přístup k předchozí node. Díky tomu můžeme jen nastavit tail na předchozí node aktuálního tailu namísto procházení celého linked listu a hledání předposlední položky.
class DoublyLinkedList {
/* ... */
// metoda pro odstranění a získání poslední položky linked listu
pop() {
// pokud linked list neobsahuje žádné položky, vrátí se undefined
if (!this.head) return undefined;
// uložení node, která je momentálně tail do proměnné
const removedNode = this.tail;
if (this.length === 1) {
// pokud linked list obsahuje jen jednu položku, tak se head a tail nastaví na null
this.head = null;
this.tail = null;
} else {
// pokud linked list obsahuje více jak jednu položku, tak se jako tail nastaví předchozí node aktuální tail node
this.tail = this.tail.prev;
// nastavení vlastnosti next nové tail node na null
this.tail.next = null;
// nastavení vlastnosti prev odstraněné node na null (abychom po jejím vrácení nemohli s její pomocí linked list procházet)
removedNode.prev = null;
}
// snížení počtu položek v linked listu
this.length--;
// vrácení odstraněné node
return removedNode;
}
}
const list = new DoublyLinkedList();
list.push(3).push(true).push(12).push(23);
// odstranění dvou posledních položek linked listu
list.pop();
list.pop();Metoda shift
Dále si do naší DoublyLinkedList třídy přidáme metodu shift, která bude sloužit k odstranění a získání první položky linked listu. Protože nodes v Doubly Linked Listu obsahují odkaz také na jejich předcházející node, tak jej nové head budeme muset nastavit na null.
class DoublyLinkedList {
/* ... */
// metoda pro odstranění a získání první položky linked listu
shift() {
// pokud je linked list prázdný, vrátí se undefined
if (!this.head) return undefined;
// uložení aktuální head do proměnné
const oldHead = this.head;
if (this.length === 1) {
// pokud linked list obsahuje jen jednu položku, tak se head a tail nastaví na null
this.head = null;
this.tail = null;
} else {
// pokud linked list obsahuje více jak jednu položku, tak se jako head nastaví následující node v linked listu
this.head = oldHead.next;
// nastavení vlastnosti prev nové head na null
this.head.prev = null;
// nastavení vlastnosti next odstraněné node na null (abychom s její pomocí nemohli linked list procházet až ji vrátíme)
oldHead.next = null;
}
// snížení počtu položek v linked listu
this.length--;
// vrácení odstraněné node
return oldHead;
}
}
const list = new DoublyLinkedList();
list.push(3).push(true).push(12).push(23);
// odstranění dvou prvních položek linked listu
list.shift();
list.shift();Metoda unshift
Metodu shift pro odstraňování položek ze začátku doubly linked listu máme. Teď si vytvoříme metodu unshift, pomocí které budeme naopak přidávat položky na začátek doubly linked listu.
class DoublyLinkedList {
/* ... */
// metoda pro přidání položky na začátek linked listu
unshift(value) {
// vytvoření nové node
const newNode = new Node(value);
if (this.length === 0) {
// pokud linked list neobsahuje žádné položky, tak se nová node nastaví jako head a tail
this.head = newNode;
this.tail = newNode;
} else {
// pokud linked list obsahuje nějaké položky, tak se vlastnost next nové node nastaví na aktuální head
newNode.next = this.head;
// vlastnost prev pro aktuální head se nastaví na novou node
this.head.prev = newNode;
// nová node se nastaví jako head
this.head = newNode;
}
// zvýšení počtu položek v linked listu
this.length++;
// po provedení metody se linked list vrátí (abychom mohli třeba řetězit další metody)
return this;
}
}
const list = new DoublyLinkedList();
// přidání tří položek na začátek linked listu
list.unshift(3);
list.unshift(true);
list.unshift(12);Metoda get
Stejně jako pro Singly Linked List, tak i pro Doubly Linked List si vytvoříme metodu get, pomocí které budeme moci získat požadovanou node z linked listu podle předaného indexu. Vlastně bychom ani nemuseli pro Doubly Linked List vytvářet novou, mohli bychom zkopírovat tu, kterou jsme vytvořili pro Singly Linked List. Tím bychom ale nevyužili toho, že v Doubly Linked Listu nodes obsahují odkazy také na předchozí nodes. Pokud by například linked list obsahoval 50 nodes a chtěli bychom získat předposlední node, tak bychom museli projet celý list, než bychom se k ní dostali. Kdybychom ale využili toho, že nodes obsahují odkazy také na předchozí položky a procházeli bychom linked list od konce, dostali bychom se k ní mnohem rychleji.
Takže si pro Doubly Linked List vytvoříme novou metodu get, která zjistí prostřední index podle počtu položek v linked listu a porovná jestli je předaný index větší nebo menší než tento index. Pokud bude předaný index menší než prostřední index, tak se bude linked list procházet od začátku, a když větší tak se bude procházet od konce.
class DoublyLinkedList {
/* ... */
// metoda pro získání položky z linked listu podle předaného indexu
get(index) {
// pokud je index mimo rozsah linked listu, tak se vrátí null
if (index < 0 || index >= this.length) return null;
// získání prostředního indexu linked listu
const middleIndex = this.length / 2;
if (index <= middleIndex) {
// pokud je index menší nebo se rovná prostřednímu indexu, tak se linked list bude procházet od začátku
let currentNode = this.head;
// tento cyklus bude linked list postupně procházet
for (let i = 0; i < this.length; i++) {
// pokud se index i rovná předanému indexu, tak se vrátí nalezená node
if (index === i) return currentNode;
// posunutí na další node v linked listu
currentNode = currentNode.next;
}
} else {
// pokud je index větší než prostřední index, tak se linked list bude procházet od konce
let currentNode = this.tail;
// tento cyklus bude linked list postupně procházet
for (let i = this.length-1; i >= 0; i--) {
// pokud se index i rovná předanému indexu, tak se vrátí nalezená node
if (index === i) return currentNode;
// posunutí na další node v linked listu (vlastně spíš předchozí, protože se linked list prochází od konce)
currentNode = currentNode.prev;
}
}
}
}
const list = new DoublyLinkedList();
list.unshift(3).unshift(8).unshift(12).unshift(23).unshift(14);
// získání čtvrté node v linked listu
const ziskanaNode = list.get(3);Metoda set
Další metoda, kterou si do naší DoublyLinkedList třídy přidáme, bude metoda set. Bude úplně stejná jako ta pro Singly Linked List, kterou jsme vytvořili v minulé části. Získáme node pomocí metody get podle předaného indexu a změníme jí hodnotu, kterou uchovává.
class DoublyLinkedList {
/* ... */
// metoda pro nastavení hodnoty na specifickém indexu
set(index, value) {
// získání požadované node pomocí metody get
const node = this.get(index);
// pokud se žádná node nenašla, tak se vrátí false
if (!node) return false;
// změnění hodnoty nalezené node
node.value = value;
// po úspěšném změnění hodnoty funkce vrátí true
return true;
}
}
const list = new DoublyLinkedList();
list.unshift(3).unshift(true).unshift(12);
// změnění hodnoty druhé položky v linked listu
list.set(1, false);Metoda insert
Pro přidávání položek do linked listu podle předaného indexu si vytvoříme metodu insert. Bude podobná její verzi pro Singly Linked List, ale narozdíl od ní musí nově přidanou položku napojit také druhým směrem.
class DoublyLinkedList {
/* ... */
// metoda pro přidání hodnoty na specifickém indexu
insert(index, value) {
// pokud je předaný index mimo rozsah linked listu, tak se vrátí false
if (index < 0 || index > this.length) return false;
// pokud se index rovná délce linked listu, tak se pro přidání položky použije metoda push
if (index === 0) return !!this.unshift(value); // aby se vrátilo true, tak je použita dvakrát negace
// pokud se index rovná 0, tak se pro přidání položky použije metoda unshift
if (index === this.length) return !!this.push(value); // aby se vrátilo true, tak je použita dvakrát negace
// vytvoření nové node
const newNode = new Node(value);
// získání node, která se pro novou node nastaví jako předchozí
const prevNode = this.get(index-1);
// získání node, která se pro novou node nastaví jako následující
const nextNode = prevNode.next;
// propojení nové node s její předchozí node
prevNode.next = newNode, newNode.prev = prevNode;
// propojení nové node s její následující node
newNode.next = nextNode, nextNode.prev = newNode;
// zvýšení počtu položek v linked listu
this.length++;
// položka se úspěšně přidala, vrátí se true
return true;
}
}
const list = new DoublyLinkedList();
list.unshift(3).unshift(true).unshift(12);
// přidání položky na index 2
list.insert(2, 25);Metoda remove
Poslední metodu, kterou si pro náš Doubly Linked List vytvoříme bude metoda remove, pomocí které budeme moci z linked listu odstranit položku podle předaného indexu.
class DoublyLinkedList {
/* ... */
// metoda pro odstranění položky podle předaného indexu
remove(index) {
// pokud je předaný index mimo rozsah linked listu, tak se vrátí undefined
if (index < 0 || index >= this.length) return undefined;
// pokud se má odstranit první node linked listu, tak se použije metoda shift
if (index === 0) return this.shift();
// pokud se má odstranit poslední node linked listu, tak se použije metoda pop
if (index === this.length-1) return this.pop();
// získání node, která se má odstranit
let removedNode = this.get(index);
// získání předchozí node odstraňované node
let prevNode = removedNode.prev;
// získání následující node odstraňované node
let nextNode = removedNode.next;
// propojení předchozí a následující node odstraňované node
prevNode.next = nextNode;
nextNode.prev = prevNode;
// nastavení vlastností prev a next odstraněné node na null (abychom s její pomocí nemohli linked list procházet až ji vrátíme)
removedNode.prev = null, removedNode.next = null;
// snížení počtu položek v linked listu
this.length--;
// vrácení odstraněné node
return removedNode;
}
}
const list = new DoublyLinkedList();
list.unshift(3).unshift(true).unshift(12);
// odstranění druhé položky linked listu
list.remove(1);Big O náročnost Doubly Linked Listu
Na závěr této části se ještě podíváme, jaká je čásová náročnost některých operací s doubly linked listem.
- Vkládání hodnot (na začátek a konec): O(1)
- Odstraňování hodnot (ze začátku a z konce): O(1)
- Hledání: O(n) - technicky je to O(n/2), protože procházíme jen polovinu linked listu, ale to je stále O(n)
- Přístup k položkám: O(n)