JavaScript Comprehensive Linked List

gistfile1.txt

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

class LinkedList {
    constructor(value) {
        const newNode = new Node(value);
        this.head = newNode;
        this.tail = this.head;
        this.length = 1;
    }

    printList() {
        let temp = this.head;
        while (temp !== null) {
            console.log(temp.value);
            temp = temp.next;
        }
    }

    getHead() {
        if (this.head === null) {
            console.log("Head: null");
        } else {
            console.log("Head: " + this.head.value);
        }
    }

    getTail() {
        if (this.tail === null) {
            console.log("Tail: null");
        } else {
            console.log("Tail: " + this.tail.value);
        }
    }

    getLength() {
        console.log("Length: " + this.length);
    }

    push(value) {
        const newNode = new Node(value);
        if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }

    pop() {
        if (this.length === 0) return undefined;
        let temp = this.head;
        let pre = this.head;
        while (temp.next) {
            pre = temp;
            temp = temp.next;
        }
        this.tail = pre;
        this.tail.next = null;
        this.length--;

        // Edge case: if there is zero node in list after length--
        if (this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        return temp;
    }
    unshift(value) {
        const newNode = new Node(value);
        if (this.length === 0 || !this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

    shift() {
        if (this.length === 0) return undefined;
        let temp = this.head;
        this.head = this.head.next;
        this.length--;
        if (this.length === 0) {
            this.tail = null;
        }
        return temp;
    }

    get(index) {
        if (index < 0 || index >= this.length) return undefined;
        let temp = this.head;
        for (let i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    set(index, value) {
        let tmp = this.get(index);
        if (tmp) {
            tmp.value = value;
            return true;
        }
        return false;
    }

    insert(index, value) {
        // If its beginning or end, use unshift or push
        if (index === 0) return this.unshift(value);
        if (index === this.length) return this.push(value);

        // If its out of bounds, return false
        if (index < 0 || index > this.length) return false;

        // If its in the middle
        // get the previous node and set the next node to the new node
        const newNode = new Node(value);
        const temp = this.get(index - 1);

        newNode.next = temp.next;
        temp.next = newNode;
        this.length++;

        return true;
    }

    remove(index) {
        // If its beginning or end, use shift or pop
        if (index === 0) return this.shift();
        if (index === this.length - 1) return this.pop();

        // If its out of bounds, return false
        if (index < 0 || index >= this.length) return undefined;

        // if its in the middle
        const temp = this.get(index);
        const before = this.get(index - 1);
        before.next = temp.next;
        temp.next = null;
        this.length--;
        return temp;
    }

    reverse() {
        // swap head and tail
        let temp = this.head;
        this.head = this.tail;
        this.tail = temp;

        // reverse the list
        let next = temp.next;
        let prev = null;
        for (let i = 0; i < this.length; i++) {
            next = temp.next;
            temp.next = prev;
            prev = temp;
            temp = next;
        }

        return this;
    }

    // Find Middle Node if `length` is not available 
    findMiddleNode() {
        // Handle edge case: empty list
        if (this.head === null) {
            return null;
        }
        
        // Initialise both pointers at head
        let slow = this.head;
        let fast = this.head;
        
        // Tortoise and Hare algorithm
        // Slow moves 1 step, fast moves 2 steps
        while (fast !== null && fast.next !== null) {
            slow = slow.next;        // Move slow pointer 1 step
            fast = fast.next.next;   // Move fast pointer 2 steps
        }
        
        return slow;
    }
}


function test() {
    let myLinkedList = new LinkedList(4);

    myLinkedList.getHead();
    myLinkedList.getTail();
    myLinkedList.getLength();
    console.log("\nLinked List:");
    myLinkedList.printList();

    /*
        EXPECTED OUTPUT:
        ----------------
        Head: 4
        Tail: 4
        Length: 1
        
        Linked List:
        4
        
        null
        
        null
    */
}

function testPop() {
    /* 
    For POP
    */
    let myLinkedList = new LinkedList(1);
    myLinkedList.push(2);

    // (2) Items in LL - Returns 2 Node
    if (myLinkedList.length !== 0) {
        console.log(myLinkedList.pop().value);
    } else {
        console.log("null");
    }

    // (1) Item in LL - Returns 1 Node
    if (myLinkedList.length !== 0) {
        console.log(myLinkedList.pop().value);
    } else {
        console.log("null");
    }

    // (0) Items in LL - Returns null
    if (myLinkedList.length !== 0) {
        console.log(myLinkedList.pop().value);
    } else {
        console.log("null");
    }
}

function testUnshift() {
    let myLinkedList = new LinkedList(2);
    myLinkedList.push(3);

    console.log("Before unshift():");
    console.log("-----------------");
    myLinkedList.getHead();
    myLinkedList.getTail();
    myLinkedList.getLength();

    console.log("\nLinked List:");
    myLinkedList.printList();

    myLinkedList.unshift(1);

    console.log("\nAfter unshift():");
    console.log("----------------");
    myLinkedList.getHead();
    myLinkedList.getTail();
    myLinkedList.getLength();

    console.log("\nLinked List:");
    myLinkedList.printList();

    /*
    EXPECTED OUTPUT:
    ----------------
    2
    1
    null

    */
}

function testShift() {

    let myLinkedList = new LinkedList(2);
    myLinkedList.push(1);

    // (2) Items in LL - Returns 2 Node
    if (myLinkedList.length !== 0) {
        console.log(myLinkedList.shift().value);
    } else {
        console.log("null");
    }

    // (1) Item in LL - Returns 1 Node
    if (myLinkedList.length !== 0) {
        console.log(myLinkedList.shift().value);
    } else {
        console.log("null");
    }

    // (0) Items in LL - Returns null
    if (myLinkedList.length !== 0) {
        console.log(myLinkedList.shift().value);
    } else {
        console.log("null");
    }


    /*
        EXPECTED OUTPUT:
        ----------------
        2
        1
        null
    
    */
}

function testGet() {

    let myLinkedList = new LinkedList(0);
    myLinkedList.push(1);
    myLinkedList.push(2);
    myLinkedList.push(3);

    console.log(myLinkedList.get(3).value);

    /*
        EXPECTED OUTPUT:
        ----------------
        3
    
    */
}

function testSet() {



    let myLinkedList = new LinkedList(0);
    myLinkedList.push(1);
    myLinkedList.push(2);
    myLinkedList.push(3);

    console.log("Linked List before set():");
    myLinkedList.printList();

    myLinkedList.set(2, 99);

    console.log("\nLinked List after set():");
    myLinkedList.printList();



    /*
        EXPECTED OUTPUT:
        ----------------
        Linked List before set():
        0
        1
        2
        3
        
        Linked List after set():
        0
        1
        99
        3
    
    */
}

function testInsert() {



    let myLinkedList = new LinkedList(1);
    myLinkedList.push(3);

    console.log("LL before insert():");
    myLinkedList.printList();

    myLinkedList.insert(1, 2);

    console.log("\nLL after insert(2) in middle:");
    myLinkedList.printList();

    myLinkedList.insert(0, 0);

    console.log("\nLL after insert(0) at beginning:");
    myLinkedList.printList();

    myLinkedList.insert(4, 4);

    console.log("\nLL after insert(4) at end:");
    myLinkedList.printList();


    /*
        EXPECTED OUTPUT:
        ----------------
        LL before insert():
        1
        3
    
        LL after insert(2) in middle:
        1
        2
        3
    
        LL after insert(0) at beginning:
        0
        1
        2
        3
    
        LL after insert(4) at end:
        0
        1
        2
        3
        4
    
    */
}

function testRemove() {

    let myLinkedList = new LinkedList(1);
    myLinkedList.push(2);
    myLinkedList.push(3);
    myLinkedList.push(4);
    myLinkedList.push(5);

    console.log("LL before remove():");
    myLinkedList.printList();

    console.log("\nRemoved node:");
    console.log(myLinkedList.remove(2).value);
    console.log("LL after remove() in middle:");
    myLinkedList.printList();

    console.log("\nRemoved node:");
    console.log(myLinkedList.remove(0).value);
    console.log("LL after remove() of first node:");
    myLinkedList.printList();

    console.log("\nRemoved node:");
    console.log(myLinkedList.remove(2).value);
    console.log("LL after remove() of last node:");
    myLinkedList.printList();


    /*
        EXPECTED OUTPUT:
        ----------------
        LL before remove():
        1
        2
        3
        4
        5
    
        Removed node:
        3
        LL after remove() in middle:
        1
        2
        4
        5
    
        Removed node:
        1
        LL after remove() of first node:
        2
        4
        5
    
        Removed node:
        5
        LL after remove() of last node:
        2
        4
    
    */
}

function testReverse() {




    let myLinkedList = new LinkedList(1);
    myLinkedList.push(2);
    myLinkedList.push(3);
    myLinkedList.push(4);

    console.log("LL before reverse():");
    myLinkedList.printList();

    myLinkedList.reverse();

    console.log("\nLL after reverse():");
    myLinkedList.printList();


    /*
        EXPECTED OUTPUT:
        ----------------
        LL before reverse():
        1
        2
        3
        4
        
        LL after reverse():
        4
        3
        2
        1
    
    */
}


// testShift();
test();