Doubly Linked List: Complete Guide & Implementation

A doubly linked list (also called a double linked list) is an important data structure that extends the capabilities of traditional linked lists. Unlike single-direction linked lists, doubly linked lists enable bi-directional traversal, making them essential for applications requiring efficient forward and backward navigation.

In this comprehensive guide, we’ll master doubly linked list implementation, explore core operations, and discover real-world applications where these versatile data structures excel.

What is a doubly linked list?

A doubly linked list is a useful data structure in which each node contains three parts:

• Data field: Stores the actual information
• Next pointer: References the following node
• Previous pointer: References the preceding node

Advantages:

• Bi-directional traversal: We can move forward and backward through the list efficiently.
• Efficient insertion and deletion: Adding or removing elements at both ends or in the middle is simpler because we have references to the previous and next nodes.
• Better support for certain algorithms: Some algorithms, such as those involving undo/redo functionality, are easier to implement using a doubly linked list.

Disadvantages:

• More memory usage: Each node requires extra memory to store the previous pointer.
• Increased complexity: Operations such as insertion and deletion require careful pointer updates to maintain list integrity.
• Potential for bugs: Incorrect pointer manipulation can lead to data corruption or memory leaks.

Real-world analogy:

Think of your daily commute on the subway as a real-world example of a doubly linked list. Your home is the beginning of the list, your place of work is the end, and every stop in between is a particular node in the list:

Now that we know what a doubly linked list is, let’s check out some basic operations that we can perform on the same.

Basic doubly linked list operations

Some basic operations that we can perform on a doubly linked list are:

• Insertion at the beginning
• Insertion at the end
• Deletion from the beginning
• Deletion from the end
• Deletion from the middle

Let’s understand how to perform these operations one by one.

Insertion at the beginning

When inserting at the beginning of a doubly linked list, we first need to check if there is a current head to the list. If there isn’t, then the list is empty, and we can simply make our new node both the head and tail of the list and set both pointers to null. If the list is not empty, then we:

• Set the current head’s previous pointer to our new head
• Set the new head’s next pointer to the current head
• Set the new head’s previous pointer to null

Insertion at the end

Just like inserting at the beginning, there are two cases when inserting a node at the end of a doubly linked list. If the list is empty, then we make the new node the head and tail of the list and set the pointers to null. If the list is not empty, then we:

• Set the current tail’s next pointer to the new tail
• Set the new tail’s previous pointer to the current tail
• Set the new tail’s next pointer to null

Here is a visual representation of the two insertion operations:

Deletion from the beginning

Removing the head involves updating the pointer at the beginning of the list. We will set the previous pointer of the new head (the element directly after the current head) to null and update the head property of the list. If the head is also the tail, the tail removal process will occur as well.

Deletion from the end

Similarly, removing the tail involves updating the pointer at the end of the list. We will set the next pointer of the new tail (the element just before the tail) to null and update the tail property of the list. If the tail is also the head, the head removal process will occur as well.

Here is a visual representation of the two deletion operations:

Deletion from the middle

It is also possible to remove a node from the middle of a list. Since that node is neither the head nor the tail of the list, there are two pointers that must be updated:

• We must set the removed node’s preceding node’s next pointer to its following node.
• We must set the removed node’s following node’s previous pointer to its preceding node.

There is no need to change the pointers of the removed node, as updating the pointers of its neighboring nodes will remove it from the list. If no nodes in the list are pointing to it, the node is orphaned.

Here is a visual representation of deletion from the middle of a doubly linked list:

With basic operations sorted, it’s time to learn how to implement a doubly linked list programmatically.

Doubly linked list implementation

This example implements a doubly linked list in Python, where each node stores data along with pointers to both the previous and next nodes. It includes methods to insert nodes at the beginning or end, delete nodes from the beginning, end, or middle, and print the list forward or backward. The example usage shows how these operations work in sequence, demonstrating insertion, deletion, and traversal in both directions:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    # Insert at the beginning
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        if self.head:
            self.head.prev = new_node
        self.head = new_node

    # Insert at the end
    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node
        new_node.prev = temp

    # Delete from the beginning
    def delete_at_beginning(self):
        if not self.head:
            print("\nList is empty.")
            return
        print(f"\nDeleting node with data: {self.head.data}")
        self.head = self.head.next
        if self.head:
            self.head.prev = None

    # Delete from the end
    def delete_at_end(self):
        if not self.head:
            print("\nList is empty.")
            return
        temp = self.head
        if not temp.next:
            print(f"\nDeleting node with data: {temp.data}")
            self.head = None
            return
        while temp.next:
            temp = temp.next
        print(f"\nDeleting node with data: {temp.data}")
        temp.prev.next = None

    # Delete from the middle
    def delete_node(self, node):
        if not node:
            print("\nNode is None.")
            return
        print(f"\nDeleting node with data: {node.data}")
        if node.prev:
            node.prev.next = node.next
        if node.next:
            node.next.prev = node.prev
        if node == self.head:
            self.head = node.next

    # Print the list forward
    def print_forward(self):
        temp = self.head
        print("List (forward): ", end="")
        while temp:
            print(temp.data, end=" <-> " if temp.next else "")
            temp = temp.next
        print()

    # Print the list backward
    def print_backward(self):
        temp = self.head
        if not temp:
            print("\nList is empty.")
            return
        while temp.next:
            temp = temp.next
        print("List (backward): ", end="")
        while temp:
            print(temp.data, end=" <-> " if temp.prev else "")
            temp = temp.prev
        print()

