A Doubly Linked List is a linear data structure which collectively represents a sequence of data in which each node has three parts.
In this tutorial, we will learn about the implementation of a doubly linked list and various operations on it like insertion, deletion and traversal of a Doubly Linked List and it's advantages and disadvantages over Singly Linked List.
A Doubly Linked List is a collection of nodes in which each node has three
parts i.e, pointer to previous node
,
data
and
pointer to next node
and last node points
to null
.
We have to create a data structure or Node which contains three part i.e, first part contains address of previous node, second part contains data of the node and third node contains address of next pointer. We can create this by using user defined data type (depends on the programming language used).
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None
class Node {
constructor(data) {
this.prev = null;
this.data = data;
this.next = null;
}
}
Traversing means visiting all the node once i.e, we want to read all the
data available in the doubly linked list.
We can do so by visiting all the nodes one by one and reading the data
available in each node.
Simply, use a temporary variable and initialize it with the head node so
that we can start with the begining of the list and then go through all
the nodes one by one till the last node is reached. And we can get the
last node by checking the next value of node i.e., if next value of node
is
null
then this is the end of node.
def traverse(self):
if self.head:
temp = self.head
while temp:
print(temp.data)
temp = temp.next
else:
print(None)
traverse() {
if (this.head) {
let temp = this.head;
while (temp) {
console.log(temp.data);
temp = temp.next;
}
} else {
console.log(null);
}
}
Reverse traversing means visiting all the node once from the backward
direction i.e, we want to read all the data available in the doubly linked
list from the tail.
We can do so by visiting all the nodes one by one and reading the data
available in each node.
Simply, use a temporary variable and initialize it with the tail node so
that we can start with the end of the list and then go through all the
nodes one by one till the first node is reached. And we can get the first
node by checking the next value of node i.e., if next value of node is
null
then this is the begining of node.
def reverse_traverse(self):
if self.tail:
temp = self.tail
while temp:
print(temp.data)
temp = temp.prev
else:
print(None)
reverseTraverse() {
if (this.tail) {
let temp = this.tail;
while (temp) {
console.log(temp.data);
temp = temp.prev;
}
} else {
console.log(null);
}
}
To find length of a linked list we can simply use a temporary variable and initialize it by assigning the head node. Now, move it to every node one by one and increase the counter variable.
def length(self):
temp = self.head
count = 0
while temp:
count += 1
temp = temp.next
return count
length() {
let temp = this.head;
let count = 0;
while (temp) {
count++;
temp = temp.next;
}
return count;
}
Insertion in a Linked List can be done in following three ways:
While inserting a node at the begining position, two situation may arise:
def insert_at_start(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
insertAtStart(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
}
While inserting a node at the end position, two situation may arise:
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
insertAtEnd(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
}
While inserting at any given position following 3 situation may arise based on user input:
given position - 1
and then insert
the new node by adjusting the previous and next pointer.
def insert_at_position(self, pos, data):
new_node = Node(data)
if pos < 0 or pos > self.length():
raise Exception('Enter a valid postion')
else:
if pos == 0:
self.insert_at_start(data)
elif pos == self.length()-1:
self.insert_at_end(data)
else:
temp = self.head
for _ in range(pos-1):
temp = temp.next
new_node.next = temp.next
temp.next = new_node
new_node.prev = temp
insertAtPosition(pos, data) {
const newNode = new Node(data);
if (pos < 0 || pos > this.length()) {
throw "Enter a valid position";
} else {
if (pos == 0) {
this.insertAtStart(data);
} else if (pos == this.length() - 1) {
this.insertAtEnd(data);
} else {
let temp = this.head;
for (let i = 0; i < pos - 1; i++) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
newNode.prev = temp;
}
}
}
Same as insertion deletion in a Linked List can be done in 3 ways:
While deleting a node at the from begining, two situation may arise:
null
null
to the new
previous part of new head node.
def delete_from_start(self):
if self.head:
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
else:
data = self.head.data
self.head = self.head.next
self.head.prev = None
return data
else:
raise Exception('Empty linked list')
deleteFromStart() {
if (this.head) {
let data;
if (this.head === this.tail) {
data = this.head.data;
this.head = this.tail = null;
} else {
data = this.head.data;
this.head = this.head.next;
this.head.prev = null;
}
return data;
} else {
throw "Empty Linked List";
}
}
While deleting a node at the from the end, two situation may arise:
null
null
to
the next part of new tail node.
def delete_from_end(self):
if self.head:
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
else:
data = self.tail.data
self.tail = self.tail.prev
self.tail.next = None
return data
else:
raise Exception('Empty linked list')
deleteFromEnd() {
if (this.head) {
let data;
if (this.head === this.tail) {
data = this.head.data;
this.head = this.tail = null;
} else {
data = this.tail.data;
this.tail = this.tail.prev;
this.tail.next = null;
}
return data;
} else {
throw "Empty Linked List";
}
}
While deleting at any given position following 3 situation may arise based on user input:
def delete_at_position(self, pos):
if pos < 0 or pos >= self.length():
raise Exception('Enter a valid postion')
else:
if pos == 0:
return self.delete_from_start()
elif pos == self.length()-1:
return self.delete_from_end()
else:
temp = self.head
for _ in range(pos):
temp = temp.next
data = temp.data
prev_node = temp.prev
prev_node.next = temp.next
temp.next.prev = prev_node
return data
deleteAtPosition(pos) {
if (pos < 0 || pos >= this.length()) {
throw "Enter a valid position";
} else {
if (pos == 0) {
return this.deleteFromStart();
} else if (pos === this.length() - 1) {
return this.deleteFromEnd();
} else {
let temp = this.head;
for (let i = 0; i < pos; i++) {
temp = temp.next;
}
const data = temp.data;
const prevNode = temp.prev;
prevNode.next = temp.next;
temp.next.prev = prevNode;
return data;
}
}
}
Implementation of singly linked list linked list with all the function combined with output.
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_at_start(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def insert_at_position(self, pos, data):
new_node = Node(data)
if pos < 0 or pos > self.length():
raise Exception('Enter a valid postion')
else:
if pos == 0:
self.insert_at_start(data)
elif pos == self.length()-1:
self.insert_at_end(data)
else:
temp = self.head
for _ in range(pos-1):
temp = temp.next
new_node.next = temp.next
temp.next = new_node
new_node.prev = temp
def delete_from_start(self):
if self.head:
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
else:
data = self.head.data
self.head = self.head.next
self.head.prev = None
return data
else:
raise Exception('Empty linked list')
def delete_from_end(self):
if self.head:
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
else:
data = self.tail.data
self.tail = self.tail.prev
self.tail.next = None
return data
else:
raise Exception('Empty linked list')
def delete_at_position(self, pos):
if pos < 0 or pos >= self.length():
raise Exception('Enter a valid postion')
else:
if pos == 0:
return self.delete_from_start()
elif pos == self.length()-1:
return self.delete_from_end()
else:
temp = self.head
for _ in range(pos):
temp = temp.next
data = temp.data
prev_node = temp.prev
prev_node.next = temp.next
temp.next.prev = prev_node
return data
def get_first(self):
if self.head:
return self.head.data
else:
raise Exception('Linked List is empty')
def get_last(self):
if self.tail:
return self.tail.data
else:
raise Exception('Linked List is empty')
def traverse(self):
if self.head:
temp = self.head
while temp:
print(temp.data)
temp = temp.next
else:
print(None)
def reverse_traverse(self):
if self.tail:
temp = self.tail
while temp:
print(temp.data)
temp = temp.prev
else:
print(None)
def length(self):
temp = self.head
count = 0
while temp:
count += 1
temp = temp.next
return count
dll = DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.insert_at_end(4)
dll.insert_at_end(5)
dll.insert_at_end(6)
dll.traverse()
class Node {
constructor(data) {
this.prev = null;
this.data = data;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
insertAtStart(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
}
insertAtEnd(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
}
insertAtPosition(pos, data) {
const newNode = new Node(data);
if (pos < 0 || pos > this.length()) {
throw "Enter a valid position";
} else {
if (pos == 0) {
this.insertAtStart(data);
} else if (pos == this.length() - 1) {
this.insertAtEnd(data);
} else {
let temp = this.head;
for (let i = 0; i < pos - 1; i++) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
newNode.prev = temp;
}
}
}
deleteFromStart() {
if (this.head) {
let data;
if (this.head === this.tail) {
data = this.head.data;
this.head = this.tail = null;
} else {
data = this.head.data;
this.head = this.head.next;
this.head.prev = null;
}
return data;
} else {
throw "Empty Linked List";
}
}
deleteFromEnd() {
if (this.head) {
let data;
if (this.head === this.tail) {
data = this.head.data;
this.head = this.tail = null;
} else {
data = this.tail.data;
this.tail = this.tail.prev;
this.tail.next = null;
}
return data;
} else {
throw "Empty Linked List";
}
}
deleteAtPosition(pos) {
if (pos < 0 || pos >= this.length()) {
throw "Enter a valid position";
} else {
if (pos == 0) {
return this.deleteFromStart();
} else if (pos === this.length() - 1) {
return this.deleteFromEnd();
} else {
let temp = this.head;
for (let i = 0; i < pos; i++) {
temp = temp.next;
}
const data = temp.data;
const prevNode = temp.prev;
prevNode.next = temp.next;
temp.next.prev = prevNode;
return data;
}
}
}
getFirst() {
if (this.head) return this.head.data;
throw "Linked List is empty";
}
getLast() {
if (this.tail) return this.tail.data;
throw "Linked List is empty";
}
traverse() {
if (this.head) {
let temp = this.head;
while (temp) {
console.log(temp.data);
temp = temp.next;
}
} else {
console.log(null);
}
}
reverseTraverse() {
if (this.tail) {
let temp = this.tail;
while (temp) {
console.log(temp.data);
temp = temp.prev;
}
} else {
console.log(null);
}
}
length() {
let temp = this.head;
let count = 0;
while (temp) {
count++;
temp = temp.next;
}
return count;
}
}
const dll = new DoublyLinkedList();
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.insertAtEnd(4);
dll.insertAtEnd(5);
dll.insertAtEnd(6);
dll.traverse();
Output
1 2 3 4 5 6
AUTHOR