1. Introduction

A linked list is a linear data structure consisting of nodes, where each node holds some data and a reference (pointer) to the next node in sequence. This creates a chain of nodes that are not necessarily stored contiguously in memory. Unlike an array, the order is maintained by these pointers. The last node’s next pointer indicates a terminator (typically null).

Linked lists are common in coding interviews for problems involving pointer manipulation, such as reversing a list, detecting cycles, finding middle elements, or merging sorted lists. They also appear in system design contexts (e.g., LRU cache).

How to identify linked list problems:

Look for mentions of "nodes," "pointers," "next," "prev," "head," or "tail." If a problem involves frequent insertions/deletions in the middle of a sequence or requires in-place reordering without random index access, a linked list is likely intended.

2. Core Idea / Mental Model

Analogy: Think of a linked list as a train of connected cars. Each car (node) holds data and has couplers (pointers) to the next car (and previous in a doubly linked list). You traverse by moving from car to car.

• Singly Linked List: Each node points only to the next. Forward traversal only.
• Doubly Linked List: Each node points to both next and previous. Allows bidirectional traversal.

Key properties:

• Sequential Navigation: No direct index access; must follow the chain.
• Dynamic Structure: Nodes can be anywhere in memory. Insertions/deletions involve updating pointers, often O(1) once at the location.
• Pointers as Links: Head pointer starts the list. Tail pointer (optional) marks the end.

A mental model is a scavenger hunt: each clue (node) directs to the next. Inserting/deleting is like adding/removing clues and adjusting directions.

3. Base Template (Python)

Singly Linked List Example

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    def insert(self, data): # Insert at end
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        temp = self.head
        while temp.next: temp = temp.next
        temp.next = new_node

    def delete(self, key):
        if not self.head: return
        if self.head.data == key:
            self.head = self.head.next
            return
        temp = self.head
        while temp.next and temp.next.data != key:
            temp = temp.next
        if temp.next: temp.next = temp.next.next

    def traverse(self):
        elements = []
        temp = self.head
        while temp:
            elements.append(temp.data)
            temp = temp.next
        return elements

Explanation (Singly): head points to the first node. insert appends to tail. delete removes by value, handling head removal and finding the predecessor to adjust pointers. traverse collects node values.

Doubly Linked List Example

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None # For O(1) end operations

    def insert(self, data): # Insert at end
        new_node = DNode(data)
        if not self.head:
            self.head = self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def delete(self, key):
        temp = self.head
        while temp and temp.data != key: temp = temp.next
        if not temp: return # Key not found

        if temp == self.head: self.head = temp.next
        if temp == self.tail: self.tail = temp.prev
        
        if temp.prev: temp.prev.next = temp.next
        if temp.next: temp.next.prev = temp.prev

        if not self.head: self.tail = None # List became empty
        if not self.tail: self.head = None # List became empty


    def traverse(self): # Forward traversal
        elements = []
        temp = self.head
        while temp:
            elements.append(temp.data)
            temp = temp.next
        return elements

Explanation (Doubly): Nodes have prev and next. head and tail pointers maintained. insert at end is O(1). delete updates both prev and next pointers of neighbors, handling head/tail/middle cases.

4. Interactive Animation (Singly Linked List Operations)

The animation below demonstrates basic operations (insert at end, delete by value) on a singly linked list. Observe how pointers are manipulated to maintain the list structure.

5. Time & Space Complexity

For a list with n nodes:

• Traversal/Search: O(n) - must traverse sequentially.
• Insertion:
  • At head: O(1).
  • At end (singly without tail ptr): O(n) to find end, then O(1).
  • At end (singly with tail ptr, or doubly): O(1).
  • In middle (after finding position): O(1) for pointer updates. Finding position is O(n).
• Deletion:
  • Head: O(1).
  • Tail (singly without prev access): O(n) to find predecessor.
  • Tail (doubly with tail ptr): O(1).
  • Middle (after finding position): O(1) for pointer updates (doubly) or O(n) to find predecessor (singly). Finding position is O(n).

Space Complexity: O(n) to store n elements. Doubly linked lists use slightly more space per node (extra prev pointer).

6. Common Pitfalls

• Null pointer dereferencing: Always check for None before accessing node.next or node.prev. Handle empty list cases.
• Off-by-one errors in traversal: Stopping too early or too late, especially when finding node before target.
• Incorrect pointer updates: Forgetting to update all relevant pointers (e.g., prev in doubly, or both sides of a link). Draw diagrams!
• Forgetting special cases (head/tail changes): Insertions/deletions at list boundaries need careful head/tail updates.
• Memory leaks (in C/C++) or orphaned nodes: Ensure removed nodes are properly detached. Python handles garbage collection.
• Infinite loops: Accidental cycle creation if pointers are mismanaged. Ensure last node's next is None.
• Overcomplicating implementation: Consider dummy head nodes to simplify edge cases for head operations.