javascriptsingly-linked-list

Shift method in a singly linked list


I have this singly linked list:

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

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

and this shift method:

    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }

The question is whether currentHead.next should be equal to null or not. I found several sources on the internet proposing the shift method from above, but I feel like the correct version is with currentHead.next = null.


Solution

  • Setting the next property to null will avoid that the caller would follow that link and traverse through the list, which really is the task of the SinglyLinkedList class and not of the caller.

    But to bring that point home, you should really not return a node, but just the value. The caller should have no business with the Node class. It should only be the SinglyLinkedList class that uses it for its logic, but besides that it should better be completely hidden from the caller. To the caller the linked list should be nothing more than a collection of values and methods to read, delete or insert values.

    So with that in mind, you would design your classes as follows:

    class SinglyLinkedList {
        // Make properties private: caller has no business with those
        #head = null;
        #tail = null;
        #length = 0;
    
        static Node = class {
            constructor(val) {
                this.val = val;
                this.next = null;
            }
        }
        
        constructor(...values) { // allow to be initialised with values
            this.push(...values);
        }
        
        push(...values) {
            for (const val of values) {
                if (!this.#length++) {
                    this.#tail = this.#head = new SinglyLinkedList.Node(val);
                } else {
                    this.#tail = this.#tail.next = new SinglyLinkedList.Node(val);
                }
            }
        }
        
        shift() {
            if (!this.#head) return;
            const val = this.#head.val; // Get value only
            this.#head = this.#head.next;
            if (!--this.#length) this.#tail = null;
            return val;
        }
        
        *values() {
            for (let node = this.#head; node; node = node.next) {
                yield node.val; // only yield value, not node
            }
        }
        
        *[Symbol.iterator]() {
            yield* this.values();
        }
        
        toString() {
            return [...this.values()].join(" -> ");
        }
        
        get length() { // Read only
            return this.#length;
        }
    }
    
    const list = new SinglyLinkedList(10, 20, 30, 40);
    console.log(...list);
    const first = list.shift();
    console.log("shifted out:", first);
    console.log("remainder: " + list);
    console.log("length:", list.length);