# Example usage
if __name__ == "__main__":
    dll = DoublyLinkedList()

    # Insert at the beginning
    dll.insert_at_beginning(10)
    dll.insert_at_beginning(20)
    dll.insert_at_beginning(30)
    print("After inserting at the beginning:")
    dll.print_forward()

    # Insert at the end
    dll.insert_at_end(5)
    dll.insert_at_end(0)
    print("\nAfter inserting at the end:")
    dll.print_backward()

    # Delete from the beginning
    dll.delete_at_beginning()
    print("\nAfter deleting at the beginning:")
    dll.print_forward()

    # Delete from the end
    dll.delete_at_end()
    print("\nAfter deleting at the end:")
    dll.print_backward()

    # Delete from the middle (e.g., node with data 20)
    temp = dll.head
    while temp and temp.data != 20:
        temp = temp.next
    if temp:
        dll.delete_node(temp)
    print("\nAfter deleting a node in the middle with data: 20")
    dll.print_forward()

Copy to clipboard
Copy to clipboard

Here is the output:

After inserting at the beginning:
List (forward): 30 <-> 20 <-> 10

After inserting at the end:
List (backward): 0 <-> 5 <-> 10 <-> 20 <-> 30

Deleting node with data: 30

After deleting at the beginning:
List (forward): 20 <-> 10 <-> 5 <-> 0

Deleting node with data: 0

After deleting at the end:
List (backward): 5 <-> 10 <-> 20

Deleting node with data: 20

After deleting a node in the middle with data: 20
List (forward): 10 <-> 5

Copy to clipboard
Copy to clipboard

Next, we’ll compare doubly linked lists with singly linked lists to understand exactly how they differ in their functionalities.

Singly linked list vs doubly linked list comparison

Here are the differences between singly linked lists and doubly linked lists:

Finally, let’s check out the real-world applications of a doubly linked list.

Doubly linked list applications

We use doubly linked lists in many applications due to their ability to efficiently add, remove, and traverse elements. Some common use cases include:

• Implementing navigation systems: Browsers use doubly linked lists to implement back and forward navigation. The user can move between pages easily without losing context.
• Undo/redo functionality in text editors: Each operation can be stored as a node, allowing users to revert or repeat actions seamlessly.
• Task scheduling: Operating systems and software use doubly linked lists to manage processes and tasks where efficient insertion and deletion are crucial.
• Music or video playlists: Media players rely on doubly linked lists to allow users to move to the previous or next track with ease.
• Memory management: Doubly linked lists are used in memory allocation algorithms where blocks of memory need to be dynamically managed.

These examples highlight the real-world importance of the doubly linked list data structure. Their efficiency and flexibility make them a popular choice in scenarios requiring dynamic data manipulation.

Conclusion

In this guide, we thoroughly explored doubly linked lists, covering their definition, advantages, disadvantages, and implementation techniques such as insertion and deletion from different locations of the list. Additionally, we identified the differences between singly linked lists and doubly linked lists and examined practical applications where doubly linked lists play a crucial role.

By understanding how doubly linked lists work and where they are used, we equip ourselves with a powerful tool in data structure management. While they require careful pointer manipulation and consume more memory than singly linked lists, their ability to efficiently handle dynamic data makes them indispensable in many programming scenarios.

If you want to learn more about doubly linked lists, check out the Learn Data Structures and Algorithms with Python course on Codecademy.

Frequently asked questions

1. What is a doubly linked list?

A doubly linked list is a useful data structure where each node contains three fields: data, a pointer pointing to the next node, and a pointer pointing to the previous node. This allows movement in both forward and backward directions.

2. What’s the difference between singly linked lists and doubly linked lists?

A singly linked list stores data and a pointer to the next node, allowing traversal in only one direction. On the other hand, a doubly linked list stores data, a next pointer, and a previous pointer, enabling traversal in both directions but requiring more memory.

3. What is another name for doubly linked list?

A doubly linked list is sometimes referred to as a two-way linked list because it allows movement in both directions.

4. Why use a doubly linked list?

We use a doubly linked list when we need efficient insertion and deletion from both ends, as well as easy traversal in forward and backward directions. It is particularly useful in applications like browsers, text editors, and memory management.

5. Is stack a doubly linked list?

No, a stack is not a doubly linked list. A stack is another essential data structure that follows the LIFO (Last In, First Out) principle. However, a stack can be implemented using arrays, singly linked lists, or doubly linked lists depending on the requirements.