Doubly Linked Lists.


Introduction to Doubly linked list(DLL):-

In my previous article about singly linked list i have explained about it thoroughly. Doubly linked list is not different from it except for the fact that each node will have address to next node and address to previous node along with data. Since there are two links this data structure is called Doubly linked list. By using this additional link to previous node we will be able to traverse from the head node to the tail node and tail node to head node. Since we are storing an additional node memory consumption will be more.

For example, consider¬†a bunch of train cars connected to each other where one car connects to the next one and that one connects¬†to the next one.¬†But there is no index that we use to access data in the car. So We’ve just started the first one and then moved to the second one moved to the third one moved to the¬†fourth and then moved to the fifth and so on till the last car. Once the very last car is reached again you have to start from the first car and follow a similar process.

Doubly linked list terminologies:-

In a Doubly linked list, every element is called a node. So a doubly linked list consists of a bunch of nodes. Each and every node in the doubly linked list consists of three entries.

  1.  Data.
  2. Address to the next node represented with next.
  3. Address to the previous node represented with previous.

If the node is the last node then the address to the next node. i.e it could be represented as per our wish either by storing null or -1 etc. Along with this, The previous values of head node can also be represented by -1 or null as it does not contain any data in-front of it.Besides this, The very first node in the doubly linked list is called as the head node. The last node is called the tail node.

While implementing we don’t keep track of every single node in the linked list. Rather we keep track of 3 nodes. They are¬†

  1. Head node.
  2. Tail node.
  3. The total length of the linked list etc. i.e number of nodes in DLL.

By keeping track of the head and from the head we can figure out the next one. And from there we can figure out the next one all the way until the end. And then also we keep track full length to make things easier.

Doubly linked list representation.

Defining a Node:-

Okay, we have seen enough theory. let’s start writing our code. let’s start by defining a class for each node. It just stores a piece of data which we’ll call it value and then it stores a reference to next node which we’ll call next and another value previous to store the previous node. So let’s define our class and call it Node.

class
 Node {
    Object value;
    Node next; Node previous;
    
public Node(Object value) {
        
super();
        
this.value = value; this.next= null; this.previous= null;
    }
}
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.previous = null;
    }
}

Defining a Doubly Linked List:-

As we have discussed above a doubly linked list consists of head node, tail node, and length of the doubly linked list. So By using the node above a doubly linked list can be defined as shown below.

In the above example code observe that in the constructor we have set head and rail to null and length of the list to 0. This is because we will not have any data when we initialize the doubly linked list.

public class DoublyLinkedList {
    public Node head;
    public Node tail;
    public int length;
    public SinglyLinkedList() {
        super();
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}
class DoublyLinkedList {
    constructor() {
        this.length = 0;
        this.head = null;
        this.tail = null;
    }
}

In the above example code observe that in the constructor we have set head and tail to null and length of the list to 0. This is because we will not have any data when we initialize the doubly linked list.

Operations on Doubly Linked List:-

1. Push:- 

Push operation adds a new node at the end of the doubly linked list i.e to the tail node.
Doubly linked list push illustration.
But remember that when we push the first node we have to add an additional check for the null condition as the head, tail are null after the initializing it.
The pseudocode for push operation is as shown below.
Doubly linked list push pseudocode.
 
 Implementation is as shown below.
public DoublyLinkedList push(Object value) {
        Node newNode = new Node(value);
        if (this.length == 0) {
            this.head = newNode;
            this.tail = newNode;
        }
        else {
            this.tail.next = newNode;
            newNode.previous = this.tail;
            this.tail = newNode;
        }
        this.length += 1;
        return this;
    }
push(value) {
        var newNode = new Node(value)
        if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        }
        else {
            this.tail.next = newNode;
            newNode.previous = this.tail;
            this.tail = newNode;
        }
        this.length += 1;
        return this;
    }

The time complexity of the push operation is O(1) as we are adding a new node to the tail node and is available on variable tail.

2. Pop:-

Pop operation is used to remove the last node in the doubly linked list.
Doubly linked list pop illustration.
Even though we have access to the tail node we cant directly make it null. Because we need to update the tail value to the last but one node and reduce the length by 1.
The pseudocode for the pop operation is as shown below.
Doubly linked list pop pseudocode.

