Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 31

Doubly Linked Lists: Implementation and Operations

Recommended resources

Welcome back to our journey through data structures. In our previous lesson, you successfully built a singly linked list from the ground up, mastering one-way traversal and the pointer mechanics for insertion and deletion. This foundational knowledge is the perfect springboard for our next topic.

One of the key limitations we observed in a singly linked list was its unidirectional nature. Operations like deleting the last element required traversing the entire list, resulting in O(n) time complexity. Today, we'll address this by exploring its more versatile sibling: the doubly linked list. By adding just one more pointer to each node, we unlock bidirectional traversal and significantly improve the efficiency of several core operations.

This lesson will guide you through implementing a doubly linked list in Java, covering its structure and all associated insertion and deletion methods.

1. The Doubly Linked List: Adding a New Dimension

A doubly linked list enhances the simple chain of nodes we saw before. While a singly linked list node only knows about the next node, a doubly linked list node keeps track of both its neighbors.

Each node in a doubly linked list contains three pieces of information:

  1. The actual data value.
  2. A reference (or "pointer") to the next node in the sequence.
  3. A reference (or "pointer") to the previous node in the sequence.

This structure allows for traversal in both forward and backward directions.

A basic doubly linked list. Each node contains data and two pointers: 'next' pointing to the subsequent node and 'prev' pointing to the preceding node. The head's 'prev' is NULL, and the last node's 'next' is NULL.

Let's begin by watching a short segment from the "take U forward" series, which introduces this concept and shows how the Node class is modified.

L3. Introduction to Doubly LinkedList | Insertions and Deletions

This video introduces the doubly linked list, explains how its two-way pointers work, and shows how to represent the enhanced Node in code.

Watch the segment from the introduction. Pay close attention to the addition of the back (or prev) pointer and how it changes the node's structure compared to a singly linked list.

2. Building the Doubly Linked List in Java

Just like with the singly linked list, our implementation will consist of a main DoublyLinkedList class and a private inner Node class. The key difference is the addition of the prev reference in our Node.

Let's look at the basic code structure for this.

Introduction to Doubly Linked Lists in Java

This article from GeeksforGeeks provides a clear and concise blueprint for our DoublyLinkedList class in Java.

Read the section Creating the Classes. This will show you the definition for the Node class with its three fields (data, prev, next) and the DoublyLinkedList class that holds the head and tail references.

As you saw in the reading, the structure is very similar to our previous lesson, with the crucial addition of Node prev. Having both head and tail pointers will be instrumental in achieving O(1) time complexity for operations at both ends of the list.

3. Core Operations: Insertion

With the ability to look both ways, the logic for insertion becomes a game of reconnecting four pointers. Let's examine the common insertion scenarios.

Insertion at the Head

To insert a new node at the beginning of the list, we need to:

  1. Create the new node.
  2. Set the new node's next to the current head.
  3. If the list isn't empty, set the current head's prev to the new node.
  4. Update the list's head to point to the new node.
  5. Handle the edge case where the list was initially empty (the new node is also the tail).

This operation remains an efficient O(1).

Insertion at the Tail

This is where the doubly linked list truly shines compared to its singly-linked counterpart. Thanks to our tail pointer and the new prev pointer, we can add a node to the end in O(1) time.

  1. Create the new node.
  2. Set the new node's prev to the current tail.
  3. Set the current tail's next to the new node.
  4. Update the list's tail to point to the new node.
  5. Handle the empty list edge case.

Insertion Before a Specific Node

To insert a new node before an existing node (givenNode):

  1. Find the givenNode's predecessor: prevNode = givenNode.prev.
  2. Create the new node.
  3. Set newNode.next = givenNode and newNode.prev = prevNode.
  4. Update the pointers of the neighbors: prevNode.next = newNode and givenNode.prev = newNode.

The following video from the TUF series provides a detailed walkthrough of all insertion scenarios, including the pointer logic and Java code.

L3. Introduction to Doubly LinkedList | Insertions and Deletions

This video covers all four main insertion types: before the head, before the tail, before the k-th element, and before a given node.

