Singly Linked List

V této části se podíváme na Singly Linked List. Ukážeme si jaké má výhody a nevýhody oproti poli a vytvoříme si jej.

Co je to Linked List

Linked List je datová struktura skládající se z nodes, které jsou spolu jedním nebo oběma směry propojeny. Node je objekt, který uchovává hodnotu a odkaz na další položku v linked listu. Popřípadě i předchozí, pokud se jedná o Doubly Linked List. Linked List obsahuje vlastnosti jako je head, tail a length. Head ukazuje na první objekt v linked listu a tail ukazuje na poslední položku v linked listu. Vlastnost length udává počet položek v linked listu. Linked List představuje základ pro jiné datové struktury jako jsou stacky nebo queues.

Porovnání Linked Listu s polem

Předtím než začneme linked list vytvářet, tak bychom se mohli podívat v čem je jiný oproti poli.

Linked List

Nemá indexy.
Spojený pomocí nodes, které obsahují ukazatel na další položku (popřípadě i na předchozí pokud jde o Doubly Linked List).
Nemůžeme jen tak vzít jakoukoliv hodnotu z linked listu, aniž bychom linked list procházeli.

Pole

Má indexy.
Vkládání a odstraňování položek je více náročné na výkon, protože se musí posouvat indexy.
Můžeme se rychle dostat k jakékoliv hodnotě pomocí indexu.

Vytvoření základu Singly Linked Listu

Pro Singly Linked List si vytvoříme třídu, kterou budeme používat k jeho vytvoření. Tato třída bude obsahovat vlastnosti head, tail a length. Vlastnost head bude uchovávat první node v linked listu a vlastnost tail bude uchovávat poslední node v linked listu. Vlastnost length bude uchovávat počet nodes v linked listu.

Protože se linked list skládá z nodes, tak si pro ně musíme také vytvořit třídu. Node bude obsahovat vlastnost uchovávající hodnotu a odkaz na další node v linked listu.

// třída pro node
class Node {
    constructor(value) {
        // node uchovává hodnotu
        this.value = value;
        // také uchovává odkaz na další položku v linked listu
        this.next = null;
    }
}

// třída pro Singly Linked List
class SinglyLinkedList {
    constructor() {
        // vlastnost head uchovává první položku v linked listu
        this.head = null;
        // vlastnost tail uchovává poslední položku v linked listu
        this.tail = null;
        // vlastnost length uchovává počet položek v linked listu
        this.length = 0;
    }
}

// vytvoření singly linked listu
const list = new SinglyLinkedList();
// přidání položek do linked listu (později si na to vytvoříme metodu)
list.head = new Node(5); // první položka linked listu
list.head.next = new Node(true); // druhá položka linked listu
list.head.next.next = new Node("list"); // třetí položka linked listu
list.tail = list.head.next.next; // poslední položka linked listu je jeho třetí položka
list.length = 3; // linked list obsahuje 3 položky

value: 5

value: true

value: "list"

Předchozí ukázka ukazuje vytvoření linked listu a přidání položek (zatím složitější cestou). Na tuto operaci si později vytvoříme metodu. Také si vytvoříme metodu na odstraňování položek, získávání položek a tak dále. Ve zbytku této části si do naší SinglyLinkedList třídy přidáme různé metody. Ukázky budou vždy ukazovat hlavně jen samotnou metodu bez dalšího kódu kolem.

Metoda push

Pole nám nabízejí metodu push, která slouží k přidání položky na konec pole. Stejnou metodu si vytvoříme i pro singly linked list. Bude sloužit k přidání položky na konec linked listu.

class SinglyLinkedList {
    /* ... */