Implementation of pop operation is as shown below.

public Node pop() {
        if (this.length == 0) {
            return null;
        }
        else if (this.length == 1) {
            this.head = null;
            this.tail = null;
            this.length -= 1;
            return this.head;
        }
        else {
            Node currentTail = this.tail;
            Node newTail = currentTail.previous;
            currentTail.previous = null;
            newTail.next = null;
            this.tail = newTail;
            this.length -= 1;
            return currentTail;
        }
    }
pop() {
        if (this.length === 0) {
            return null;
        }
        else if (this.length === 1) {
            this.head = null;
            this.tail = null;
            this.length -= 1;
            return this.head;
        }
        else {
            var currentTail = this.tail;
            var newTail = currentTail.previous;
            currentTail.previous = null;
            newTail.next = null;
            this.tail = newTail;
            this.length -= 1;
            return currentTail;
        }
    }

The time complexity of the pop operation is O(1) as we have to traverse from tail and make last but one node next value to null.

3. Shift:-

Shift operation is used for removing the first element from a doubly linked list.
Doubly linked list shift illustration.
The Pseudocode for shift operation as explained below.
 
Doubly linked list shift pseudocode.
public Node shift() {
        if (this.length == 0) {
            return null;
        }
        if (this.length == 1) {
            this.head = null;
            this.tail = null;
            this.length -= 1;
            return null;
        }
        else {
            Node currentHead = this.head;
            Node newHead = currentHead.next;
            newHead.previous = null;
            currentHead.next = null;
            this.head = newHead;
            this.length -= 1;
            return currentHead;
        }
    }
shift() {
        if (this.length === 0) {
            return null;
        }
        if (this.length === 1) {
            this.head = null;
            this.tail = null;
            this.length -= 1
            return null;
        }
        else {
            var currentHead = this.head;
            var newHead = currentHead.next;
            newHead.previous = null;
            currentHead.next = null;
            this.head = newHead;
            this.length -= 1
            return currentHead;
        }
    }

The time complexity of shift operation is O(1) as we remove the head by updating the head.next value as new head. But remember to update the latest head nodes previous value to null.

4. Unshift:-

Unshift operation is used to add a new node in-front of the existing head node. 
Doubly linked list unshift illustration.
Pseudocode for the unshift operation is as shown in the below image.
 
Doubly linked list unshift pseudocode.
Implementation is as shown below.
public DoublyLinkedList unshift(Object value) {
        if (this.length == 0) {
            this.push(value);
            return this;
        }
        else {
            Node newNode = new Node(value);
            Node currentHead = this.head;
            currentHead.previous = newNode;
            newNode.next = currentHead;
            this.head = newNode;
            this.length += 1;
            return this;
        }
    }
unshift(value) {
        if (this.length === 0) {
            this.push(value);
            return this;
        }
        else {
            var newNode = new Node(value);
            var currentHead = this.head;
            currentHead.previous = newNode;
            newNode.next = currentHead;
            this.head = newNode;
            this.length += 1;
            return this;
        }
    }

As we are just adding a new node at the beginning of doubly linked all we have to do is create a new node and make next value of new node to current head. So the time complexity can be generalized as O(1).

5. get:-

Get operation is used to get the element at a given position. 
Pseudocode for the given operation is described below.
Doubly linked list get pseudocode.

 

The implementation as follows.

public Node get(int index) {
        if (index < 0 || index >= this.length) {
            return null;
        }
        double middleLength = Math.floor(index / 2);
        if (index <= middleLength) {
            int counter = 0;
            Node current = this.head;
            while (counter != index) {
                current = current.next;
                counter++;
            }
            return current;
        }
        else {
            int counter = this.length - 1;
            Node current = this.tail;
            while (counter != index) {
                current = current.previous;
                counter--;
            }
            return current;
        }
    }
get(index) {
        if (index < 0 || index >= this.length) {
            return null;
        }
        var middleLength = Math.floor(index / 2);
        if (index <= middleLength) {
            var counter = 0;
            var current = this.head;
            while (counter !== index) {
                current = current.next;
                counter++;
            }
            return current;
        }
        else {
            var counter = this.length - 1;
            var current = this.tail;
            while (counter !== index) {
                current = current.previous;
                counter--;
            }
            return current;
        }
    }

