Doubly Linked Lists
Tags: algorithms, beginners, python, career
Published: 2023-10-23 14:12:25

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/62ul32pe1fc9li9kfhna.png)

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:

```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
```
Now that's about Doubly Linked Lists. See you in the next one. Until then, Sayonara!