Doubly Linked Lists - Implementation and Comparison#

Welcome to Day 9 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore doubly linked lists, implement one from scratch, and compare it with singly linked lists.

What is a Doubly Linked List?#

A doubly linked list is a type of linked list where each node contains data and two pointers:

1. A pointer to the next node
2. A pointer to the previous node

This bi-directional linking allows for more flexible operations, especially when traversing the list in reverse or deleting nodes.

Implementing a Doubly Linked List#

Let’s implement a doubly linked list with basic operations:

 1class Node:
 2    def __init__(self, data):
 3        self.data = data
 4        self.prev = None
 5        self.next = None
 6
 7class DoublyLinkedList:
 8    def __init__(self):
 9        self.head = None
10        self.tail = None
11
12    def is_empty(self):
13        return self.head is None
14
15    def append(self, data):
16        new_node = Node(data)
17        if self.is_empty():
18            self.head = self.tail = new_node
19        else:
20            new_node.prev = self.tail
21            self.tail.next = new_node
22            self.tail = new_node
23
24    def prepend(self, data):
25        new_node = Node(data)
26        if self.is_empty():
27            self.head = self.tail = new_node
28        else:
29            new_node.next = self.head
30            self.head.prev = new_node
31            self.head = new_node
32
33    def delete(self, data):
34        current = self.head
35        while current:
36            if current.data == data:
37                if current.prev:
38                    current.prev.next = current.next
39                else:
40                    self.head = current.next
41                
42                if current.next:
43                    current.next.prev = current.prev
44                else:
45                    self.tail = current.prev
46                
47                return
48            current = current.next
49
50    def display_forward(self):
51        current = self.head
52        while current:
53            print(current.data, end=" <-> ")
54            current = current.next
55        print("None")
56
57    def display_backward(self):
58        current = self.tail
59        while current:
60            print(current.data, end=" <-> ")
61            current = current.prev
62        print("None")

Comparing Singly and Doubly Linked Lists#

Advantages of Doubly Linked Lists:#

1. Bi-directional Traversal: Can be traversed both forward and backward.
2. Efficient Deletion: Deleting a node is more efficient as we have direct access to the previous node.
3. Insert Before Operation: Inserting a node before a given node is easier.

Disadvantages of Doubly Linked Lists:#

1. Extra Memory: Requires extra space for the previous pointer.
2. Complexity: Implementation is slightly more complex due to the extra pointer.

Time Complexity Comparison#

Deleting a node#

Reverse Traverssal#

Example Usage#

Common Interview Questions#

1. Implement a Palindrome Checker: Use a doubly linked list to check if a given sequence is a palindrome.
2. LRU Cache: Implement a Least Recently Used (LRU) cache using a doubly linked list and a hash map.
3. Flatten a Multilevel Doubly Linked List: Given a doubly linked list where each node might have a child list, flatten it into a single level linked list.

Exercise#

1. Implement a method insert_after(self, target_data, new_data) that inserts a new node with new_data after the first occurrence of a node with target_data.
2. Write a method reverse(self) that reverses the doubly linked list in-place.
3. Implement a method is_palindrome(self) that checks if the doubly linked list is a palindrome.

Summary#

Today, we explored doubly linked lists, their implementation, and how they compare to singly linked lists. Doubly linked lists offer more flexibility in certain operations at the cost of additional memory usage. Understanding the trade-offs between different data structures is crucial for choosing the right tool for specific problems.

Tomorrow, we’ll dive into more advanced linked list operations and tackle some common interview problems related to linked lists. Stay tuned!

Solution#

 1class DoublyLinkedList:
 2    # ... existing methods (append, prepend, delete, display_forward) ...
 3
 4    def insert_after(self, target_data, new_data):
 5        current = self.head
 6        while current:
 7            if current.data == target_data:
 8                new_node = Node(new_data)
 9                new_node.prev = current
10                new_node.next = current.next
11                if current.next:
12                    current.next.prev = new_node
13                else:
14                    self.tail = new_node
15                current.next = new_node
16                return True
17            current = current.next
18        return False
19
20    def reverse(self):
21        current = self.head
22        self.tail = self.head
23        prev = None
24        while current:
25            prev = current.prev
26            current.prev = current.next
27            current.next = prev
28            current = current.prev
29        if prev:
30            self.head = prev.prev
31
32    def is_palindrome(self):
33        front, back = self.head, self.tail
34        while front and back and front is not back and back.next is not front:
35            if front.data != back.data:
36                return False
37            front = front.next
38            back = back.prev
39        return True