Doubly Linked List in Javascript (Data Structures)

Almost identical to the singly-linked lists, except every node has another pointer, to the previous node. It provides more flexibility over singly-linked lists.

Todos:

1. Push and Pop

2. Unshift and Shift

3. Get and Set

4. Insert and Remove

Creating a Node: It contains a value and two pointers next, prev.

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

Doubly Linked List: three important things - head, tail, length

// Doubly Linked List
class DoublyLinkedList {
    constructor() {
        this.head = head;
        this.tail = tail;
        this.length = 0;
    }
}

Push: Adding a node to the end of the doubly linked list

1. This function will accept a value. Create a new node with the value passed to the function.

2. If the head property is null, then set the head and tail to be the new node.

3. If not, set the next property on the tail of DLL to that node.

4. Set the previous property on the new node to be the tail.

5. Set the tail to be the newly created node.

6. Increment the length of the DLL by one.

7. Return DLL.

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

Pop: removing a node from the end of the DLL.

1. If there is no head, return undefined.

2. Store the current tail in a variable to return later.

3. If length is one, set the head and tail to be null;

4. Update the tail to be the previous node.

5. Set the new tail’s next value to null.

6. Decrement the length by one.

7. Return the removed value.

    // pop
        pop() {
            if(!this.head) return undefined;
   
            let poppedItem = this.tail;
            if(this.length === 1) {
                this.head = null;
                this.tail = null;
            } else {
                this.tail = poppedItem.prev;
                this.tail.next = null;
                poppedItem.prev = null;
            }
   
            this.length--;
            return poppedItem;
        }
   

Unshift: adding a new node to the beginning of the DLL.

1. This function should accept a value and create a new node using that value.

2. If the length of the DLL is zero, set the head and tail to be the new node.

3. Otherwise,

• Set the prev property on the head of the list to be the new node.

• Set the next property on the new node to the current head.

• Update the head of the DLL to be the newly created node.

4. Increment the length by one.

5. Return the list.

// Unshift
    unshift(val) {
        let newNode = new Node(val);

        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }

        this.length++;
        return this;
    }

Shift: removing a node from the beginning of the DLL.

1. If length is zero, return undefined.

2. Store the value of the head in a variable.

3. If length is one, set the head and tail to null.

4. Update the head to be the next of the old head.

5. Set the head's previous property to null.

6. Set the old heads next to null.

7. Decrement the length by one.

8. Return old head.

    // Shift
        shift() {
            if(this.length === 0) return undefined;
            let oldHead = this.head;
            if(this.length === 1) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = oldHead.next;
                this.head.prev = null;
                oldHead.next = null;
            }
   
            this.length--;
            return oldHead;
        }
   

Get: accessing a node in a DLL.

1. This function will accept an index. If the index is less than 0 (zero) or ≥ (gte) to the length, return null.

2. If the index is ≤ (lte) half of the length of the list.

• Loop through the list starting from the head and loop towards the middle.

• Return the node once it's found.

3. If the index is ≥ (gte) half of the length of the list.

• Loop through the list starting from the tail and loop towards the middle.

• Return the node once it is found.

    // get
        get(index) {
            if(index < 0 || index >= this.length) return null;
            if(index <= this.length / 2) {
                let count = 0;
                let current = this.head;
                while(count !== index) {
                    current = current.next;
                    count++;
                }
                return current;
            } else {
                let count = this.length - 1;
                var current = this.tail;
                while(count !== index) {
                    current = current.prev;
                    count--;
                }
  
                return current;
            }
        }
  

Set: replacing the value of the node to the index in a DLL.

1. Create a variable which is the result of the get method at the index passed to the function.

• If the get method returns a valid node, set the value of that node to be the value passed to the function.

• Return true.

2. Otherwise, return false.

set(index, value) {
    let foundNode = this.get(index);
    if(foundNode !== null) {
        foundNode.val = val;
        return true;
    }
    return false;
}

Insert: adding a node in a DLL at a certain position.

1. If the index is less than zero or ≥ (gte) the length return false.

2. If the index is zero, unshift.

3. If the index is the same as the length, push.

4. Use the get method to access the index-1.

5. Set the next and prev property on the correct nodes to link everything together.

6. Increment the length by one.

7. return true.

    // Insert 
        insert(index, val) {
            if(index < 0 || index > this.length) return false;
            if(index === 0) return this.unshift(val); // return will give true/false
            if(index === this.length) return this.push(val);
   
            let newNode = new Node(val);
            let prevNode = this.get(index-1);
            let nextNode = prevNode.next;
   
            prevNode.next = newNode;
            newNode.prev = prevNode;
            newNode.next = nextNode;
            nextNode.prev = newNode;
   
            this.length++;
            return true;
   
        }
   

Remove: removing a node in the DLL from a certain position.

1. If the index is less than 0 or ≥ (gte) the length return undefined.

2. If the index is zero, shift.

3. If the index is the same as the length-1, pop.

4. Use the get method to retrieve the item to be removed.

5. Update the next and previous properties to remove the found node from the list.

6. Set next and previous to null on the found node.

7. Decrement the length by one.

8. Return the removed node.

    // remove
        remove(index) {
            if(index < 0 || index >= this.length) return undefined;
            if(index === 0) return this.shift();
            if(index === this.length - 1) return this.pop();
   
            let removedNode = this.get(index);
            let prevNode = removedNode.prev;
            let nextNode = removedNode.next;
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
   
            removedNode.next = null;
            removedNode.prev = null;
   
            this.length--;
            return removedNode;
        }
   

---

Time Complexity of Doubly Linked List:

• Access: O(N)

• Search: O(N)

• Insertion: O(1)

• Removal: O(1)

---

Summary:

1. Almost identical to SLL except there is an additional pointer to the previous node.

2. Better at finding nodes and can do it in half time compared to SLL.

3. They need more memory considering the extra pointer.