    // 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 = this.head;
        } else {
            // pokud linked list není prázdný, tak se pro node na kterou ukazuje tail 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 SinglyLinkedList();
// přidání položek na konec linked listu pomocí metody push
list.push(3);
list.push(true);
list.push(12);

Metoda pop

Další metodu, kterou si do našeho Singly Linked Listu přidáme, bude metoda pop. U polí tato metoda slouží k odstranění a získání poslední položky pole. U linked listu bude metoda pop fungovat stejně. Odstraní poslední položku linked listu a vrátí ji.

U singly linked listu je odstraňování poslední položky trochu těžší, protože jsou jeho nodes propojeny jen jedním směrem. Musíme najít jeho předposlední node, nastavit ji jako tail a nastavit její vlastnost next na null.

class SinglyLinkedList {
    /* ... */

    // metoda pro odstranění a získání poslední položky z linked listu
    pop() {
        // pokud linked list neobsahuje žádné položky, vrátí se undefined
        if (!this.head) return undefined;
        // tato proměnná bude později odkazovat na node, která se odstraní
        let current = this.head;
        // tato proměnná bude později odkazovat na node, která bude nový tail
        let newTail = current;
        // následující cyklus najde poslední a předposlední položku v listu
        while (current.next) {
            newTail = current;
            current = current.next;
        }
        // změnění vlastnosti tail na předposlední node v listu
        this.tail = newTail;
        // nastavení vlastnoti next nové tail node na null
        this.tail.next = null;
        // snížení počtu položek v linked listu
        this.length--;
        // pokud je pole prázdné (nový tail je stejný jako odstraněná node), tak se nastaví vlastnosti head a tail na null
        if (this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        // vrácení odstraněné node
        return current;
    }
}

const list = new SinglyLinkedList();
// použití metody push pro vložení hodnot do linked listu
list.push(3).push(true).push(12).push(23);

// odstranění dvou posledních položek linked listu
list.pop();
list.pop();

Metoda shift

Pomocí metody shift můžeme u pole odstranit a získat jeho první položku. Stejnou metodu si vytvoříme i pro náš Singly Linked List. Odstraní první node linked listu a vrátí ji.

class SinglyLinkedList {
    /* ... */

    // metoda pro odstranění a získání první položky z linked listu
    shift() {
        // pokud je linked list prázdný, vrátí se undefined
        if (!this.head) return undefined;
        // uložení aktuální node, která je head, do proměnné
        let currentHead = this.head;
        // nastavení následující node v linked listu jako head (pokud tam již žádná není, nastaví se null);
        this.head = currentHead.next;
        // snížení počtu položek v linked listu
        this.length--;
        // pokud je linked list prázdný, nastaví se také tail na null
        if (this.length === 0) {
            this.tail = null;
        }
        // nastavení vlastnosti next odstraněné node na null (aby přes ni nešlo linked list procházet až ji vrátíme)
        currentHead.next = null;
        // vrácení odstraněné node
        return currentHead;
    }
}

const list = new SinglyLinkedList();
list.push(3).push(true).push(12).push(23);

// odstranění dvou prvních položek linked listu
list.shift();
list.shift();

Metoda unshift

Na přidávání položek na začátek pole existuje metoda unshift. U polí je přidávání položky na začátek drahou operací, protože se musí u ostatních položek pole posunout indexy. U linked listu to tak není, protože se nic přeindexovávat nemusí. Při přidávání položky do linked listu se jen vytvoří nová node, nastaví se jako head, a její vlastnost next se nastaví na bývalou head.

class SinglyLinkedList {
    /* ... */

    // 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.head) {
            // pokud je linked list prázdný, tak se nová node nastaví jako head a tail
            this.head = newNode;
            this.tail = newNode;
        } else {
            // pokud není linked list prázdný, tak se nové node nastaví vlastnost next na aktuální head
            newNode.next = this.head;
            // a 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 SinglyLinkedList();

// přídání tří položek na začátek linked listu
list.unshift(3);
list.unshift(true);
list.unshift(12);

Metoda get

U polí máme možnost získat požadovanou položku pomocí jejího indexu. Linked listy indexy nemají, ale pokud chceme položku podle předaného indexu přece jenom najít, tak si na to můžeme vytvořit metodu. Získávání specifických položek z linked listu není ale tak efektivní jako u polí, protože se linked list musí postupně projet až k požadované node.

class SinglyLinkedList {
    /* ... */

    // 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;

        // do této proměnné se uloží node, která se najde
        let current = this.head;

        // tento cyklus bude probíhat tak dlouho, dokud se nedojde na požadovanou node
        for (let i = 1; i <= index; i++) {
            // posunutí na další node v linked listu
            current = current.next;
        }

        // vrácení nalezené node
        return current;
    }
}

const list = new SinglyLinkedList();
list.unshift(3).unshift(true).unshift(12);

// získání druhé node v linked listu
const ziskanaNode = list.get(1);

Metoda set

Jako další metodu si do našeho Singly Linked Listu přídáme metodu set. Pomocí této metody půjde nastavit hodnota node na předaném indexu. Vytvoření této metody je jednoduché, protože k získání požadované node použijeme metodu get, kterou jsme si vytvořili předtím. Poté jen změníme hodnotu, kterou node uchovává.

class SinglyLinkedList {
    /* ... */

    // 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 SinglyLinkedList();
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 jsme si zatím vytvořili metody push a unshift. Pomocí těchto metod ale můžeme položku přidat pouze na začátek nebo konec linked listu. Pro přídání položky podle předaného indexu si vytvoříme metodu insert.

class SinglyLinkedList {
    /* ... */

    // 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 === this.length) return !!this.push(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 === 0) return !!this.unshift(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á bude předcházet nově přidané node
        const prevNode = this.get(index-1);
        // vlastnost next nové node bude ukazovat na node, na kterou ukazuje vlastnost next předešlé node
        newNode.next = prevNode.next;
        // nastavení vlastnosti next předcházející node na novou node
        prevNode.next = 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 SinglyLinkedList();
list.unshift(3).unshift(true).unshift(12);

// přidání položky na index 2
list.insert(2, 25);

Metoda remove

Pro odstraňování položek ze začátku a konce linked listu máme metody shift a pop. Teď si pro náš Singly Linked List vytvoříme metodu, která nám umožní odstranit položku podle předaného indexu.

class SinglyLinkedList {
    /* ... */

    // 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 poslední node linked listu, tak se použije metoda pop
        if (index === this.length - 1) return this.pop();
        // pokud se má odstranit první node linked listu, tak se použije metoda shift
        if (index === 0) return this.shift();

        // získání node, která předchází node, která se má smazat (použitím metody get)
        const prevNode = this.get(index-1);
        // získání node, která se má odstranit
        const removedNode = prevNode.next;
        // node, která předchází odstraňované node se nastaví vlastnost next na node, kterou má odstraňovaná node jako next
        prevNode.next = removedNode.next;
        // nastavení vlastnosti next odstraněné node na null (aby přes ni nešlo linked list procházet až ji vrátíme)
        removedNode.next = null;

        // snížení počtu položek v linked listu
        this.length--;
        // vrácení odstraněné node
        return removedNode;
    }
}

const list = new SinglyLinkedList();
list.unshift(3).unshift(true).unshift(12);

// odstranění druhé položky linked listu
list.remove(1);

Metoda reverse

Jako poslední metodu si do pro náš Singly Linked List vytvoříme metodu reverse. Jejím zavoláním budeme moci linked list převrátit. Prohodí se tedy head a tail a obrátí se směr propojení linked listu.

class SinglyLinkedList {
    /* ... */

    // metoda pro převrácení linked listu
    reverse() {
        // uložení aktuální head do proměnné
        let node = this.head;
        // prohození head a tail
        this.head = this.tail;
        this.tail = node;

        // pomocné proměnné
        let next;
        let prev = null;

        // tento cyklus bude probíhat tak dlouho, dokud se linked list celý neprojede
        while (node) {
            // uložení vlastnosti next do proměnné next
            next = node.next;
            // nastavení vlastnosti next na předchozí node
            node.next = prev;

            // uložení node do proměnné prev, abychom ji v dalším cyklu mohli použít jako předchozí node
            prev = node;
            // v dalším cyklu se nastaví další node (pokud se next nerovná null)
            node = next;
        }
        return this;
    }
}

const list = new SinglyLinkedList();
list.unshift(3).unshift(true).unshift(12).unshift(26);

// převrácení linked listu
list.reverse();

Big O náročnost Singly Linked Listu

Na závěr bychom se ještě mohli podívat, jaká je časová náročnost některých operací se singly linked listem.

Vkládání hodnot (na začátek a konec): O(1)
Odstraňování hodnot: záleží kde, pokud položku odstraňujeme ze začátku linked listu, tak je to O(1), jinak je to spíš O(n)
Hledání: O(n)
Přístup k položkám: O(n)

pokračovat na další část

Algoritmy a Datové Struktury v JS