Linked Lists: Implementation and Time Complexity Analysis

What Are Linked Lists?

A linked list is a linear data structure where elements — called nodes — are stored in non-contiguous memory locations. Each node contains two parts: the actual data and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not rely on contiguous memory allocation, which gives them unique advantages and trade-offs.

The fundamental building block is the Node. In its simplest form for a singly linked list, a node looks like this:

class Node:
    def __init__(self, data):
        self.data = data   # The value stored
        self.next = None   # Reference to the next node

Multiple nodes chained together form the linked list. The first node is called the head, and the last node points to None (or null), signaling the end of the list. There are several variants:

• Singly Linked List — Each node points only to the next node
• Doubly Linked List — Each node points to both the next and the previous node
• Circular Linked List — The last node points back to the head instead of null

Why Linked Lists Matter

Linked lists are not just an academic exercise — they form the foundation for many real-world data structures and systems:

• Dynamic memory allocation — Linked lists grow and shrink at runtime without expensive reallocation
• Hash table collision resolution — Separate chaining uses linked lists to handle collisions
• File systems — Many file systems use linked list structures for directory entries and block allocation
• Undo/Redo functionality — Applications maintain history using doubly linked lists
• Memory allocators — Free memory blocks are often tracked with linked list free lists

The key differentiator compared to arrays is the cost model for insertions and deletions. Arrays require O(n) shifting of elements for insert/delete at arbitrary positions, while linked lists can achieve O(1) insert/delete once you have a reference to the node — but you trade away O(1) random access.

Singly Linked List — Full Implementation