Before Head: Watch from this segment. Before Tail: Watch the logic from this part. Notice how it finds the node before the tail to insert there. This is different from a simple insertAtEnd. Before k-th element: The logic for a general case is explained from this timestamp. Before a given Node: Finally, see the most direct case from this explanation.

4. Core Operations: Deletion

Deletion follows a similar pattern of re-wiring pointers. The prev pointer makes these operations remarkably symmetric and efficient.

Deleting the Head

To remove the first node:

  1. Update the head to be head.next.
  2. Set the new head's prev pointer to null.
  3. Handle the edge case where the list becomes empty.

This is an O(1) operation.

Deleting the Tail

This is a major performance improvement. In a singly linked list, this was O(n). In a doubly linked list, it's O(1).

  1. Update the tail to be tail.prev.
  2. Set the new tail's next pointer to null.
  3. Handle the edge case where the list becomes empty.

This O(1) efficiency for deleting from the tail is a key reason why doubly linked lists are used in implementing data structures like a Deque (double-ended queue).

Deleting a Specific Node

To delete a specific nodeToDelete:

  1. Connect its neighbors to each other: nodeToDelete.prev.next = nodeToDelete.next.
  2. And in the other direction: nodeToDelete.next.prev = nodeToDelete.prev.
  3. Handle edge cases where nodeToDelete is the head or the tail.

Let's return to the TUF video to see the implementation details for deletion.

L3. Introduction to Doubly LinkedList | Insertions and Deletions

This video details the deletion of the head, tail, k-th element, and a given node, complete with edge case handling.

Deleting Head: Watch from this segment. Deleting Tail: Watch from this section. Note the O(1) nature if a tail pointer is maintained. Deleting k-th element: The general case is covered from this timestamp. Deleting a given Node: The logic is explained from here.

5. The Complete Picture

You've now seen the theory and implementation details for every fundamental operation. To solidify your understanding, it's essential to see how these methods fit together in a complete class and how they are used.

Introduction to Doubly Linked Lists in Java

This GeeksforGeeks article provides a complete, runnable Java program that implements all the operations we've discussed, with clear code and diagrams for each.

Review the entire article. Pay special attention to the following sections: Traversal: Note the implementation of both traverseForward and traverseBackward. Insertion: Review the code for insertion at the beginning, at a position, and at the end. Compare it with the video's logic. Deletion: Study the code for deleting from the beginning, at a position, and from the end. Finally, trace the main method in the complete example to see how these methods are called and how they modify the list. Also, as you requested, here is the link to the Java solutions for Striver's A2Z DSA Sheet. You can find the complete implementation files for doubly linked lists here.

GitHub - Bharat2044/Striver-A2Z-DSA-Sheet-Solution-using-JAVA: This repository contains Strivers A2Z DSA Course/Sheet Code Solution using JAVA with explanation. 🔥

This GitHub repository contains the Java solutions for the course you're following.

Navigate to the folder named Lec 2: Learn Doubly LinkedList. You can explore the *.java files there to see a complete, problem-oriented implementation.

Conclusion

In this lesson, you've taken a significant step forward by implementing the doubly linked list. By adding a single prev pointer to each node, you've created a more powerful and flexible data structure.

Key Takeaways:

  • Structure: A doubly linked list node contains data, a next pointer, and a prev pointer, allowing for bidirectional traversal.
  • SLL vs. DLL: The main trade-off is memory (DLLs use more memory per node) for performance and flexibility. DLLs provide O(1) insertion/deletion at the tail (with a tail pointer) and make reverse traversal trivial.
  • Pointer Logic: All insertion and deletion operations in the middle of the list involve re-wiring four key pointer references to correctly link and unlink nodes.
  • Java's LinkedList: It's worth noting that Java's built-in java.util.LinkedList is implemented as a doubly linked list, which is why it can efficiently function as both a Queue and a Deque.

In our next lesson, we will pivot from building data structures to solving problems with them. We'll start with a classic interview question: reversing a singly linked list, which will test your understanding of pointer manipulation in a new way.