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.

## Table of Contents

## Open Table of Contents

## 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!