Join Our 4-Week Free Gen AI Course with select Programs.

Request a callback

or Chat with us on

Doubly Linked List in Data Structure: A Detailed Explanation for Beginners

Basics of Python
Basics of Python
icon
5 Hrs. duration
icon
9 Modules
icon
1800+ Learners
logo
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.

Doubly Linked List in Data Structure

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.

 

  • Data
  • A pointer to the next node (next)
  • A pointer to the previous node (prev)

Doubly Linked List in Data Structure

Doubly Linked List Implementation in Java

The following program implements the Doubly linked data structure in the Java language.

 

Program

class Node { int data; Node next; Node prev;  Node(int data) { this.data = data; this.next = null; this.prev = null; } }  class DoublyLinkedList { private Node head; private Node tail;  public DoublyLinkedList() { this.head = null; this.tail = null; }  public void addLast(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; tail = newNode; } else { tail.next = newNode; newNode.prev = tail; tail = newNode; } }  public void addFirst(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; tail = newNode; } else { newNode.next = head; head.prev = newNode; head = newNode; } }  public void remove(int data) { Node current = head; while (current != null) { if (current.data == data) { if (current.prev != null) { current.prev.next = current.next; } else { head = current.next; } if (current.next != null) { current.next.prev = current.prev; } else { tail = current.prev; } return; } current = current.next; } }  public void displayForward() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); }  public void displayBackward() { Node current = tail; while (current != null) { System.out.print(current.data + " "); current = current.prev; } System.out.println(); } }  public class Main { public static void main(String[] args) { DoublyLinkedList list = new DoublyLinkedList();  list.addLast(10); list.addLast(20); list.addFirst(5);  System.out.println("List in forward order:"); list.displayForward();  System.out.println("List in backward order:"); list.displayBackward();  list.remove(10); System.out.println("After removing 10:"); list.displayForward(); } }

Output

List in forward order: 5 10 20 List in backward order: 20 10 5 After removing 10: 5 20

Doubly Linked List implementation in Python

The following program implements the Doubly linked data structure in Python.

 

Program

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None  class DoublyLinkedList: def __init__(self): self.head = None self.tail = None  def add_last(self, data): new_node = Node(data) if self.head is None: self.head = new_node self.tail = new_node else: self.tail.next = new_node new_node.prev = self.tail self.tail = new_node  def add_first(self, data): new_node = Node(data) if self.head is None: self.head = new_node self.tail = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node  def remove(self, data): current = self.head while current: if current.data == data: if current.prev: current.prev.next = current.next else: self.head = current.next if current.next: current.next.prev = current.prev else: self.tail = current.prev return current = current.next  def display_forward(self): current = self.head while current: print(current.data, end=' ') current = current.next print()  def display_backward(self): current = self.tail while current: print(current.data, end=' ') current = current.prev print()  # Example usage if __name__ == "__main__": dll = DoublyLinkedList()  dll.add_last(10) dll.add_last(20) dll.add_first(5)  print("List in forward order:") dll.display_forward()  # Output: 5 10 20  print("List in backward order:") dll.display_backward()  # Output: 20 10 5  dll.remove(10) print("After removing 10:") dll.display_forward()  # Output: 5 20

Output

List in forward order: 5 10 20 List in backward order: 20 10 5 After removing 10: 5 20

Doubly Linked List implementation in JavaScript

The following program implements the Doubly linked data structure in the JavaScript language.

Program

class Node { constructor(data) { this.data = data; this.next = null; this.prev = null; } }  class DoublyLinkedList { constructor() { this.head = null; this.tail = null; }  addLast(data) { const newNode = new Node(data); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail; this.tail = newNode; } }  addFirst(data) { const newNode = new Node(data); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { newNode.next = this.head; this.head.prev = newNode; this.head = newNode; } }  remove(data) { let current = this.head; while (current) { if (current.data === data) { if (current.prev) { current.prev.next = current.next; } else { this.head = current.next; } if (current.next) { current.next.prev = current.prev; } else { this.tail = current.prev; } return; } current = current.next; } }  displayForward() { let current = this.head; while (current) { process.stdout.write(current.data + ' '); current = current.next; } console.log(); }  displayBackward() { let current = this.tail; while (current) { process.stdout.write(current.data + ' '); current = current.prev; } console.log(); } }  // Example usage const dll = new DoublyLinkedList();  dll.addLast(10); dll.addLast(20); dll.addFirst(5);  console.log("List in forward order:"); dll.displayForward(); // Output: 5 10 20   console.log("List in backward order:"); dll.displayBackward(); // Output: 20 10 5  dll.remove(10); console.log("After removing 10:"); dll.displayForward(); // Output: 5 20

Output

List in forward order: 5 10 20 List in backward order: 20 10 5 After removing 10: 5 20

Also Read: Java Script Interview Questions

Operations on Doubly Linked List

  • Traversal in Doubly Linked List
  • Insertion at the Beginning of Doubly Linked List
  • Insertion at the end of the Doubly Linked List
  • 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); } }

Output

Forward Traversal: 1 2 3 Backward Traversal: 3 2 1

Insertion at the Beginning in Doubly Linked List

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.

Doubly Linked List

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.

double 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
DevOps & Cloud Engineering
Internship Assurance
DevOps & Cloud Engineering

Conclusion

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
Yes, we can traverse a doubly linked list in reverse by following the previous pointers from the tail node to the head.
You can traverse the whole from head to tail, counting each node until the end, which gives you the length of the 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.
brochureimg

The DevOps Playbook

Simplify deployment with Docker containers.

Streamline development with modern practices.

Enhance efficiency with automated workflows.

left dot patternright dot pattern

Programs tailored for your success

Popular

Management

Data Science

Finance

Technology

Future Tech

Upskill with expert articles

View all
Hero Vired logo
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.

Data Science

Accelerator Program in Business Analytics & Data Science

Integrated Program in Data Science, AI and ML

Accelerator Program in AI and Machine Learning

Advanced Certification Program in Data Science & Analytics

Technology

Certificate Program in Full Stack Development with Specialization for Web and Mobile

Certificate Program in DevOps and Cloud Engineering

Certificate Program in Application Development

Certificate Program in Cybersecurity Essentials & Risk Assessment

Finance

Integrated Program in Finance and Financial Technologies

Certificate Program in Financial Analysis, Valuation and Risk Management

Management

Certificate Program in Strategic Management and Business Essentials

Executive Program in Product Management

Certificate Program in Product Management

Certificate Program in Technology-enabled Sales

Future Tech

Certificate Program in Gaming & Esports

Certificate Program in Extended Reality (VR+AR)

Professional Diploma in UX Design

Blogs
Reviews
Events
In the News
About Us
Contact us
Learning Hub
18003093939     ·     hello@herovired.com     ·    Whatsapp
Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved