Linked Lists: Singly, Doubly, and Circular Variants

Linked lists trade O(1) random access for O(1) insertion and deletion at known positions. Each node stores its data plus a pointer to the next node (singly) or both next and previous (doubly). This scattered memory layout makes them flexible but cache-unfriendly—understanding when to use them matters.

Introduction

A linked list is a linear data structure where elements (nodes) are connected via pointers rather than stored contiguously. Each node contains its data and a reference to the next node. Linked lists trade O(1) random access for O(1) insertion and deletion at arbitrary positions—a fundamental trade-off that makes them essential in specific scenarios.

Linked lists matter because they form the backbone of many common abstractions: stacks, queues, and deques are typically implemented with linked lists in production systems. They shine when you need frequent insertions and deletions at known positions, when element sizes vary significantly, or when you need data structures that grow and shrink without array resizing overhead.

Singly Linked List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


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

    def append(self, val):
        """O(1) append to end."""
        new_node = ListNode(val)
        if not self.head:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def prepend(self, val):
        """O(1) insert at head."""
        new_node = ListNode(val, self.head)
        self.head = new_node
        if not self.tail:
            self.tail = new_node
        self.size += 1

    def delete(self, val):
        """O(n) delete first occurrence."""
        if not self.head:
            return False

        if self.head.val == val:
            self.head = self.head.next
            if not self.head:
                self.tail = None
            self.size -= 1
            return True

        current = self.head
        while current.next:
            if current.next.val == val:
                if current.next == self.tail:
                    self.tail = current
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        return False

    def get(self, index):
        """O(n) get by index."""
        if index < 0 or index >= self.size:
            raise IndexError
        current = self.head
        for _ in range(index):
            current = current.next
        return current.val

    def reverse(self):
        """O(n) iterative reversal."""
        prev = None
        current = self.head
        self.tail = self.head

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        self.head = prev

Singly Linked List Node Structure

graph LR
    subgraph SinglyLinked["Singly Linked List"]
        direction LR
        A["Node A<br/>val: A<br/>next: &rarr;"] --> B["Node B<br/>val: B<br/>next: &rarr;"] --> C["Node C<br/>val: C<br/>next: null"]
    end
    Head["head"] --> A
    Tail["tail"] --> C

Each node has a value and a pointer to the next node. The head pointer marks the start, and tail.next is null to mark the end. You traverse starting at head, following next pointers until you hit null.

Doubly Linked List

class DListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, val):
        """O(1) append."""
        new_node = DListNode(val, self.tail, None)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node
        self.size += 1

    def prepend(self, val):
        """O(1) insert at head."""
        new_node = DListNode(val, None, self.head)
        if self.head:
            self.head.prev = new_node
        else:
            self.tail = new_node
        self.head = new_node
        self.size += 1

    def delete(self, node):
        """O(1) delete given node reference."""
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next

        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

        self.size -= 1

    def reverse(self):
        """O(n) reversal by swapping prev/next."""
        current = self.head
        self.tail, self.head = self.head, self.tail

        while current:
            current.prev, current.next = current.next, current.prev
            current = current.prev  # Was next before swap

Circular Linked List

class CircularLinkedList:
    """Circular list where last node points back to first."""

    def __init__(self):
        self.head = None
        self.size = 0

    def append(self, val):
        new_node = ListNode(val)
        if not self.head:
            new_node.next = new_node  # Points to itself
            self.head = new_node
        else:
            # Insert at end, before head
            new_node.next = self.head
            # Find last node
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
        self.size += 1

    def Josephus_circle(self, k):
        """
        Josephus problem: people standing in circle, eliminate every kth.
        Returns survivor's position.
        """
        if self.size == 1:
            return 0

        current = self.head
        while self.size > 1:
            # Count k-1 steps
            for _ in range(k - 1):
                current = current.next

            # Remove kth person (current.next)
            removed = current.next
            current.next = removed.next
            if removed == self.head:
                self.head = removed.next
            self.size -= 1

        return current.val

Cycle Detection

