Dynamic Linked Lists

========================

A dynamic linked list (DLL) is a type of data structure that consists of nodes, each of which contains a value and a reference (or “link”) to the next node in the sequence. This allows for efficient insertion and deletion of nodes at any position in the list.

Overview

Dynamic Linked Lists are similar to static linked lists, but they allow for dynamic adjustment of the list size as elements are added or removed. This is achieved by using pointers to each element, which can be relocated when necessary.

Components

A DLL typically consists of the following components:

• Node: Each node in the list contains a value and two pointers: prev (previous node) and next (next node). The prev pointer points to the previous node in the sequence, while the next pointer points to the next node.
• Head: The head of the DLL is the first node in the list. It contains a reference to the next node.
• Tail: The tail of the DLL is the last node in the list. It contains a reference to the previous node.

Methods

Here are some common methods used for dynamic linked lists:

Insertion

When inserting a new node at the beginning or end of the list, we need to update the prev and next pointers accordingly.

def insert_at_head(node, value):
    new_node = Node(value)
    new_node.next = node.prev
    if not node.prev:
        node.prev = new_node
    else:
        node.prev.next = new_node

Deletion

When deleting a node from the list, we need to update the prev and next pointers of its siblings.

def delete(node):
    prev_node = node.prev
    next_node = node.next
    
    if node == node.prev:
        # Node is at the head of the list
        node.prev = None
    else:
        # Node is in the middle of the list
        prev_node.next = next_node

Traversal

To traverse the list, we can start from the head and move to each subsequent node.

def traverse(node):
    while node:
        print(node.value)
        node = node.next

Implementation

Here’s an example implementation of a DLL in Python:

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

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

    def insert_at_head(self, value):
        new_node = Node(value)
        if not self.head:
            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 delete(self, node):
        prev_node = node.prev
        next_node = node.next
        
        if node == self.head:
            # Node is at the head of the list
            self.head = prev_node
            if not prev_node:
                self.tail = None
        else:
            # Node is in the middle of the list
            prev_node.next = next_node

    def traverse(self):
        current_node = self.head
        while current_node:
            print(current_node.value)
            current_node = current_node.next

# Example usage:
dll = DynamicLinkedList()
dll.insert_at_head(1)
dll.insert_at_head(2)
dll.insert_at_head(3)

print("Traversing the list:")
dll.traverse()

dll.delete(dll.head)

print("\nAfter deletion:")
dll.traverse()

Advantages

Dynamic Linked Lists have several advantages, including:

• Efficient insertion and deletion: DLLs can insert or delete nodes at any position in the list without affecting the overall size of the list.
• Flexible sizing: DLLs can dynamically adjust their size as elements are added or removed.

However, DLLs also have some disadvantages, such as:

• More complex implementation: DLLs require more complex code and logic than static linked lists.
• Higher memory usage: Each node in a DLL requires additional memory to store the prev and next pointers.