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:
One thought on “DataStructures Series #8 – The Doubly LinkedList DataStructure”
Comments are closed.