CODEWITHSUNDEEP
javascriptsingly-linked-list
fBpv
fBpv

Reputation: 3

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.

Upvotes: 0

Views: 58

Answers (2)

trincot
trincot

Reputation: 350756

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

Upvotes: 2

XNxa
XNxa

Reputation: 26

The reference to currentHead will be returned, and since it is no longer referenced by the list itself, there is no need to set currentHead.next to null, because JavaScript's garbage collector will clean up when it isn't unused anymore. But, if you want to ensure the detached node is completely isolated (i.e., its next property points to null), you could add currentHead.next = null;. This will prevent memory leaks or unintended side effects if the returned node is used once returned.

I guess you could also return the value from the currendHead instead of the Node.

Upvotes: 0

Related Questions