As observed in the above logic, To get a value at a given position we have to repeat a loop that half the length of doubly linked list. So the time complexity can be represented as O(n/2).

6. set:-

The set operation is used for updating the value at a particular node. 
The process involves traversing the doubly linked list until a specified node and replacing the value at that with the new value provided. So pseudocode is as shown in the following picture.
 
Doubly linked list set pseudocode.
 
public boolean set(int index, Object value) {
        Node node = this.get(index);
        if (node != null) {
            node.value = value;
            return true;
        } else {
            return false;
        }
    }
set(index, value) {
        var node = this.get(index);
        if (node) {
            node.val = value
            return true;
        } else {
            return false;
        }
    }

7. Insert:-

As part of insert operation we will insert a new node a specific position as requested by the user. 
Doubly linked list insert illustration.

The logic we need to follow is as described below.

Doubly linked list insert pseudocode
public boolean insert(int index, Object value) {
        if (index < 0 || index > this.length) {
            return false;
        }
        if (index == 0) {
            this.unshift(value);
            return true;
        }
        if (this.length == index) {
            this.push(value);
            return true;
        }
        Node newNode = new Node(value);
        Node nthNode = this.get(index - 1);
        nthNode.next = newNode;
        newNode.next = nthNode.next;
        nthNode.next.previous = newNode;
        newNode.previous = nthNode;
        this.length += 1;
        return true;
    }
insert(index, value) {
        if (index < 0 || index > this.length) {
            return false;
        }
        if (index === 0) {
            this.unshift(value);
            return true;
        }
        if (this.length === index) {
            this.push(value);
            return true;
        }
        var newNode = new Node(value);
        var nthNode = this.get(index - 1);
        nthNode.next = newNode;
        newNode.next = nthNode.next;
        nthNode.next.previous = newNode;
        newNode.previous = nthNode;
        this.length += 1;
        return true;
    }

The best case time complexity of doubly linked list for insert operation is O(1). This occurs when there is none or one element in it. But for worst-case scenario, we have traverse till kth position and insert a new node. Since we are using get method in insertion process, The time complexity can be represented as O(n/2).

8. Remove:-

As the name suggests, Remove operation is used for removing a node at a given index. 

Doubly linked list remove illustration.

The logic behind it is very similar to inserting a new node. But we update the next and previous values as discussed in the pseudocode.

Doubly linked list remove pseudocode.
public Node remove(int index) {
        if (index < 0 || index > this.length) {
            return null;
        }
        if (index == 0) {
            return this.shift();
        }
        if (index == this.length - 1) {
            Node pop = this.pop();
            return pop;
        }
        else {
            Node nthNode = this.get(index);
            nthNode.previous.next = nthNode.next;
            nthNode.next.previous = nthNode.previous;
            nthNode.next = null;
            nthNode.previous = null;
            this.length -= 1;
            return nthNode;
        }
    }
remove(index) {
        if (index < 0 || index > this.length) {
            return null;
        }
        if (index === 0) {
            return this.shift();
        }
        if (index === this.length - 1) {
            var pop = this.pop();
        }
        else {
            var nthNode = this.get(index);
            nthNode.previous.next = nthNode.next;
            nthNode.next.previous = nthNode.previous;
            nthNode.next = null;
            nthNode.previous = null;
            this.length -= 1;
            return nthNode;
        }
    }

The best case time complexity of doubly linked list for removal operation is O(1). This occurs when there is only one element in it. But for worst-case scenario, we have traverse till kth position and remove an existing node. Since we are using get method in removal process, The time complexity can be represented as O(n/2).

Applications of doubly linked list:-

Applications of doubly linked list are similar to the singly linked list such as implementation music players, image viewers, browser next and previous buttons, undo and redo functionalities etc.
Disadvantages of doubly linked lists:-

  1. As nodes are created randomly in the memory, the process of reading them is time consuming.
  2. Memory consumption is more as additional link to previous node is maintained at every node.

That’s all about doubly linked lists. Thanks for reading. Stay tuned for more.