ReviseAlgo Logo

Linked Lists

Linked List Fundamentals

Master Linked List structures: Singly, Doubly, and Circular Linked Lists, node definitions, and comparison with contiguous array memory.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is a Linked List?

A Linked List is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a Node) is a separate object containing a value and a pointer (or reference) that points to the next node in the sequence.

Why is it Important?

Unlike arrays, linked lists can grow or shrink dynamically in size without needing expensive re-allocations or element shifts. If you know the reference to the node, inserting or deleting an item takes O(1) time.

Where is it Used?

  • Web Browser History: Tracking visited pages sequentially to support forward and backward navigation.
  • CPU Task Schedulers: Round-robin schedulers utilize circular lists to cycle through running processes endlessly.

    • 2. Mental Model: A Scavenger Hunt

    Think of a Linked List as a Scavenger Hunt:

  • You start at the starting line (the head pointer).
  • At the starting line, you are given a clue containing a value (e.g., "Box 1") and a map coordinate pointing to the next clue.
  • You must physically walk to that coordinate to read the next clue.
  • You cannot skip clues or jump directly to Clue #5 without reading Clues 1 through 4 first.
  • The hunt ends when a clue tells you: "There are no more locations left" (the pointer is null).

    • 3. Core Structural Variations

    1. Singly Linked List

    Each node contains a data value and a single reference pointer next pointing to the subsequent node.

    2. Doubly Linked List

    Each node contains a data value, a next pointer, and a prev pointer pointing to the preceding node. This allows traversal in both directions but increases memory consumption.

    3. Circular Linked List

    A list where the final node's next pointer references the head node rather than pointing to null, creating a closed loop.

    Singly Linked List Node Representations

    4. Visualizing Variations

    Below is a visual representation of Singly, Doubly, and Circular Linked Lists:

    5. Real-World Examples

  • Operating System Memory Pages: Free block managers track available memory fragments using linked structures.
  • Music Playlists: Standard music queue players construct tracks queue as a doubly circular list to loop playback smoothly.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test list comparisons:
  • "What are the advantages and disadvantages of a Linked List over an Array?"
  • HashMap lookup: Arrays provide O(1) random access. Linked lists take O(N) lookup.
  • Insertion: Arrays require shifting elements (O(N) writes) to insert at the front. Linked lists take O(1) pointer adjustments.

    • Common Mistakes

    Warning: 1. Memory Management Leaks in C++: In languages like C++, list node allocations are dynamic. Forgetting to recursively free deleted node structures using delete will cause severe memory leaks.
    > 2. Pointer Dereference Crashes: Attempting to read curr.next.val when curr or curr.next is null triggers immediate runtime crashes (e.g. NullPointerException). Always check bounds.

    7. Summary

  • Singly Linked: Value + single next reference pointer.
  • Doubly Linked: Value + next and prev reference pointers.
  • Circular Linked: Final node's next points back to head.
  • Complexities: Access is O(N), search is O(N); insertions/deletions at known positions are O(1) time.

    • 8. Quiz

    Question 1: What is the main advantage of a Linked List over an Array? Answer: Linked lists have dynamic sizes and can perform insertions/deletions at the head or known positions in O(1) time without needing to shift elements or re-allocate contiguous blocks.
    Question 2: What is the time complexity to retrieve the N-th element in a Doubly Linked List? Answer: O(N) time. Even though we can traverse backwards or forwards, we must still step node-by-node from the head or tail to reach the target index.
    Question 3: How does a Doubly Linked List simplify deletions over a Singly Linked List? Answer: In a Singly Linked List, deleting a node requires finding its preceding node to re-link pointers, taking O(N) scan. In a Doubly Linked List, because each node has a reference to prev, we can delete it in-place in O(1) time directly.
    Question 4: True or False: Linked lists are more CPU cache-friendly than arrays. Answer: False. Arrays are stored in contiguous memory blocks, letting CPU pre-fetchers load sequential indices into cache lines. Linked list nodes are scattered randomly across the heap, leading to frequent cache misses.
    Question 5: What value does the next pointer of the final node in a Singly Linked List contain? Answer: null (or nullptr/None), indicating the end of the list.