Linked List

The following are my notes regarding Linked List:

Singly Linked List:

node has pointer to the next node
head ... tail
can only be traversed forward

Doubly Linked List:

node has pointer to the next node AND the previous node
head ... tail
can only be traversed forward and backwards

Circular linked list:
header and tail point to each other

Array vs linked list:
1. Memory:
array support direct access (elements are contiguous block of memory)
Linked list support sequential access (elements can be store anywhere in memory) to access a particular element of the list you have to step-through each node in the list.
because elements are distributed in memory, adding/removing elements is faster than arrays

2. Benefits: If you have a very volatile data set that is constantly changing, its best to use linked list because it will always take the same amount of time to add or delete an element in the list.

The following a JavaScript class to build a link list using Node.js (see the video at the bottom of this page)

// initialize the list
class Node {
    constructor(_value, _prev, _next) {
        this.value = _value;
        this.prev = _prev || null; // or set default value to null if prev reference is got given
        this.next = _next || null; // or set default value to null if next reference is got given
    }
}
class LinkedList {
    constructor(_head = null, _tail = null) { // set default to null
        // Option: No parameters in constructor().. you can use the next line to declare both the tail and head as default of null
        // this.head = this.tail = null;
        this.head = _head; // initial set default value to null
        this.tail = _tail; // initial set default value to null
    }
    // add to end of list (tail)
    append(value) {
        // check if list is empty by checking if tail is empty
        if (!this.tail) {
            //initialize head and tail to new value
            this.head = this.tail = new Node(value);
        } else {
            let oldTail = this.tail; // temporarily save the old tail
            this.tail = new Node(value); // set tail to the new value
            oldTail.next = this.tail; // set the new tail as the next node from the last tail
            this.tail.prev = oldTail; // set the prev node as the old tail to the new tail
        }
    }
    // add to begining of list (head)
    prepend(value) {
        if (!this.head) {
            this.head = this.tail = new Node(value);
        } else {
            let oldHead = this.head;
            this.head = new Node(value);
            this.head.next = oldHead;
            oldHead.previous = this.head;
        }
    }
    //
    deleteHead(value) {
        if (!this.head) {
            return null;
        } else {
            let removedHead = this.head;
            // check if this is the last node in the list
            if (this.head === this.tail) {
                this.head = this.tail = null; // set head and tail to null
            } else {
                // set the next as the head
                this.head = this.head.next;
                // set head pre as null
                this.head.pre == null;
            }
            return removedHead.value;
        }
    }
    //
    deleteTail() {
        // check if list if empty, if so, return null, nothing to do
        if (!this.tail) {
            return null;
        } else {
            // set previous node from tail
            let removeTail = this.tail;
            // check if this is the last node (1 node left)
            if (this.head === this.tail) {
                this.head = this.tail = null; // set head and tail to null
            } else {
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
            return removeTail.value;
        }
    }
    search(value) {
        // travers list
        // start at the head node
        let currentNode = this.head;
        while (value) {
            // if the current value matches the searched value, return the current node
            if (currentNode.value === value) {
                return currentNode;
            } {
                // keep traversing through the list, and to the next node
                currentNode = currentNode.next;
            }
            // return null if searched valued is not found
            return null;
        }
    }
}

let list = new LinkedList();
list.append(1)
list.append(2)
list.append(3)
list.prepend(0)
list.prepend(-1)
list.search(1)
list.search(3)
list.search(999)
list.deleteHead() // -1
list.deleteTail() // 3
list.deleteTail() // 2
list.deleteHead() // 0
list.deleteHead() // 1
list.deleteTail() // null
console.log(list);


t2CEgPsws3U