JS - rekurencja pętlą, node

Teraz przejdziemy po elementach listy wiązanej za pomocą stosu i pętli zamiast rekurencji, poznając patent, który bardzo się przyda w przyszłości do grafów.

Ok, z poprzedniego przykładu:

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

let one = new Node(1);
let two = new Node(2);
let three = new Node(3);
let four = new Node(4);

one.next = two;
two.next = three;
three.next = four;

Wtedy w ten sposób sobie wyświetlaliśmy elementy listy:

function printLinkedList(root){

    function _handle(root){

        if(root === null)
            return;

        console.log(root.val);
        _handle(root.next);

    }

    _handle(root);
}

printLinkedList(one);
//1 2 3 4

Bardzo elegancko. Wersja ze stosem zamiast rekurencji aż tak elegancka nie jest, ale ma tę zaletę, że do drzewek i grafów również się nadaje, tam gdzie rekurencja zawodzi, bo jest więcej niż jeden kierunek, w którym można iść i zamiast wywołań rekurencyjnych next trzeba każdy kierunek (lewo, prawo, ten czy tamten graf) wrzucić na stos.

Ok, ale spróbujmy w naszym przykładzie stos wykorzystać:

function stackPrintLinkedList(root){
   
    let nodeStack = [];
    let inStack = [];
   
    nodeStack.push(root);
   
    while(nodeStack.length > 0){
       
        let currentNode = nodeStack.pop();
       
        inStack.push(currentNode.val);

        if(currentNode.next !== null)
            nodeStack.push(currentNode.next);
      }
    
    let outStack = [];

    while(inStack.length > 0){
        outStack.push(inStack.pop());
    }

    while(outStack.length > 0){
        console.log(outStack.pop());
    }
}

stackPrintLinkedList(one);
//1 2 3 4

Tutaj jest bardzo podstępny mechanizm użyty:

stos nodeStack jest warunkiem pętli while
zrzucamy z tego stosu i wrzucamy do inStack value
jeżeli zrzucony element ma next, to wrzucamy go na stos będący warunkiem pętli (rekurencja w pętli, tak!)

I całe piękno tego rozwiązania, w przypadku LL brzydkiego, polega na tym, że node może mieć zamiast next left i right, N S W E (kierunki geograficzne) albo nieograniczoną ilość innych grafów.

I rekurencja tego NIE obsłuży. „Stosowa rekurencja” już tak.

Ok, ale jak to działa:

Wrzuć root na stos będący warunkiem
Zrzuć ze stosu i na inStack wrzuć wartość
Sprawdź, czy next, jeśli tak, wrzuć na stos będący warunkiem
Po pierwszej pętli zrzucaj z inStack 1,2,3,4 (4 pierwsze do zrzutu) i wrzucaj na outStack 4,3,2,1 (1 pierwsze do zrzutu)
Zrzucaj z outStack i loguj 1, potem 2, 3, 4…

Cała filozofia i w przypadku linked list nie jest to nam potrzebne, rekurencja lepsza, natomiast drzewa i grafy (zwłaszcza grafy), tam się tego rodzaju stosy przydadzą, warto zatem znać to podejście.

JS – rekurencja pętlą, node