javascriptlinked-listcircular-list

Problems when printing a circular singly linked list


I have a circular singly linked list code:

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

class LinkdeList{
    constructor(){
        this.first = null;
        this.last = null;
    }

    empty(){
        return this.first === null
    }

    insert(value){
        let newest = new Node(value);

        if (this.empty()) {
            this.first = this.last = newest;
            this.last.next = this.first;
        }else{
            newest.next = this.first;
            this.first = newest;
            this.last.next = this.first;
        }
    }

    traverse(){
        let aux = this.first;
        while (aux.next != this.first) {
            console.log(aux.value);
            aux = aux.next;
        }
    }
}

let linked = new LinkdeList();
linked.insert("David");
linked.insert("John");
linked.insert("Adam")
linked.insert("Bob");
linked.traverse();

And when I tried to print the list, I just get in console 3 names:

Bob
Adam
John

And as you can see I push 4 names in my linked list. I tried to print the values of my list in the traverse method, but It didn´t work because I don´t get in console:

Bob
Adam
John
David

Solution

  • The loop stops one step too early. This is a good case for a do ... while loop. You should also protect it from failing when the list is empty

        traverse() {
            if (this.empty()) return; // <---
            let aux = this.first;
            do {
                console.log(aux.value);
                aux = aux.next;
            } while (aux != this.first);
        }
    

    Some other remarks on your code:

    class Node {
        constructor(value) {
            this.value = value;
            this.next = this; // self-reference
        }
    }
    
    class LinkedList {
        constructor() {
            this.last = null; // No need for a `first`
        }
    
        isEmpty() {
            return this.last === null;
        }
    
        insert(value) {
            const newest = new Node(value);
            if (!this.isEmpty()) {
                newest.next = this.last.next;
                this.last.next = newest;
            }
            this.last = newest;
        }
    
        *traverse() { // Generator
            if (this.isEmpty()) return; // Guard
            let aux = this.last;
            do  {
                aux = aux.next;
                yield aux.value; // Don't print. Yield instead.
            } while (aux != this.last);
        }
    }
    
    const linked = new LinkedList();
    linked.insert("David");
    linked.insert("John");
    linked.insert("Adam")
    linked.insert("Bob");
    // Caller of traverse can decide what to do: we want to print:
    for (const name of linked.traverse()) console.log(name);