Implementing a Doubly Linked List in Python

A doubly linked list is a linear data structure that consists of a sequence of nodes where each node contains data and pointers to the previous and next node in the sequence. Unlike a singly linked list, where nodes only point in one direction, nodes in a doubly linked list have connections in both directions allowing you to traverse the list in either direction.

Doubly linked lists are useful data structures due to their ability to iterate in both directions and delete nodes efficiently without having to traverse the entire list. They have applications in implementing undo/redo functionality, browser history, blockchain, and more.

In this comprehensive guide, you will learn how to implement a doubly linked list in Python by building out methods for insertion, deletion, and traversal operations.

Open Table of Contents

Overview of Doubly Linked Lists
Implementing a Node
Building the Doubly Linked List Class
Time and Space Complexity
Applications of Doubly Linked Lists
Summary

Overview of Doubly Linked Lists

Let’s first understand what comprises a basic doubly linked list:

Node - Each element in the linked list is called a node. A node contains the data being stored and pointers to the previous and next node.
Head - This is the first node in the doubly linked list. The head node’s previous pointer points to None.
Tail - This is the last node in the doubly linked list. The tail node’s next pointer points to None.
Pointer - Each node contains two pointer attributes, prev and next that point to the previous and next node respectively. The prev and next pointers allow you to traverse the list.

Here is a visual representation of a simple doubly linked list:

Head <-> Node1 <-> Node2 <-> Tail

Head.next = Node1
Node1.prev = Head
Node1.next = Node2
Node2.prev = Node1
Node2.next = Tail
Tail.prev = Node2

The order of elements in a doubly linked list depends on the sequence of insertions and deletions performed. New nodes can be inserted anywhere by updating the next and prev pointers of adjacent nodes.

Below are some key characteristics of doubly linked lists:

Nodes contain both next and prev pointers
Can be traversed in both forward and backward directions
Insertion and deletion of nodes is efficient without reorganizing the entire structure
Uses more memory than a singly linked list due to extra prev pointer
Manipulations are more complex due to extra pointer

Implementing a Node

Let’s start by defining a Node class representing each node in our doubly linked list:

class Node:

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

The Node constructor initializes the data attribute to the data value passed and sets next and prev pointers to None.

We can also define a simple print_nodes() helper function to print node data for debugging:

def print_nodes(node):

    while node:
        print(node.data, end=" ")
        node = node.next
    print()

This sequentially traverses the list starting from the passed node and prints each node’s data attribute.

Building the Doubly Linked List Class

The main DoublyLinkedList class will contain methods to insert, delete and print nodes in the linked list.

We will use a dummy head and tail node to avoid edge cases of inserting and deleting around the actual list boundaries.

class DoublyLinkedList:

    def __init__(self):
        self.head = Node(0)
        self.tail = Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.length = 0

The constructor initializes an empty list with dummy head and tail nodes. Their next and prev pointers point to each other to create a circular sentinel list.

We also initialize a length property to track the number of actual nodes in the list (excluding head and tail).

Inserting Nodes

To insert a new node in the doubly linked list, we need to update the next and prev pointers of the adjacent nodes accordingly.

There are several cases to handle:

Insert at Head

Update new node’s next to reference current head
Update head’s prev to new node
Update head to new node

Insert at Tail

Update new node’s prev to current tail
Update tail’s next to new node
Update tail to new node

Insert in Middle

Update new node’s next pointer to current node’s next
Update new node’s prev pointer to current node
Update current node’s next to new node
Update next node’s prev to new node

This can be implemented in the following insert() method:

def insert(self, data):

    new_node = Node(data)

    if self.length == 0:
        self.head.next = new_node
        new_node.prev = self.head
        self.tail = new_node
    elif self.length == 1:
        self.head.next.prev = new_node
        new_node.next = self.tail
        self.head.next = new_node
        new_node.prev = self.head
    else:
        self.tail.prev.next = new_node
        new_node.prev = self.tail.prev
        new_node.next = self.tail
        self.tail.prev = new_node

    self.length += 1

Based on the list length, we handle the three cases:

