Singly Linked List - Javascript

Creating a Node :

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

Singly Linked List:

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

1. Push Method:

Pseudocode :

1. Function should accept a value.
2. Create a new node using the value passed in the function.
3. If there is no head property on the list, set the head and tail to be the newly created node.
4. Otherwise set the next property on the tail to be the new node and set the tail property on the list to be the newly created node.
5. Increment the length by one.
6. Return the linked list.

Code:

// With Comments:

push(val) {

        let newNode = new Node(val);  // Creating a new node using the value passed
// If we don't have head property on the list or If we have head property on list
        if(!this.head) {                             
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
// Increment the length by 1 and return the linked list
        this.length++;
        return this;
    }

// Without comments

push(val) {
        let newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }

1. Pop Method:

Pseudocode

1. If there are no nodes in the list, return undefined.
2. Loop through the list until you reach the Tail.
3. Set the next property on the second last node to be null.
4. Set the Tail to be the second to last node.
5. Decrement the length of the list by one.
6. Return the value of the node removed.

Code:

// With Comments
 pop() {
        if(!this.head) return undefined; // If no nodes in list return undefined
        // variables to store head and new Tail
        let current = this.head; 
        let newTail = current;

        // Loop until last element is not reached
        while(current.next) {
            newTail = current;
            current = current.next;
        }

        // Assigning second last element to tail and setting the pointer to null
        this.tail = newTail;
        this.tail.next = null;

        // Reduce the length by 1
        this.length--;

        // If we removed the last node of the list then we set the head and tail's value to null
        if(this.length === 0) {
            this.head = null;
            this.tail = null;
        }

        // Return the last element
        return current;
    }

// Without Comments
 pop() {
        if(!this.head) return undefined;
        let current = this.head;
        let newTail = current;
        while(current.next) {
            newTail = current;
            current = current.next;
        }

        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0) {
            this.head = null;
            this.tail = null;
        }

        return current;
    }

1. Shift method:

Pseudocode:

1. If there are no nodes, return undefined.
2. Store the current head property in a variable.
3. Set the head property to be the current head's next property.
4. Decrement the length by one.
5. Return the value of the node removed.

Code:

// With Comments

shift() {
        // If list is empty return undefined
        if(!this.head) return undefined;

        // Store the current head in a variable
        let currentHead = this.head;

        // Assign the second value of the list to the head
        this.head = currentHead.next;

       // reduce the length by one
        this.length--;

        // If no nodes are left in the list
        if(this.length === 0) {
            this.tail = null;
        }

        return currentHead;
    }

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

        return currentHead;
    }

1. Unshift method:

Pseudocode:

1. This function should accept a value.
2. Create a new node using the value passed to the function.
3. If there is no head property on the list, set the head and tail to be the newly created node.
4. Otherwise set the newly created node's next property to be the current head property on the list.
5. Set the head property on the list to be that newly created node.
6. Increment the length of the list by one.
7. Return the Linked List.

// With Comments
 unshift(val) {
        // Create a new Node using the value passed
        let newNode = new Node(val);

        // If the list is empty then set head and tail to the newly created node else set newnode's next property to current head and head to new node.
        if(!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }

        // Increase the length by one
        this.length++;
        // return the list
        return this;
    }

// Without Comments
 unshift(val) {
        let newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

1. Get method:

Pseudocode:

1. This function should accept an index.
2. If the index is less than zero or greater than or equal to the length of the list, return null.
3. Loop through the list until you reach the index and return the node at that specific index.

Code:

// With comments

get(index) {
        // If index Is less than zero or greater than the length of the list
        if(index < 0 || index >= this.length) return null;

        // Setting two variables *counter* and *current*
        let counter = 0;
        let current = this.head;

        // Loop through the list increase the counter until it's equal to the index passed
        while(counter !== index) {
            current = current.next;
            counter++;
        }

        // return the node at that index
        return current;
    }

// Without Comments

get(index) {
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }

1. Set method:

Pseudocode

1. This function should accept a value and an index.
2. Use the get function to find the specific node.
3. If the node is not found, return false.
4. If the node is found, set the value of that node to be the value passed to the function and return true.

Code:

// With Comments
set(index, val) {
        // Use the **get** method to find the node
        var foundNode = this.get(index);

        // If node is found then change the value, else return false
        if(foundNode) {
            foundNode.val = val;
            return true;
        }

        return false;
    }

// Without Comments
set(index, val) {
        var foundNode = this.get(index);
        if(foundNode) {
            foundNode.val = val;
            return true;
        }

        return false;
    }

1. Insert method:

Pseudocode:

1. If the index is less than zero or greater than the length, return false.
2. If the index is the same as the length, push a new node to the end of the list.
3. If the index is zero, unshift a new node to the start of the list.
4. Otherwise, using the get method, access the node at the index-1.
5. Set the property on that node to be the new node.
6. Set the next property on the new node to be the previous node.
7. Increment the length.
8. Return true.

Code:

// With Comments
insert(index, val) {
        // If index is less than zero or more than length of the list
        if(index < 0 || index > this.length) return false;

        // if index is same as the length then push the node
        // we use !! to return true/false
        if(index === this.length) return !! this.push(val);

        // if index is 0, then unshift the value
        if(index === 0) return !! this.unshift(val);

        // If value has to be inserted in between list

        // create a new node;
        let newNode = new Node(val);

        // get the previous element;
        let prev = this.get(index - 1);

        // store current previous.next property in a variable
        let temp = prev.next;

        // set new node to previous.next
        prev.next = newNode;

        // set next property on newNode to be temp;
        newNode.next = temp;

        // increment the length by 1
        this.length++;
        return true
    }

// Without Comments
insert(index, val) {

        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !! this.push(val);
        if(index === 0) return !! this.unshift(val);

        let newNode = new Node(val);
        let prev = this.get(index - 1);
        let temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;

        this.length++;
        return true
    }

1. Remove method:

Pseudocode:

1. If the index is less than zero or greater than the index, return undefined.
2. If the index is the same as the length-1, pop.
3. If the index is zero, shift.
4. Otherwise, using the get method, access the node at the index-1.
5. Set the next property on that node to be the next of the next node.
6. Decrement the length.
7. Return the value of the node removed.

Code:

// With Comments
remove(index) {
        // if Index is less than 0 or greater than length
        if(index < 0 || index >= this.length) return undefined;

        // if index is 0 then shift
        if(index === 0) return this.shift();

        // if index is length - 1 then pop
        if(index === this.length - 1) return this.pop();

        // get previous node
        var previousNode = this.get(index-1);

        // store removed node in a variable
        var removed = previousNode.next;

        // set previousNode next property to next of next 
        previousNode.next = removed.next;

        // reduce length by one
        this.length--;
        return removed;
    }

// Without Comments
remove(index) {
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();

        var previousNode = this.get(index-1);
        var removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;
        return removed;
    }