Understanding Linked Lists in Python

Linked lists are a fundamental linear data structure where elements are not stored at contiguous memory locations. Instead, elements are linked using pointers. This article explores the concept of linked lists, different types (singly, doubly, circular), their operations, and how to implement them in Python.

What is a Linked List?

A linked list consists of nodes where each node contains:

1. Data: The actual value stored in the node.
2. Pointer(s): Reference(s) to the next (and possibly previous) node in the list.

Unlike arrays (or Python lists), linked lists offer more flexibility in terms of dynamic memory allocation and ease of insertion/deletion, especially in the middle of the list. However, they lack direct (O(1)) access to elements by index.

Types of Linked Lists

1. Singly Linked List

Each node contains data and a pointer to the next node. The last node's pointer is typically None (or null). Traversal is unidirectional.

Node Structure (Singly):

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    # ... methods for operations

2. Doubly Linked List

Each node contains data, a pointer to the next node, and a pointer to the previous node. This allows for bidirectional traversal.

Node Structure (Doubly):

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
    # ... methods for operations

3. Circular Linked List

The last node's next pointer points back to the first node (head), forming a circle. This can be implemented as singly or doubly circular.

Common Operations on Linked Lists

Let's consider operations for a singly linked list. Similar logic applies to other types with adjustments for additional pointers.

a. Traversal

Iterating through the list, usually starting from the head.

# In SinglyLinkedList class
def display(self):
    elements = []
    current_node = self.head
    while current_node:
        elements.append(current_node.data)
        current_node = current_node.next
    print(" -> ".join(map(str, elements)))

b. Insertion

• At the beginning: Create a new node, point its next to the current head, and update the head to be the new node. (O(1))
• At the end: Traverse to the last node, point its next to the new node. (O(n) for singly, O(1) if tail pointer is maintained)
• At a specific position: Traverse to the node before the desired position, then adjust pointers. (O(n))

# In SinglyLinkedList class (insert at beginning)
def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

c. Deletion

• From the beginning: Update head to head.next. (O(1))
• From the end: Traverse to the second-to-last node, set its next to None. (O(n))
• A specific value/node: Find the node and its predecessor, then bypass the node. (O(n))

# In SinglyLinkedList class (delete a node by value)
def delete_node(self, key):
    current_node = self.head
    # If head node itself holds the key to be deleted
    if current_node and current_node.data == key:
        self.head = current_node.next
        current_node = None
        return
    
    prev_node = None
    while current_node and current_node.data != key:
        prev_node = current_node
        current_node = current_node.next
        
    if current_node is None: # Key not found
        return
        
    prev_node.next = current_node.next
    current_node = None

d. Search

Traverse the list until the element is found or the end is reached. (O(n))

# In SinglyLinkedList class
def search(self, key):
    current_node = self.head
    while current_node:
        if current_node.data == key:
            return True
        current_node = current_node.next
    return False

Performance Characteristics (Big O)

Operation	Singly Linked List	Doubly Linked List	Python List (Array)
Access (by index)	O(n)	O(n)	O(1)
Search (by value)	O(n)	O(n)	O(n)
Insertion (begin)	O(1)	O(1)	O(n)
Insertion (end)	O(n)*	O(1)*	O(1) (amortized)
Insertion (middle)	O(n)	O(n)	O(n)
Deletion (begin)	O(1)	O(1)	O(n)
Deletion (end)	O(n)	O(1)*	O(1)
Deletion (middle)	O(n)	O(n)	O(n)

* Can be O(1) if a tail pointer is maintained.

Advantages of Linked Lists

• Dynamic Size: Can easily grow or shrink.
• Ease of Insertion/Deletion: Adding or removing nodes (especially in the middle) is efficient (O(1) if you have a pointer to the previous node) compared to arrays where elements need shifting. This is a key difference from Python lists.

Disadvantages of Linked Lists

• No Random Access: Elements cannot be accessed directly by index in O(1) time. Traversal is required.
• Extra Memory: Pointers require additional memory space per node.
• Cache Performance: Elements are not stored contiguously, which can lead to poorer cache locality compared to arrays.

When to Use Linked Lists

• When you need frequent insertions and deletions from the middle of the list.
• When you don't know the size of the list in advance and need dynamic resizing.
• Implementing other data structures like stacks, queues, or adjacency lists for graphs.
• Applications where sequential access is common, and random access is rare.

Linked lists are a foundational concept. For example, the "chain" in blockchain technology is essentially a linked list where each block points to the previous one. Similarly, understanding linked structures is beneficial when exploring WebAssembly and its memory management, as it can interact with more complex data layouts.

Python Implementation Example (Singly Linked List)

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data): # Insert at the end
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def prepend(self, data): # Insert at the beginning
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def display(self):
        elements = []
        current_node = self.head
        while current_node:
            elements.append(str(current_node.data))
            current_node = current_node.next
        print(" -> ".join(elements))

# Example Usage
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.prepend(0)
sll.display()  # Output: 0 -> 1 -> 2 -> 3

Next Steps

With a grasp of linked lists, you're well-equipped to tackle more complex data structures that build upon them, such as Trees and Graphs. Understanding the trade-offs between linked lists and array-based lists is crucial for efficient programming.