Inserting into empty list
Inserting with only head and tail nodes
General case of inserting in the middle

The new node pointers are updated accordingly and the length is incremented.

Let’s test it out:

dll = DoublyLinkedList()
dll.insert(1)
dll.insert(2)
dll.insert(3)

print_nodes(dll.head.next) # 1 2 3

Deleting Nodes

To delete a node from the doubly linked list, we need to patch up the next and prev pointers on the adjacent nodes.

There are several cases similar to insertion:

Delete Head Node

Update head to head’s next node
Update new head’s prev to None

Delete Tail Node

Update tail to tail’s prev node
Update new tail’s next to None

Delete Middle Node

Update next node’s prev to deleted node’s prev
Update prev node’s next to deleted node’s next

This can be implemented in the following delete() method:

def delete(self, node):

    if self.length == 1:
        self.head.next = self.tail
        self.tail.prev = self.head
    elif node == self.head.next:
        self.head.next = self.head.next.next
        self.head.next.prev = self.head
    elif node == self.tail.prev:
        self.tail.prev.prev.next = self.tail
        self.tail.prev = self.tail.prev.prev
    else:
        node.prev.next = node.next
        node.next.prev = node.prev

    self.length -= 1

Based on the list length and position of the node, we handle the edge cases and general case of updating the next and prev pointers around the node being deleted.

Let’s test deleting the head and tail nodes:

dll.delete(dll.head.next) # Delete head
print_nodes(dll.head.next) # 2 3

dll.delete(dll.tail.prev) # Delete tail
print_nodes(dll.head.next) # 2

Traversing the Doubly Linked List

Since each node contains pointers in both directions, we can traverse the doubly linked list from head to tail or vice versa.

Here is a traverse_forward() method to traverse the list in forward direction:

def traverse_forward(self):
    temp = self.head.next

    while temp != self.tail:
        print(temp.data, end=" ")
        temp = temp.next

    print()

It starts from the node after the head and prints each node’s data while traversing through the next pointers until reaching the tail.

Similarly, we can define a traverse_backward() method:

def traverse_backward(self):
    temp = self.tail.prev

    while temp != self.head:
        print(temp.data, end=" ")
        temp = temp.prev

    print()

This starts from the node before the tail and prints each node’s data while traversing backwards using the prev pointers until reaching the head.

Let’s test out forward and backward traversal:

dll.traverse_forward() # 2
dll.traverse_backward() # 2

Time and Space Complexity

Time Complexity: All operations like insertion, deletion and access have an average time complexity of O(1). Only traversal is O(N) since we need to traverse N nodes.
Space Complexity: The space required is O(N) since we need to allocate N actual nodes to store N elements in the linked list.

In summary, doubly linked lists provide efficient constant time insertions and deletions but requires more memory for the extra pointer attribute in each node compared to singly linked lists.

Applications of Doubly Linked Lists

Some real-world applications that can utilize doubly linked list data structures include:

Browser History - Browsers use doubly linked lists to store visit history and enable forward and backward navigation through pages.
Undo/Redo Functionality - Editors leverage doubly linked lists to implement unlimited undo/redo features by storing edit history.
Music Playlists - Music apps can use doubly linked lists to efficiently shuffle songs in playlists and traverse forwards/backwards.
Blockchain - Each block in a blockchain network points to its previous and next block forming a doubly linked list of blocks.
Multi-level Game Maps - Game levels can be modeled as a doubly linked list to allow players to progress forward or go back to previous levels.

Summary

In this guide, you learned how to implement a doubly linked list data structure in Python. The key takeaways include:

Each node stores data and pointers to next and previous nodes
Dummy head and tail nodes simplify insertion and deletion logic
Methods insert(), delete() and traverse() provide core linked list functionality
Works well for undo/redo, history, and back/forward navigation features

Doubly linked lists add useful traversal and deletion capabilities over normal linked lists. They serve as the backbone for a variety of applications such as editor undo/redo, browser history, music playlists and blockchain.

Hopefully this provides a solid foundation on working with this fundamental data structure in your Python programs!