def has_cycle(head):
    """Floyd's cycle detection - O(n) time, O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False


def cycle_start(head):
    """
    Find start of cycle using Floyd's algorithm.
    Returns node where cycle begins, or None.
    """
    slow = fast = head
    has_cycle = False

    # Find meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break

    if not has_cycle:
        return None

    # Reset slow to head, move both one step at a time
    # They'll meet at cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow


def remove_cycle(head, cycle_start):
    """Remove cycle given the cycle start node."""
    if not cycle_start:
        return

    # Find the node just before cycle_start
    pointer = cycle_start
    while pointer.next != cycle_start:
        pointer = pointer.next

    pointer.next = None  # Break the cycle

Linked List vs Array

Operation	Linked List	Array
Access by index	O(n)	O(1)
Insert at head	O(1)	O(n)
Insert at tail	O(1)*	O(1)*
Delete at head	O(1)	O(n)
Delete at tail	O(n)**	O(1)
Insert in middle	O(1)***	O(n)
Memory overhead	+8-16 bytes/node	0
Cache performance	Poor	Excellent

*With tail pointer Requires traversal to find predecessor *If you have iterator to position

When to Use Each Type

Singly Linked List:

• Memory is constrained (only one pointer per node)
• You only need forward traversal
• Implementing stacks or simple queues

Doubly Linked List:

• You need to delete nodes given only a reference (O(1) deletion)
• You need reverse traversal
• Implementing LRU cache or deque

Circular Linked List:

• Round-robin scheduling
• Circular buffers
• Games with elimination (Josephus problem)

Production Failure Scenarios and Mitigations

Linked lists break in production in ways unit tests rarely catch. These are the failure modes I see most often, and how to stop them.

Null Pointer Dereference in C/C++

When you traverse a singly linked list and reach the end, you expect null. But what happens when a node’s next pointer is corrupted—perhaps from a buffer overflow or memory scribble? The program keeps walking into invalid memory until it segfaults or, worse, reads garbage and makes decisions based on corrupted data.

Mitigation: Use a sentinel node instead of null to mark the end. Sentinel nodes never get corrupted in the same way because they’re part of the list structure itself. In languages without manual memory management, use a safer abstraction like std::forward_list in C++ which handles edge cases, or switch to a GC’d language where this class of bug simply cannot happen.

Memory Leak from Unlinked Nodes

In languages without GC, if you remove a node from a linked list but forget to free it, you have a leak. More insidious: if the node is referenced elsewhere (a stale reference), freeing it creates a use-after-free. The leak compounds over time in long-running services—a leak of 64 bytes per operation running 10,000 times per second means 640KB leaked per second, or about 55GB per day.

Mitigation: Always pair removal with deallocation. Use RAII wrappers or smart pointers that auto-free. In C, establish a clear ownership model: either the list owns nodes and frees them on removal, or callers own them and must free after extraction. Do not mix models.

Race Conditions in Concurrent Access

Two threads modifying the same linked list simultaneously can corrupt it. Thread A removes node X while Thread B is traversing and holding a pointer to X. Thread A modifies X’s next pointer. Thread B tries to read X.next, which now points somewhere unexpected. The list structure can form cycles, lose nodes, or crash.

Mitigation: Use a mutex protecting all list mutations, or employ lock-free data structures designed for concurrency. If you need per-node locking (for very high contention), be careful about ABA problems where a node gets freed and reallocated with different contents between when a pointer is read and when it’s used. Readers-writer locks can help when reads vastly outnumber writes.

O(n) Traversal Causing Latency Spikes

In a real-time system or a latency-sensitive application like network packet processing, an O(n) linked list traversal at the wrong moment causes visible latency spikes. If your audio buffer processing depends on finding the right node in a linked list, a 1000-element list might cause an audible glitch.

Mitigation: If you need fast lookup, don’t use a linked list. Switch to a hash map or tree for O(1) or O(log n) access. If linked lists are required by design (for memory efficiency or the specific insertion semantics), consider adding a secondary index structure for lookups. Profile the actual access patterns—frequent random access is a sign you’re using the wrong data structure.

Trade-Off Table

Choosing between singly, doubly, and circular linked lists means weighing operational complexity against memory overhead and cache performance.

Operation	Singly Linked	Doubly Linked	Circular
Insert at head	O(1)	O(1)	O(1)*
Insert at tail	O(1)**	O(1)	O(n)***
Delete at head	O(1)	O(1)	O(1)*
Delete at tail	O(n)	O(1)	O(n)
Delete given node	O(n)	O(1)	O(n)
Reverse traversal	Not possible	O(n)	O(n)
Detect cycle	O(n)	O(n)	O(n)
Memory per node	1 pointer	2 pointers	1 pointer
Cache friendliness	Poor	Worse	Poor
Implementation complexity	Low	Medium	Medium

*Singly or doubly, if head is known With tail pointer maintained *Must traverse to find node before last

Use singly when: Memory is tight, you only walk forward, and you only manipulate head.

Use doubly when: You need reverse traversal, O(1) deletion from a node reference, or you’re building something like an LRU cache where both ends matter.

Use circular when: You need round-robin scheduling, circular buffers, or games where players eliminate each other in turn.

The cache friendliness row needs context. Linked list nodes scatter across the heap. Array elements sit contiguously, so prefetching works. When you traverse a linked list, each node access is a cache miss. This adds up—on a modern CPU with 100ns RAM latency, 1000 cache misses means 100 microseconds just waiting for memory, before any actual computation.

Observability Checklist

Monitoring linked list operations in production requires tracking both correctness and performance.

Correctness Monitoring

• Memory leak detection: Track heap size over time. Unexpected growth between requests or over long uptimes signals a leak. Tools like Valgrind, AddressSanitizer, or your language’s built-in leak detector help.
• Cycle detection alerts: If your Floyd’s algorithm ever triggers in production, something went wrong—either a bug in insertion logic or memory corruption. Log and alert on cycle detection hits.
• Null pointer dereference rate: Track segfaults and null access exceptions by operation count. A spike during list operations means something is wrong with the list structure.

Performance Monitoring

• Traversal latency percentiles: Instrument list operations to measure P50, P95, and P99 latency. If P99 spikes while P50 stays stable, you have occasional long traversals—possibly from accessing large lists.
• List size tracking: Monitor list sizes in production. A list that grows unbounded without compaction is a memory bomb.
• Operation throughput: Track operations per second. If throughput drops while list size grows, you may be hitting scaling limits of your list implementation.

Concurrency Monitoring

• Lock contention metrics: If using mutexes, track wait time and lock acquisition latency. High contention suggests too many threads fighting over the same list.
• ABA problem detection: Harder to detect, but if you see symptoms of stale data appearing after node reuse, ABA may be the cause.

Security Notes

Linked lists have specific security considerations that developers often miss until something breaks.

Dangling Pointer Exploitation

After freeing a node but before zeroing the pointer, you have a dangling pointer. If an attacker triggers code that reads through this pointer, they may read memory contents from previously freed objects. Sometimes they can place a new object at the same address and control what the dangling pointer reads or writes.

Mitigation: Always zero pointers after freeing the node they reference. In C/C++, use memory sanitizers in development to catch use-after-free. In garbage-collected languages, this attack is not possible because objects are not freed while references exist.

Iterator Invalidation

When you modify a linked list while iterating over it, iterators can become invalid. In C++ STL containers, modifying a list during iteration invokes undefined behavior—the iterator may skip elements, crash, or silently behave incorrectly. An attacker who can trigger specific modification patterns might cause information disclosure or denial of service.

Mitigation: Never modify a list during iteration without using safe patterns. Store modifications to apply after iteration, or use iterators that support safe modification (some list implementations provide this). In Java, iterating with a for-each loop while another thread modifies the list throws ConcurrentModificationException—this is the language protecting you.

Null Pointer Dereference Exploitation

In low-level code, a specially crafted input might cause a null pointer dereference in linked list traversal. If the list head is uninitialized or can be set to null by an attacker, dereferencing it crashes the program. In some environments, this can be used for denial of service attacks.

Mitigation: Validate all list state on entry to public functions. Check for null head before traversal. Use assertions liberally in debug builds to catch these conditions early. In production, fail gracefully rather than crash.

Memory Corruption from Buffer Overflows

While not specific to linked lists, buffer overflows in neighboring heap objects can corrupt next/prev pointers. An attacker overflowing a buffer adjacent to a linked list node might overwrite pointers to control subsequent memory accesses—essentially achieving arbitrary read/write.

Mitigation: Heap exploitation is a real concern. Use memory protection tools (ASLR, stack canaries), harden your allocator (use hardened tcmalloc or jemalloc), and avoid buffer overflows through bounds-checked languages, static analysis, or manual bounds checking.

Quick Recap Checklist

• Linked lists provide O(1) insertion/deletion at known positions
• No random access—O(n) traversal required
• Singly: one pointer, good for stack implementation
• Doubly: two pointers, O(1) deletion if you have node reference
• Circular: last node points to first, good for round-robin
• Floyd’s algorithm detects cycles with two pointers

Interview Questions

Further Reading

To deepen your understanding of linked lists and related data structures, explore these resources:

• Arrays: 1D and 2D — Compare linked lists with contiguous memory structures
• Floyd’s Cycle Detection — Mathematical proof and variations of the tortoise-and-hare algorithm for cycle detection
• Skip Lists — A probabilistic alternative to balanced trees built using multiple linked list layers for O(log n) search
• LRU Cache Implementation — Practical use of doubly linked lists combined with hash maps for O(1) cache get/put operations
• Lock-Free Linked Lists — Concurrent linked list implementations using CAS (Compare-And-Swap) for high-performance multi-threaded systems
• Bloom Filters — Space-efficient probabilistic data structures often paired with linked lists for collision resolution in hash tables

Conclusion

Linked lists give you O(1) insertion and deletion at known positions, but you lose O(1) random access. Singly linked lists are simplest; use doubly when you need reverse traversal or O(1) deletion given a node reference. Circular lists are the right tool for round-robin scheduling and similar patterns. Floyd’s cycle detection is elegant and worth memorizing. For more on data structures, see Arrays: 1D and 2D.