DataStructures Series #8 – The Doubly LinkedList DataStructure

Originally posted on my medium page: https://medium.com/@otarutunde

The Doubly LinkedList Datastructure

The doubly linkedList datastructure is a variation of the linkedList datastructure (Implementation of a List ADT), unlike the singly LinkedList datastructure , the doubly linkedList datastructure flows in both direction. Each node has three cells:

• One contains the address of the previous node
• One contains the data
• One contains the address of the next node.

Doubly Linked List Operations:

• Insert (data, position)
• Delete (data)
• Get (data)
• Insert (data)

Insert (data, position) — This will insert a node having the data at the specified position in the list

Delete (data) — This will delete the last node having the data in the list

Get (data) — This fetches the node having the data from the list sequence

Insert (data)— This will add a new node having the data to the end of the list

Implementation

The approach here is to create a class representing a node with its following properties.

Below is a pseudocode implementation for creating a list of 1 <–> 3 <–> 4:

Class Node {

  Node prevNode = null;
  int data = null;
  Node nextNode = null;
  
  class_constructor(prevNode, data, nextNode) {
     this.nextNode = nextNode;
     this.data = data;
     this.prevNode = prevNode;
  }

}

Node four = new Node(null, 4, null);
Node three = new Node(null, 3, four);
Node one = new Node(null, 1, three);
three.prevNode = one;
four.prevNode = three;

Insert a Node with data value 2 at position 1 (zero indexed) so the new sequence becomes 1 <–> 2 <–> 3 <–> 4:

InsertNode (2, 1)

Node prevNode = null;
Node currentNode = one;
listCurrentPosition = 0;

while (currentNode is not null) {
   if (listCurrentPosition == 1) {
       Node dataNode = new Node(prevNode, 2, currentNode);
       prevNode.nextNode = dataNode;
       currentNode.prevNode = dataNode;
       break out of current loop;
   }   
   prevNode = currentNode;
   currentNode = currentNode.nextNode;
   listCurrentPosition++;
}

Delete node with data 3 in the list so the sequence becomes 1 <–> 2 <–> 4:

delete (3)

Node currentNode = one;
prevNode = null;
while (currentNode.nextNode is not null) {
   if (currentNode.data == 3) {
      Node node = currentNode.nextNode;
      prevNode.nextNode = node;
      node.prevNode = prevNode;
      break out of the while loop;
   }
   prevNode = currentNode;
   currentNode = currentNode.nextNode;
}

Get node having data 2:

Get (2)

Node currentNode = one;
while (currentNode.nextNode is not null) {
   if (currentNode.data == 2) {
      return currentNode;
   }
   currentNode = currentNode.next;
}

Insert node having data 5 into the list so the sequence becomes 1 <–> 2 <–> 4 <–> 5:

Insert (5)

Node currentNode = four;
Node five = new Node(four, 5, null);
four.nextNode = five;

Real life Applications

• A two way music playlist — Music playlists with forward and backward buttons.

• A browser web history — Navigating a web browser history

REFERENCES:

• https://en.wikipedia.org/wiki/Linked_list