ReviseAlgo Logo

Linked Lists

Linked List Operations

Master Linked List insertions, traversals, and deletions using the Dummy Head pattern to eliminate edge cases.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Linked List Operations?

Linked List Operations include traversing (visiting each node), searching for a target value, inserting a new node, and deleting a node from the list.

Why study them?

Unlike arrays where index updates are native, linked list updates are done by manually re-wiring pointers. If you perform these updates in the wrong sequence, you will break the links, losing access to the rest of the list.

Where is it Used?

  • Task Queues: Appending and removing processes sequentially.
  • Memory allocators: Appending free memory nodes to memory lists.

    • 2. Mental Model: Re-wiring Train Car Hitches

    Imagine you have a chain of train cars: Car A -> Car B -> Car C. You want to insert a new Car X between Car A and Car B: 1. You hook Car X to Car B first: Car X -> Car B. 2. You unhook Car A from Car B and hook it to Car X: Car A -> Car X. 3. If you did this in reverse (unhooking Car A from Car B first), Car B and Car C would roll down the hill and be lost!

    3. Core Algorithms & Implementations

    The Dummy Head Pattern

    When deleting a node by value, deleting the first node (head) is normally an annoying edge case because there is no "previous" node to re-link, requiring you to modify the global head pointer. By introducing a Dummy Head node (dummy.next = head), the actual head node is now the second node. This guarantees that every valid node has a previous node, eliminating special edge cases.

    4. Visual Trace: Deletion by Value

    Deleting node 20 from list 10 -> 20 -> 30 using a Dummy Head:

    5. Real-World Applications

  • Memory Fragmentation Management: Keeping lists of free memory pools. Allocating memory deletes a block node, and deallocating memory inserts a block node.
  • Transaction Logs: Appending transactions sequentially to ledger systems.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers verify edge-case robustness:
  • "Given a linked list and a value, delete all occurrences." -> Requires a loop with dummy head because the head node itself might be deleted.
  • "Delete a node in a singly linked list in-place given ONLY access to that node." -> You cannot find its preceding node. Work around this by copying the next node's value into the target node, then skipping the next node: node.val = node.next.val; node.next = node.next.next;!

    • Common Mistakes

    Warning: 1. Memory Leak on Deletions in C++: Simply skipping a node via curr->next = curr->next->next leaves the deleted node floating in memory heap. Always store a reference and call delete to free it.
    > 2. Forgetting the next reference: Rewiring curr.next = newNode before updating newNode.next = curr.next disconnects the tail of the list permanently.

    7. Summary

  • Dummy Node: Eliminates special code blocks for operations modifying the head.
  • Rewiring Rule: Always link the new node's successor first before updating the previous node's successor.
  • Memory: In C++, explicitly free deleted node instances.

    • 8. Quiz

    Question 1: Why does the Dummy Head pattern simplify deletions? Answer: Because it provides a guaranteed previous node for every element in the list, allowing us to delete the actual first node (head) using the exact same pointer adjustment code as any internal node.
    Question 2: What is the time complexity to insert a node at the tail of a Singly Linked List of size N, if we only maintain a head pointer? Answer: O(N) time. Because we only have a reference to the head, we must traverse the entire list step-by-step to find the tail node before we can append the new element.
    Question 3: How can we insert at the tail in O(1) time? Answer: By maintaining a second pointer reference, tail, which always points to the final node of the list. We can then insert in constant time using: tail.next = newNode; tail = newNode;.
    Question 4: What happens if we write curr.next = newNode first during insertion? Answer: We lose the reference to curr.next and all subsequent nodes. The tail portion of the list becomes unreachable and is orphaned (causing a memory leak or garbage collection).
    Question 5: What is the output of deleting target 5 from list [5 -> 5 -> 10] using deleteValue()? Answer: [10]. The dummy head ensures all leading matching values are skipped, returning the node containing 10.