DEV Community

Cover image for Doubly Linked Lists
Adheeban Manoharan
Adheeban Manoharan

Posted on • Edited on

Doubly Linked Lists

In the last blog post we saw the implementation of Singly Linked List. Now in this post, we'll have detailed a look at his brother the Doubly Linked List.


Understanding Doubly Linked Lists

Just like singly linked lists, a doubly linked list is a data structure that consists of a collection of nodes. Each node, in this case, is a separate object, but what makes it unique is that each node is linked not only to the next but also to the previous node. This two-way linkage allows for more efficient traversal in both directions.

Doubly Linked List

In contrast to the singly linked list, which only points to the next element, a doubly linked list has two pointers in each node, one pointing to the next element and one pointing to the previous element.

Adding a Node

Adding a node in a doubly linked list is a bit more intricate than in a singly linked list. Suppose we have a node cur that we want to insert between the prev node and the next node. To achieve this, we must perform the following steps:

  • Set the reference field of the prev node to point to the cur node.
  • Set the reference field of the cur node to point to the next node.
  • Adjust the reference field of the next node to also point back to the cur node, completing the two-way linkage.

The insertion process in a doubly linked list still maintains its efficiency, and you can insert a new node in O(1) time complexity when you have references to the prev and next nodes.

Deleting a Node

Deleting a node in a doubly linked list, much like insertion, requires a bit more work due to the two-way linkage. Let's consider a node cur that we want to delete:

  • Find the cur node's previous node prev and next node next first.
  • Adjust the reference field of the prev node to point to the next node, breaking the linkage from the cur node.
  • Adjust the reference field of the next node to point back to the prev node.

In a doubly linked list, finding the next node using the reference field is simple. However, finding the previous node prev is equally efficient since we can traverse the list in both directions. The time complexity for deleting a node remains O(1).

Implementation with Python

Now, let's dive into the implementation of a doubly linked list in Python:



# ListNode class represents a node in the doubly linked list.
class ListNode:
    def __init__(self, val):
        self.val = val  # Value of the current node
        self.prev = None  # Reference to the previous node
        self.next = None  # Reference to the next node

# MyLinkedList class implements the doubly linked list with the specified methods.
class MyLinkedList:
    def __init__(self):
        self.head = None  # Reference to the head node (the first node)
        self.tail = None  # Reference to the tail node (the last node)
        self.size = 0     # Number of nodes in the linked list

    # Get the value of the node at the specified index in the linked list.
    def get(self, index):
        if index < 0 or index >= self.size:
            return -1  # Return -1 for an invalid index

        current = self.head
        for _ in range(index):
            current = current.next

        return current.val

    # Add a new node with the given value to the head of the linked list.
    def addAtHead(self, val):
        new_node = ListNode(val)
        if self.size == 0:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.size += 1

    # Append a new node with the given value to the tail of the linked list.
    def addAtTail(self, val):
        new_node = ListNode(val)
        if self.size == 0:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    # Add a new node with the given value before the node at the specified index.
    def addAtIndex(self, index, val):
        if index < 0 or index > self.size:
            return  # Do nothing for an invalid index

        if index == 0:
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        else:
            new_node = ListNode(val)
            current = self.head
            for _ in range(index - 1):
                current = current.next

            new_node.prev = current
            new_node.next = current.next
            current.next.prev = new_node
            current.next = new_node
            self.size += 1

    # Delete the node at the specified index in the linked list.
    def deleteAtIndex(self, index):
        if index < 0 or index >= self.size:
            return  # Do nothing for an invalid index

        if self.size == 1:
            self.head = self.tail = None
        elif index == 0:
            self.head = self.head.next
            self.head.prev = None
        elif index == self.size - 1:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            current = self.head
            for _ in range(index):
                current = current.next
            current.prev.next = current.next
            current.next.prev = current.prev

        self.size -= 1


Enter fullscreen mode Exit fullscreen mode

Now that's about Doubly Linked Lists. See you in the next one. Until then, Sayonara!

Top comments (0)