Below is a production-ready singly linked list implementation with detailed comments explaining each operation:

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


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

    # ─── Utility ────────────────────────────────────────────
    def __len__(self):
        """Returns the number of nodes in O(1) time."""
        return self._size

    def is_empty(self):
        """Check if the list is empty in O(1)."""
        return self.head is None

    def display(self):
        """Traverse and print all elements — O(n)."""
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" → ".join(elements) if elements else "(empty)")

    # ─── Insert Operations ─────────────────────────────────
    def prepend(self, data):
        """Insert a node at the beginning — O(1)."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self._size += 1

    def append(self, data):
        """Insert a node at the end — O(n) unless tail is tracked."""
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self._size += 1
            return

        current = self.head
        while current.next:          # Walk to the last node
            current = current.next
        current.next = new_node
        self._size += 1

    def insert_at(self, index, data):
        """Insert at a specific 0-based index — O(n)."""
        if index < 0 or index > self._size:
            raise IndexError("Index out of bounds")

        if index == 0:
            self.prepend(data)
            return

        new_node = Node(data)
        current = self.head
        # Move (index - 1) steps to reach the predecessor
        for _ in range(index - 1):
            current = current.next

        new_node.next = current.next
        current.next = new_node
        self._size += 1

    # ─── Delete Operations ─────────────────────────────────
    def delete_head(self):
        """Remove the first node — O(1)."""
        if self.head is None:
            raise ValueError("Cannot delete from empty list")
        removed_data = self.head.data
        self.head = self.head.next
        self._size -= 1
        return removed_data

    def delete_at(self, index):
        """Delete a node at a given index — O(n)."""
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")

        if index == 0:
            return self.delete_head()

        current = self.head
        for _ in range(index - 1):
            current = current.next

        removed_data = current.next.data
        current.next = current.next.next   # Bypass the target node
        self._size -= 1
        return removed_data

    def delete_by_value(self, value):
        """Delete the first occurrence of a value — O(n)."""
        if self.head is None:
            return False

        # Special case: head holds the value
        if self.head.data == value:
            self.head = self.head.next
            self._size -= 1
            return True

        current = self.head
        while current.next:
            if current.next.data == value:
                current.next = current.next.next
                self._size -= 1
                return True
            current = current.next
        return False   # Value not found

    # ─── Search Operations ─────────────────────────────────
    def search(self, value):
        """Return the index of the first occurrence — O(n)."""
        current = self.head
        index = 0
        while current:
            if current.data == value:
                return index
            current = current.next
            index += 1
        return -1   # Sentinel for "not found"

    def get_at(self, index):
        """Access element by index — O(n)."""
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        current = self.head
        for _ in range(index):
            current = current.next
        return current.data


# ─── Usage Example ─────────────────────────────────────────
if __name__ == "__main__":
    sll = SinglyLinkedList()
    sll.append(10)
    sll.append(20)
    sll.prepend(5)
    sll.insert_at(2, 15)       # Insert 15 at index 2
    sll.display()              # Output: 5 → 10 → 15 → 20
    print("Size:", len(sll))   # Output: Size: 4
    print("Search 15:", sll.search(15))  # Output: Search 15: 2
    sll.delete_at(1)           # Remove element at index 1 (value 10)
    sll.display()              # Output: 5 → 15 → 20

Doubly Linked List — Full Implementation

A doubly linked list adds a prev pointer to each node, enabling bidirectional traversal and O(1) deletion when you hold a reference to the node itself. Here is the complete implementation:

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


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None      # Tracking tail gives O(1) append
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self.head is None

    def display_forward(self):
        """Print from head to tail."""
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" → ".join(elements) if elements else "(empty)")

    def display_backward(self):
        """Print from tail to head — demonstrates prev pointers."""
        current = self.tail
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.prev
        print(" ← ".join(elements) if elements else "(empty)")

    def append(self, data):
        """Add to the end — O(1) thanks to tail pointer."""
        new_node = DoublyNode(data)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self._size += 1

    def prepend(self, data):
        """Add to the beginning — O(1)."""
        new_node = DoublyNode(data)
        if self.head is None:
            self.head = 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(self, index, data):
        """Insert at a specific index — O(n) traversal."""
        if index < 0 or index > self._size:
            raise IndexError("Index out of bounds")

        if index == 0:
            self.prepend(data)
            return
        if index == self._size:
            self.append(data)
            return

        new_node = DoublyNode(data)
        # Traverse to the node currently at the target index
        current = self.head
        for _ in range(index):
            current = current.next

        # Wire the new node between current.prev and current
        predecessor = current.prev
        predecessor.next = new_node
        new_node.prev = predecessor
        new_node.next = current
        current.prev = new_node
        self._size += 1

    def delete_at(self, index):
        """Delete by index — O(n) traversal, O(1) removal."""
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")

        # Special case: removing the only node
        if self._size == 1:
            removed = self.head.data
            self.head = self.tail = None
            self._size -= 1
            return removed

        # Remove head
        if index == 0:
            removed = self.head.data
            self.head = self.head.next
            self.head.prev = None
            self._size -= 1
            return removed

        # Remove tail
        if index == self._size - 1:
            removed = self.tail.data
            self.tail = self.tail.prev
            self.tail.next = None
            self._size -= 1
            return removed

        # General case: middle removal
        current = self.head
        for _ in range(index):
            current = current.next

        removed = current.data
        current.prev.next = current.next
        current.next.prev = current.prev
        self._size -= 1
        return removed

    def delete_node(self, node_ref):
        """
        Delete a node given a direct reference — O(1).
        This is the killer feature of doubly linked lists.
        """
        if node_ref is None:
            return

        # If it's the head
        if node_ref.prev is None:
            self.head = node_ref.next
        else:
            node_ref.prev.next = node_ref.next

        # If it's the tail
        if node_ref.next is None:
            self.tail = node_ref.prev
        else:
            node_ref.next.prev = node_ref.prev

        self._size -= 1

    def search(self, value):
        """Linear search — O(n)."""
        current = self.head
        index = 0
        while current:
            if current.data == value:
                return index, current   # Return both index and node reference
            current = current.next
            index += 1
        return -1, None


# ─── Usage Example ─────────────────────────────────────────
if __name__ == "__main__":
    dll = DoublyLinkedList()
    dll.append("alpha")
    dll.append("beta")
    dll.prepend("start")
    dll.insert_at(2, "middle")
    dll.display_forward()     # Output: start → alpha → middle → beta
    dll.display_backward()    # Output: beta ← middle ← alpha ← start
    dll.delete_at(1)          # Remove "alpha"
    dll.display_forward()     # Output: start → middle → beta

Time Complexity Analysis

Understanding the time complexity of each operation is critical for making informed design decisions. Below is a comprehensive breakdown for both singly and doubly linked lists:

Complexity Table

Why Traversal Dominates

The O(n) cost for index-based operations comes from the fundamental nature of linked lists: there is no way to jump to an arbitrary position without walking through the chain. This is the price you pay for dynamic memory flexibility. In contrast, arrays offer O(1) random access but suffer O(n) insertions and deletions due to element shifting.

Amortized Analysis Note

When you insert at the tail of a singly linked list without a tail pointer, each append is O(n). However, if you maintain a tail pointer (as we did in the doubly linked list implementation), append becomes O(1). You can retrofit a tail pointer onto the SinglyLinkedList class trivially — just add self.tail and update it on append/prepend/delete operations. This is a classic example of how a small design change dramatically improves performance.

Common Patterns and Interview Problems

Linked lists appear frequently in technical interviews. Here are the most important patterns, each with complete working code:

1. Reverse a Singly Linked List (Iterative)

def reverse_list(head):
    """
    Reverse in-place — O(n) time, O(1) space.
    Returns the new head of the reversed list.
    """
    prev = None
    current = head
    while current:
        next_temp = current.next   # Save the next pointer
        current.next = prev        # Flip the link direction
        prev = current             # Move prev forward
        current = next_temp        # Move current forward
    return prev   # prev is now the new head

2. Detect Cycle (Floyd's Tortoise and Hare)

def has_cycle(head):
    """
    Returns True if a cycle exists — O(n) time, O(1) space.
    Uses two pointers moving at different speeds.
    """
    if not head or not head.next:
        return False

    slow = head
    fast = head.next
    while fast and fast.next:
        if slow == fast:
            return True
        slow = slow.next          # Moves 1 step
        fast = fast.next.next     # Moves 2 steps
    return False

3. Find the Middle Node (Fast/Slow Pointer)

def find_middle(head):
    """
    Returns the middle node — O(n) time, O(1) space.
    When fast reaches the end, slow is at the middle.
    """
    if not head:
        return None
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # For even length, returns the second middle

4. Merge Two Sorted Lists

def merge_sorted(list1, list2):
    """
    Merges two sorted linked lists into one sorted list — O(n + m).
    Uses a dummy head to simplify edge cases.
    """
    dummy = Node(0)           # Temporary placeholder
    tail = dummy              # tail tracks the last node of merged list

    while list1 and list2:
        if list1.data <= list2.data:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next

    # Attach any remaining nodes
    tail.next = list1 if list1 else list2
    return dummy.next   # Skip the dummy head

Best Practices for Linked List Code

• Always handle edge cases first — Empty list, single-node list, operations at head and tail. These are the most common sources of null-pointer exceptions and bugs.
• Use a dummy head node — For algorithms that modify the list structure (merge, partition, etc.), a dummy head eliminates special-case branching for the first element.
• Maintain a size counter — Updating self._size on every mutation gives you O(1) length queries at minimal cost.
• Track a tail pointer when beneficial — If you frequently append, the O(1) gain justifies the extra bookkeeping.
• Draw pointer diagrams — Before writing complex link manipulations, sketch the nodes and arrows. Update the pointers in the correct order to avoid losing references.
• Never lose the next pointer — When rearranging links, always save node.next to a temporary variable before overwriting it, or you'll orphan the rest of the list.
• Consider sentinel nodes for circular lists — A sentinel (self-referential node) simplifies boundary conditions in circular linked lists.
• Write thorough unit tests — Test insert/delete at positions 0, middle, last, and beyond bounds. Test on empty and single-element lists.

When to Choose a Linked List Over an Array

The decision hinges on your access patterns:

• Frequent insertions/deletions at the front or middle — Linked lists excel here (O(1) vs O(n) for arrays)
• Unknown or highly variable size — Linked lists grow dynamically without expensive reallocation
• No need for random access — If you never need list[k] in O(1), the linked list's traversal cost is acceptable
• Memory overhead is acceptable — Each node carries pointer overhead; for small data elements, this can double memory usage
• You need O(1) node deletion with a reference — Doubly linked lists are unmatched here; arrays require shifting

Conversely, stick with arrays (or dynamic arrays like Python lists) when you need O(1) random access, cache-friendly contiguous memory, or minimal per-element overhead.

Conclusion

Linked lists are a foundational data structure that every developer should understand deeply. While they may seem simple on the surface, their true power lies in the nuanced trade-offs they present: O(1) insertions and deletions at known positions versus O(n) traversal for arbitrary access. By implementing both singly and doubly linked lists from scratch, you gain an intuitive understanding of pointer manipulation, memory management, and algorithmic efficiency that transfers directly to trees, graphs, and other pointer-based structures.

The time complexity analysis reveals that linked lists are not universally superior — they shine in specific scenarios like queue implementations, adjacency lists in graphs, and anywhere frequent structural modifications occur. The key takeaway is to match the data structure to the problem's access patterns. Keep the complexity table handy, practice the common interview patterns until they become second nature, and always draw your pointer diagrams before writing code. Mastery of linked lists builds the mental model you need for every more advanced data structure that follows.