Data Structures
  • Implement insert, delete, search, reverse in O(n) or better
  • Use slow/fast pointer technique for middle node and cycle detection
  • Learn dummy node trick to simplify edge cases in merging

Linked List Operations

You've got a linked list. Now let's operate on it.

Insert at Head

Add a node at the beginning.

def insertAtHead(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node  # This is the new head

Before: head → A → B → C → null

After inserting X: head → X → A → B → C → null

O(1). Two pointer updates.

Insert at Tail

Add a node at the end.

def insertAtTail(head, data):
    new_node = Node(data)
    
    if head is None:
        return new_node
    
    current = head
    while current.next is not None:
        current = current.next
    
    current.next = new_node
    return head

O(n). Must traverse to the end.

Optimization: Keep a tail pointer.

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def insertAtTail(self, data):
        new_node = Node(data)
        
        if self.tail is None:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

Now O(1). Just update tail.

Insert at Position

Insert at index i.

def insertAtPosition(head, data, position):
    if position == 0:
        return insertAtHead(head, data)
    
    new_node = Node(data)
    current = head
    
    for _ in range(position - 1):
        if current is None:
            return head  # Position out of bounds
        current = current.next
    
    if current is None:
        return head
    
    new_node.next = current.next
    current.next = new_node
    return head

Before: A → B → C → null, insert X at position 2

After: A → B → X → C → null

O(n). Traverse to position.

Delete by Value

Remove the first node with a specific value.

def deleteByValue(head, data):
    if head is None:
        return None
    
    # Delete head
    if head.data == data:
        return head.next
    
    current = head
    while current.next is not None:
        if current.next.data == data:
            current.next = current.next.next  # Bypass
            return head
        current = current.next
    
    return head  # Not found

Before: A → B → C → null, delete B

After: A → C → null

O(n). Find the node and its predecessor.

Delete at Position

Remove node at index i.

def deleteAtPosition(head, position):
    if head is None:
        return None
    
    if position == 0:
        return head.next
    
    current = head
    for _ in range(position - 1):
        if current is None or current.next is None:
            return head
        current = current.next
    
    if current.next is None:
        return head
    
    current.next = current.next.next
    return head

O(n). Traverse to position.

Search

Find if a value exists.

def search(head, data):
    current = head
    while current is not None:
        if current.data == data:
            return True
        current = current.next
    return False

O(n). Linear search.

Get Length

Count nodes.

def getLength(head):
    count = 0
    current = head
    while current is not None:
        count += 1
        current = current.next
    return count

O(n). Must visit all nodes.

Reverse

Reverse the list.

def reverse(head):
    prev = None
    current = head
    
    while current is not None:
        next_node = current.next  # Save next
        current.next = prev        # Reverse pointer
        prev = current             # Move prev forward
        current = next_node        # Move current forward
    
    return prev  # New head

Before: A → B → C → null

After: C → B → A → null

Step-by-step:

Initial: prev=null, current=A

Step 1:
  next_node = B
  A.next = null (was B)
  prev = A
  current = B
  Result so far: null ← A   B → C

Step 2:
  next_node = C
  B.next = A (was C)
  prev = B
  current = C
  Result so far: null ← A ← B   C → null

Step 3:
  next_node = null
  C.next = B (was null)
  prev = C
  current = null
  Result: null ← A ← B ← C

Return prev (C), the new head.

O(n). One pass.

Find Middle

Find the middle node.

Slow/Fast Pointer Technique:

def findMiddle(head):
    if head is None:
        return None
    
    slow = head
    fast = head
    
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    
    return slow  # Middle node

For A → B → C → D → E, slow ends at C.

For A → B → C → D, slow ends at C (second middle).

O(n). Fast moves twice as fast, so when fast reaches end, slow is at middle.

Detect Cycle

Check if the list has a cycle (a node points back to a previous node).

Floyd's Cycle Detection (Tortoise and Hare):

def hasCycle(head):
    if head is None:
        return False
    
    slow = head
    fast = head
    
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True  # Cycle detected
    
    return False

If there's a cycle, fast will eventually catch up to slow. If no cycle, fast reaches null.

O(n).

Remove Duplicates (Sorted List)

For a sorted linked list, remove duplicates.

def removeDuplicates(head):
    if head is None:
        return None
    
    current = head
    while current.next is not None:
        if current.data == current.next.data:
            current.next = current.next.next  # Skip duplicate
        else:
            current = current.next
    
    return head

Before: 1 → 1 → 2 → 3 → 3 → null

After: 1 → 2 → 3 → null

O(n). One pass.

Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list.

def mergeSorted(head1, head2):
    dummy = Node(0)  # Dummy node for simplicity
    tail = dummy
    
    while head1 is not None and head2 is not None:
        if head1.data <= head2.data:
            tail.next = head1
            head1 = head1.next
        else:
            tail.next = head2
            head2 = head2.next
        tail = tail.next
    
    # Attach remaining
    if head1 is not None:
        tail.next = head1
    else:
        tail.next = head2
    
    return dummy.next  # Skip dummy

List 1: 1 → 3 → 5
List 2: 2 → 4 → 6

Result: 1 → 2 → 3 → 4 → 5 → 6

O(n + m) where n and m are lengths.

Print List

Traverse and print all nodes.

def printList(head):
    current = head
    while current is not None:
        print(current.data, end=" → ")
        current = current.next
    print("null")

O(n).

Clone a List

Create a deep copy.

def clone(head):
    if head is None:
        return None
    
    new_head = Node(head.data)
    current_old = head.next
    current_new = new_head
    
    while current_old is not None:
        current_new.next = Node(current_old.data)
        current_new = current_new.next
        current_old = current_old.next
    
    return new_head

O(n). Create new nodes for each old node.

Example Usage

# Build list: 1 → 2 → 3 → 4 → 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

printList(head)  # 1 → 2 → 3 → 4 → 5 → null

# Insert at head
head = insertAtHead(head, 0)
printList(head)  # 0 → 1 → 2 → 3 → 4 → 5 → null

# Delete by value
head = deleteByValue(head, 3)
printList(head)  # 0 → 1 → 2 → 4 → 5 → null

# Reverse
head = reverse(head)
printList(head)  # 5 → 4 → 2 → 1 → 0 → null

# Find middle
middle = findMiddle(head)
print(f"Middle: {middle.data}")  # 2

# Length
print(f"Length: {getLength(head)}")  # 5

The Pattern

Most linked list operations fall into:

  • Traversal: O(n) to visit nodes
  • Insert/Delete with pointer: O(1) once you have the position
  • Search: O(n) linear
  • Two-pointer tricks: Slow/fast for middle, cycle detection

Understanding these operations means knowing:

  • How to manipulate pointers without losing references
  • When to use dummy nodes (simplifies edge cases)
  • Classic techniques: slow/fast pointers, reversal

Master these, and you'll solve most linked list problems.