DataStructures Series — 8

N.B. This article would make more sense if you read previous articles in this series.

In case you missed last week on the data-structures series here.

We discussed the Linked List ADT and we wrote some pseudocode to implement the operations of a linked list data structure.

This week, we would be discussing a type of linked list, the Doubly Linked List

The doubly Linked List

The linked list data structure discussed last week is the singly linked list because its node linkage goes in one direction.

The doubly linked list data structure 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.

As shown in the image below

photo credit: studytonight.com

Doubly Linked List Operations:

The doubly linked lists has the same operation set as the singly linked list, some have almost the same implementation while other operations implementation differ to improve performance.

Implementation

We create a Node class that has three properties representing the different cells.

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

Now, let us create a list sequence 1 <-> 3 <->4 like we did for singly linked list:

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;

We have 2 missing in the sequence, so let us quickly insert that at position 1 (assuming the sequence is zero-indexed) and have a proper sequence:

1 → 2 → 3 → 4

insertNode (2, 1) :

Node headNode = one; // value already in memory
Node currentNode = headNode;
Node previousNode = null;
$counter = 0;
while (currentNode is not null) {
   if (counter == 1) {
       Node dataNode = new Node(previousNode, 2, currentNode);
       previousNode.nextNode = dataNode;
       currentNode.prevNode = dataNode;
       break out of current loop;
   }   
   previousNode = currentNode;
   currentNode = currentNode.nextNode;
   counter++;
}

And then we can decide to delete the three in the list so the sequence looks like this: 1 → 2 → 4

delete (3) :

Node headNode = one; // value already in memory
Node previousNode = null;
Node currentNode = headNode;
while (currentNode.nextNode is not null) {
   if (currentNode.data == 3) {
      previousNode.nextNode = currentNode.nextNode; // bypass node 3
      break out of the while loop;
   }
   previousNode = currentNode;
   currentNode = currentNode.nextNode;
}

insert (5) :

To speed up this operation, we would have an additional field to keep track of the last node and update it every time we insert a new element. This would prevent us from starting from the beginning of the sequence to insert a new element.

Node lastNode = four; // value already in memory
Node five = new Node(lastNode, 5, null);
lastNode.nextNode = five;
lastNode = five;

To delete, having the lastNode, you can get the node before the it and set its nextNode to null, unlike the singly linked list where we had to start from the head of the sequence all the way down to the last, this is one of the benefits of using the doubly linked list over the singly linked list.

delete () :

Node lastNode = five; // value already in memory
Node previousNode = lastNode.prev;
previousNode.next = null;

get (2) :

Similar to delete at position, we loop through the sequence and look for a node with value 2 and return the Node.

In summary, the doubly linked list has a faster way of deleting nodes than the singly linked list. when designing algorithms, it is important to know the operations that would happen frequently and choose a data structure based on that to increase the performance of the algorithm.

Next week, we would be discussing another type of linked list and discuss some applications of the linked list data structure in general.

REFERENCES:

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