Let's discuss the intricacies of implementing a doubly linked list.

• How would you approach designing a doubly linked list class, considering the core functionalities such as insertion, deletion, and traversal in both forward and reverse directions?
• Illustrate with examples how you would handle edge cases, such as inserting at the beginning or end of the list, or deleting the only node in the list.
• Specifically, walk me through the code you would write for an insertAfter method, which inserts a new node after a given node, and analyze its time complexity. Furthermore, explain how you would prevent memory leaks when removing nodes from the list.

Doubly Linked List Implementation

Let's delve into the implementation of a doubly linked list, covering design considerations, edge case handling, and code examples.

1. Doubly Linked List Class Design

A doubly linked list consists of nodes, each containing data and pointers to the next and previous nodes. Here's how we can approach designing a doubly linked list class:

• Node Class:
  • Data field to store the value.
  • next pointer to the next node.
  • prev pointer to the previous node.
• DoublyLinkedList Class:
  • head pointer to the first node.
  • tail pointer to the last node.
  • size to track the number of nodes.
  • Methods for insertion (insertAtHead, insertAtTail, insertAfter), deletion (deleteHead, deleteTail, deleteNode), and traversal (traverseForward, traverseBackward).

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def get_size(self):
        return self.size

    def insert_at_head(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.size += 1

    def insert_at_tail(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def delete_head(self):
        if self.is_empty():
            return
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
        self.size -= 1

    def delete_tail(self):
        if self.is_empty():
            return
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None
        self.size -= 1

    def traverse_forward(self):
        if self.is_empty():
            return []
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return result

    def traverse_backward(self):
        if self.is_empty():
            return []
        result = []
        current = self.tail
        while current:
            result.append(current.data)
            current = current.prev
        return result

    def insert_after(self, node, data):
        if node is None:
            return  # or raise an exception

        new_node = Node(data)
        new_node.next = node.next
        new_node.prev = node

        if node.next:
            node.next.prev = new_node
        else:
            self.tail = new_node  # node was the last node

        node.next = new_node
        self.size += 1

    def delete_node(self, node):
        if node is None:
            return

        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next

        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

        self.size -= 1
        del node  # Important: prevent memory leaks by deallocating the node

# Example Usage
dll = DoublyLinkedList()
dll.insert_at_head(1)
dll.insert_at_tail(2)
dll.insert_at_tail(3)

print("Forward Traversal:", dll.traverse_forward())
print("Backward Traversal:", dll.traverse_backward())

node_to_insert_after = dll.head
dll.insert_after(node_to_insert_after, 4)

print("Forward Traversal after insertion:", dll.traverse_forward())


node_to_delete = node_to_insert_after.next
dll.delete_node(node_to_delete)

print("Forward Traversal after deletion:", dll.traverse_forward())

2. Handling Edge Cases

• Inserting at the beginning:
  • If the list is empty, the new node becomes both head and tail.
  • Otherwise, update the prev pointer of the current head and update head to the new node.
• Inserting at the end:
  • If the list is empty, the new node becomes both head and tail.
  • Otherwise, update the next pointer of the current tail and update tail to the new node.
• Deleting the only node:
  • Set both head and tail to None.
• Deleting the head:
  • Update head to the next node and set the prev pointer of the new head to None.
• Deleting the tail:
  • Update tail to the previous node and set the next pointer of the new tail to None.
• Inserting after a specific node
  • If the specific node is the tail, it becomes equivalent to inserting at the tail.

3. insertAfter Method

Here's the code for an insertAfter method:

def insert_after(self, node, data):
    if node is None:
        return  # or raise an exception

    new_node = Node(data)
    new_node.next = node.next
    new_node.prev = node

    if node.next:
        node.next.prev = new_node
    else:
        self.tail = new_node  # node was the last node

    node.next = new_node
    self.size += 1

Time Complexity Analysis

The insertAfter method has a time complexity of O(1) because it only involves updating a few pointers, regardless of the list size.

Preventing Memory Leaks

When removing nodes, it's crucial to prevent memory leaks. After updating the pointers, deallocate the memory occupied by the node:

def delete_node(self, node):
    if node is None:
        return

    if node.prev:
        node.prev.next = node.next
    else:
        self.head = node.next

    if node.next:
        node.next.prev = node.prev
    else:
        self.tail = node.prev

    self.size -= 1
    del node  # Important: prevent memory leaks by deallocating the node

The del node statement in Python releases the memory occupied by the node. In languages like C++, you would use delete node; to achieve the same.