Doubly Linked List in Data Structure: A Detailed Explanation for Beginners
Basics of SQL
12 Hrs. duration
12 Modules
2600+ Learners
Start Learning
A doubly linked list in data structure that is more complex than a singly linked list. It offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer for the previous node and a pointer for the next node. The doubly linked list allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions.
What is a Doubly Linked List?
A doubly linked list is a sequence of nodes where every node contains three components: the data, a pointer to the next node, and a pointer to the previous node. Such a structure makes it easier to insert nodes as well as delete nodes compared to a singly linked list, especially when you need to traverse in the backward direction.
Representation of Doubly Linked List in Data Structure
The linked list data structure, A doubly linked list is represented using nodes that have three fields.
Insertion at a specific position in the Doubly Linked List
Deletion of a node at the beginning of the Doubly Linked List
Deletion of a node at the end of the Doubly Linked List
Deletion of a node at a specific position in the Doubly Linked List.
Traversal in Doubly Linked List
Traversal is the process in a doubly linked list that involves using each node in the list in sequence. A doubly linked list is a data structure where each node contains three components.
Data: The value stored in the node.
Next Pointer: A pointer/ reference to the next node in the sequence.
Previous Pointer: A pointer/reference to the previous node in the sequence
The following program traversals the LinkedList in Java:
Program
class Node {
int data;
Node next;
Node prev;
public Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class Main {
static void forwardTraversal(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
static void backwardTraversal(Node tail) {
Node curr = tail;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.prev;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
head.next = second;
second.prev = head;
second.next = third;
third.prev = second;
System.out.println("Forward Traversal:");
forwardTraversal(head);
System.out.println("Backward Traversal:");
backwardTraversal(third);
}
}
Inserting an element at the beginning of a doubly linked list involves a few steps. A doubly linked list is a data structure where each node contains a reference to both the next and the previous node, allowing traversal in both directions.
To insert a new node at the beginning of the doubly linked list.
Create a new node, say new_node, with the given data and set its previous pointer to null, new_node -> prev = NULL.
Then set the next pointer of new_node to current head, new_node->next = head.
The linked list is not empty, update the previous pointer of the current head to new_node, head -prev = new_node
The return new_node as the head of the updated linked list.
The following program demonstrates the doubly linked list:
Program
class Node {
int data;
Node prev, next;
Node(int d) {
data = d;
prev = null;
next = null;
}
}
class Main {
static Node insertBegin(Node head, int data) {
Node new_node = new Node(data);
new_node.next = head;
if (head != null) {
head.prev = new_node;
}
return new_node;
}
static void printList(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(2);
head.next = new Node(3);
head.next.prev = head;
head.next.next = new Node(4);
head.next.next.prev = head.next;
System.out.print("Original Linked List: ");
printList(head);
head = insertBegin(head, 1);
System.out.print(
"After inserting Node 1 at the front: ");
printList(head);
}
}
Output
Original Linked List: 2 3 4
After inserting Node 1 at the front: 1 2 3 4
Insertion at the End of Doubly Linked List
Inserting a node at the end of a doubly linked list involves a few key steps. A doubly linked list consists of nodes, and each node has three components. The data, a pointer to the next node, and a pointer to the previous node.
To insert a new node at the end of the doubly linked list.
The memory is allocated for a new node, and the provided value is assigned to its data field.
The next pointer of the new node will be initialized to nullptr.
The set previous pointer of the new node to nullptr.
The following program implementation of Doubly Linked List.
Program
class Node {
int data;
Node next, prev;
Node(int newData) {
data = newData;
next = prev = null;
}
}
class Main{
public static Node insertEnd(Node head, int newData) {
Node newNode = new Node(newData);
if (head == null) {
head = newNode;
}
else {
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = newNode;
newNode.prev = curr;
}
return head;
}
public static void printList(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;
System.out.println("Original Linked List: ");
printList(head);
System.out.println(
"Inserting Node with data 4 at the end: ");
int data = 4;
head = insertEnd(head, data);
printList(head);
}
}
Output
Original Linked List:
1 2 3
Inserting Node with data 4 at the end:
1 2 3 4
Insertion at a Specific Position in Doubly Linked List
The following steps can be used to insert a node at a specific position in a doubly linked list.
To insert a new node at a specific position.
The position = 1, create a new node, make it the head of the linked list and return it.
Otherwise, traverse the list to reach the node at position -1, say curr.
The position is valid. Create a new node with the given data, and say new_node.
The update will change the new node’s next pointer to the next of the current node and its previous pointer to the current one.
Similarly, update the next pointer of the current node to the new node, curr->next = new_node.
The new node is not the last node in the list. Update the prev pointer next to the new node, new_node->next-> prev = new_node.
The following program demonstrates the insertion of a new node at a specific position.
class Node {
int data;
Node next;
Node prev;
Node(int new_data) {
data = new_data;
next = prev = null;
}
}
class Main {
public static Node insertAtPosition(Node head, int pos, int new_data) {
Node new_node = new Node(new_data);
if (pos == 1) {
new_node.next = head;
if (head != null) {
head.prev = new_node;
}
head = new_node;
return head;
}
Node curr = head;
for (int i = 1; i < pos - 1 && curr != null; ++i) {
curr = curr.next;
}
if (curr == null) {
System.out.println("Position is out of bounds.");
return head;
}
new_node.prev = curr;
new_node.next = curr.next;
curr.next = new_node;
if (new_node.next != null) {
new_node.next.prev = new_node;
}
return head;
}
public static void printList(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(4);
head.next.next.prev = head.next;
System.out.print("Original Linked List: ");
printList(head);
System.out.print("Inserting Node with data 3 at position 3: ");
int data = 3;
int pos = 3;
head = insertAtPosition(head, pos, data);
printList(head);
}
}
Output
Original Linked List:
1 2 3
Inserting Node with data 4 at the end:
1 2 3 4
Deletion at the Beginning of Doubly Linked List
To delete a node at the beginning in the Doubly linked list. You have to follow the following steps.
Check if the list is empty or not. If the list has nothing to delete, then return.
Then, store the header pointer in the variable and say temp.
Then update the head of the linked list to the node next to the current head = head->next.
The head is not NULL; update the previous pointer of a new head, and head-prev = NULL.
Program
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class Main{
public static Node delHead(Node head) {
if (head == null) {
return null;
}
Node temp = head;
head = head.next;
if (head != null) {
head.prev = null;
}
return head;
}
public static void printList(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;
System.out.print("Original Linked List: ");
printList(head);
System.out.print("After Deletion at the beginning: ");
head = delHead(head);
printList(head);
}
}
Output
Original Linked List: 1 2 3
After Deletion at the beginning: 2 3
Deletion at the End of Doubly Linked List
To delete a node at the end of a doubly linked list, follow the following steps.
First, check if the doubly linked is empty. If it is empty, then there is nothing to delete
If the list is empty, move to the last node of the doubly linked list, say curr.
The update the second-to-last node’s next pointer to NULL, curr-prev->next = NULL.
The free memory is allocated for the node that was deleted.
Program
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class Main {
public static Node delLast(Node head) {
if (head == null) {
return null;
}
if (head.next == null) {
return null;
}
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
if (curr.prev != null) {
curr.prev.next = null;
}
return head;
}
// Function to print the list
public static void printList(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;
System.out.print("Original Linked List: ");
printList(head);
System.out.print("After Deletion at the end: ");
head = delLast(head);
printList(head);
}
}
Output
Original Linked List: 1 2 3
After Deletion at the end: 1 2
Deletion at a Specific Position in Doubly Linked List
In the Doubly Linked list, we can delete the node at the specific position by following the steps.
Traverse to the node at the specific position, say that curr.
If the position is valid, adjust the pointer to skip the node to be deleted.
If the curr is not the head of the linked list, then update the next pointer of the node before curr to point to the node after curr, curr-prev-> next = curr-next.
The curr is not the last node of the linked list, Then update the previous pointer of the node after curr to the node before curr, curr->next->prev = curr->prev.
The free memory is allocated for the deleted node.
Program
// Java Program to delete node at a specific position in Doubly Linked List
class Node {
int data;
Node prev;
Node next;
Node(int d) {
data = d;
prev = null;
next = null;
}
}
class Main{
public static Node delPos(Node head, int pos) {
if (head == null) {
return head;
}
Node curr = head;
for (int i = 1; curr != null && i < pos; ++i) {
curr = curr.next;
}
if (curr == null) {
return head;
}
if (curr.prev != null) {
curr.prev.next = curr.next;
}
if (curr.next != null) {
curr.next.prev = curr.prev;
}
if (head == curr) {
head = curr.next;
}
return head;
}
public static void printList(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;
System.out.print("Original Linked List: ");
printList(head);
System.out.print("After Deletion at position 2: ");
head = delPos(head, 2);
printList(head);
}
}
Output
Original Linked List: 1 2 3
After Deletion at position 2: 1 3
In this article, we learned about the doubly linked list. It is a powerful data structure that provides a flexible way to store and manage memory. Unlike a singly linked list, each node in a doubly linked list contains references to the next and previous nodes, allowing for efficient bidirectional traversal. Understanding doubly linked lists is very important for effectively handling the complex data management tasks in programming.
FAQs
Can you traverse a doubly linked list in reverse?
Yes, we can traverse a doubly linked list in reverse by following the previous pointers from the tail node to the head.
How do you find the length of a doubly linked list?
You can traverse the whole from head to tail, counting each node until the end, which gives you the length of the list.
How do you clear or delete all nodes in a doubly linked list?
To clear or doubly link a list, traverse it from the head, deleting each node individually. Finally, the head and tail pointers were set to null.
Deploying Applications Over the Cloud Using Jenkins
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
