Linked Lists

Learning Objectives

By the end of this page, you will be able to:

Define a linked list and explain how nodes and pointers create a chain-like structure in memory.
Implement a singly linked list in Python, including insertion, deletion, and traversal.
Distinguish singly, doubly, and circular linked lists and pick the right variant for a given problem.
State the time complexity of insertion, deletion, search, and access for each linked list type.
Compare linked lists against arrays and explain when each wins.
Identify and avoid the most common linked list bugs (lost head, broken links, null-pointer traversal).

Quick Answer

A linked list is a linear data structure where each element (a "node") holds a value and a pointer to the next node, instead of sitting in contiguous memory like an array. This makes insertion and deletion at the front or middle O(1) once you have a reference to the spot, because you just rewire pointers — no shifting elements. The trade-off is that you lose random access: to reach the 5th node you must walk from the head, one link at a time, so lookups cost O(n). Linked lists come in three main flavors — singly linked (one-way), doubly linked (two-way), and circular (tail points back to head). They matter because they're the mental model behind many higher-level structures: stacks, queues, hash-map buckets, and even the LRU cache used in operating systems and browsers.

Basic Concepts

A linked list is built from two ideas:

Node — the basic unit, storing:
- a value (the data)
- a reference ("pointer" or "link") to the next node
Head — a reference to the first node. If head is None, the list is empty. There's no fixed size and no index-based memory layout — each node can live anywhere in memory; only the pointers tie them together.

This is the key mental shift from arrays: an array is one contiguous block you can jump into with arithmetic (base + i * size). A linked list is a scattered set of nodes connected only by pointers, so you must follow the chain to get anywhere.

Real-world example: think of a scavenger hunt where each clue tells you where to find the next clue. You can't skip to clue 5 without first reading clues 1 through 4 — that's exactly the sequential-access cost of a linked list.

Why it matters: this pointer-based design is what gives linked lists O(1) insertion/deletion at known positions, and it's the same underlying idea used in the "chaining" collision-resolution strategy in hash tables and in doubly linked node chains used inside LRU caches.

Common misunderstanding: students often think a linked list is "just a resizeable array." It isn't — arrays give O(1) random access and poor mid-list insertion; linked lists give the opposite trade-off. Confusing the two is the single most common linked-list exam mistake.

Types of Linked Lists

Singly Linked List

Each node points only to the next node. Traversal is one-directional (head → tail).

class Node:
    def __init__(self, data):
        self.data = data   # Value stored in the node
        self.next = None   # Reference to the next node

class LinkedList:
    def __init__(self):
        self.head = None   # Empty list initially

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:       # Walk to the last node
            last_node = last_node.next
        last_node.next = new_node   # Link new node at the end

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()  # 1 -> 2 -> 3 -> None

Key points:

Dynamic size — grows/shrinks without reallocation, unlike a fixed array.
Efficient front insertion/deletion — O(1) once you have the node reference.
Sequential access only — you cannot jump to the middle without walking from head.

Real-world example: a music playlist in "shuffle-off" mode is essentially a singly linked list — each song only needs to know the "next" track.

Why it matters: singly linked lists are the simplest possible pointer structure, and they underpin stack implementations (push/pop at the head is O(1)).

Common misunderstanding: students often forget to check if not self.head before traversing, causing a crash on an empty list. Always guard against head is None first.

Doubly Linked List

Each node stores references to both the next and previous nodes, enabling traversal in either direction.

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None   # Reference to the previous node
        self.next = None   # Reference to the next node

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None    # Keeping a tail pointer makes append O(1)

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = self.tail = new_node
            return
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node

    def print_forward(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Example usage
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.print_forward()  # 1 <-> 2 <-> 3 <-> None

Key points:

Bidirectional traversal — you can walk backward from tail too.
Extra memory per node — one more pointer (prev) than a singly linked list.
Faster deletion when you already hold the node — no need to walk from the head to find the predecessor, since node.prev is already known.

Real-world example: a web browser's back/forward history and text editor "undo/redo" chains are classic doubly linked lists — you move forward and backward through states.

Why it matters: Python's own collections.deque and Java's LinkedList are implemented as doubly linked lists specifically so that both-end operations stay O(1).

Common misunderstanding: students assume doubly linked means "twice as fast." It doesn't speed up search — it only makes backward traversal and predecessor-aware deletion possible. Search is still O(n).

Circular Linked List

The last node points back to the first node instead of to None, forming a loop. Can be built as circular-singly or circular-doubly.

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head   # Points to itself
            return
        last_node = self.head
        while last_node.next != self.head:
            last_node = last_node.next
        last_node.next = new_node
        new_node.next = self.head       # Close the loop

    def print_list(self):
        if not self.head:
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("(head)")

# Example usage
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.print_list()  # 1 -> 2 -> 3 -> (head)

Key points:

No None terminator — you must stop by checking "have I returned to head?", not by checking for null.
Continuous traversal — useful when you need to cycle through elements repeatedly.

Real-world example: round-robin CPU scheduling and multiplayer "whose turn is it next" logic both cycle through a circular linked list of processes/players, wrapping back to the start automatically.

Why it matters: it eliminates a special "wrap-around" case you'd otherwise have to code by hand with an array and modulo arithmetic.

Common misunderstanding: students write while current.next: (checking for None) out of habit — that condition is never true in a circular list, causing an infinite loop. You must compare against head instead.

Common Operations on Linked Lists

Insertion at the Beginning (Singly Linked List)

def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

Deletion from the End

def delete_from_end(self):
    if not self.head:
        return
    if not self.head.next:          # Only one element
        self.head = None
        return
    second_last = self.head
    while second_last.next.next:
        second_last = second_last.next
    second_last.next = None

Reversing a Singly Linked List

A classic interview question — reverse the next pointers so the list points the other way, using only O(1) extra space:

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next   # Save the next node before overwriting
        current.next = prev        # Reverse the pointer
        prev = current              # Move prev forward
        current = next_node         # Move current forward
    self.head = prev                # New head is the old tail

Big-O Cost Summary

Operation	Array	Singly Linked List	Doubly Linked List
Access by index	O(1)	O(n)	O(n)
Search by value	O(n)	O(n)	O(n)
Insert at front	O(n)	O(1)	O(1)
Insert at end (no tail pointer)	O(1) amortized	O(n)	O(n)
Insert at end (with tail pointer)	O(1) amortized	O(1)	O(1)
Delete at front	O(n)	O(1)	O(1)
Delete at end	O(1)	O(n)	O(1) (with tail pointer)
Delete a known node	O(n)	O(n) (must find predecessor)	O(1)

Visual: Node Structure and Reversal

The diagram above shows a singly linked list 1 -> 2 -> 3 -> None. During reversal, each node's next pointer is flipped one at a time (prev, current, next_node walking forward together) until the list reads 3 -> 2 -> 1 -> None with head now pointing at the old tail.

Advantages of Linked Lists

Dynamic size — grows/shrinks without reallocation, unlike a fixed-capacity array.
Efficient insertions/deletions — O(1) at the front (and at the end/known node with the right pointers), with no shifting of other elements.

Disadvantages of Linked Lists

No random access — reaching element i costs O(n) because you must walk from the head.
Memory overhead — every node carries one or two extra pointer fields beyond the data itself.
Poor cache locality — nodes are scattered in memory, so traversal is slower in practice than an array scan of the same size, even though both are technically O(n).

Key Terms

Term	Definition	Context/Related
Node	A single element holding data plus a pointer to the next (and possibly previous) node	Building block of every linked list
Head	Reference to the first node in the list	Starting point of all traversal
Tail	Reference to the last node (or, in a circular list, the node whose `next` points to head)	Kept explicitly for O(1) append
Pointer / Reference	A link stored in a node that identifies the next (or previous) node	`next`, `prev` fields
Singly Linked List	List where each node references only the next node	One-directional traversal
Doubly Linked List	List where each node references both next and previous nodes	Bidirectional traversal
Circular Linked List	List where the last node points back to the head instead of `None`	No null terminator
Traversal	Walking the list node by node from head (or tail) to read/process data	O(n) cost
Sentinel / Dummy Node	A placeholder node used to simplify edge cases like empty-list insertion	Common in production implementations

Common Mistakes

Misconception: "A linked list is just a dynamic array with a different name." Why it's wrong: Arrays give O(1) index access via memory arithmetic; linked lists have no such arithmetic and require O(n) traversal to reach a given position. Their performance profiles are opposites, not synonyms. Correct understanding: Use an array/dynamic array when you need fast random access; use a linked list when you need cheap insertion/deletion at known positions and don't need indexing.
Misconception: "Deleting a node is instant no matter where it is." Why it's wrong: In a singly linked list, deleting a node requires access to its predecessor to rewire next, and finding that predecessor takes O(n) unless you already hold a reference to it. Correct understanding: Deletion is O(1) only if you already have a pointer to the previous node (as in a doubly linked list) — otherwise it's O(n) because of the search needed first.
Misconception: "Losing track of head is a minor bug." Why it's wrong: If you overwrite self.head before saving a reference to the rest of the list (e.g., during insertion at the front or reversal), you permanently lose access to every node after it — this is a common source of "disappearing data" bugs. Correct understanding: Always save new_node.next = self.head (or the equivalent "next" reference) before reassigning self.head, exactly as shown in insert_at_beginning and reverse above.

Comparison and Connections

Aspect	Array	Linked List
Memory layout	Contiguous block	Scattered nodes linked by pointers
Random access	O(1)	O(n)
Insert/delete at front	O(n) (must shift)	O(1)
Extra memory per element	None	One or two pointers per node
Cache performance	Good (sequential memory)	Poor (nodes scattered)
Resizing	Costly (reallocate + copy)	Not needed — grows node by node

Aspect	Singly Linked List	Doubly Linked List	Circular Linked List
Pointers per node	1 (`next`)	2 (`next`, `prev`)	1 or 2
Traversal direction	Forward only	Both directions	Forward (loops back to head)
Terminator	`None` at tail	`None` at both ends	No `None` — loops to head
Typical use	Stacks, simple queues	Browser history, `deque`, LRU cache	Round-robin scheduling, circular buffers

Practice Questions

Recall

What two pieces of information does a single node in a singly linked list store? Answer: The data value itself, and a reference/pointer to the next node in the list.
What distinguishes a circular linked list from a singly linked list? Answer: In a circular linked list the last node's next points back to the head instead of to None, so there's no null terminator.

Understanding

Why is inserting at the front of a linked list O(1), but inserting at the front of an array is O(n)? Answer: A linked list insertion just creates a new node and rewires two pointers. An array insertion at the front must shift every existing element one position to the right to make room.
Why does a doubly linked list use more memory per node than a singly linked list, and what does that extra memory buy you? Answer: Each node stores an extra prev pointer. That buys backward traversal and O(1) deletion when you already hold a reference to the node, since you don't need to search for the predecessor.

Application

You're designing an undo/redo feature for a text editor. Which linked list variant fits best, and why? Answer: A doubly linked list — undo moves backward (prev) and redo moves forward (next) through the history of states, both in O(1) per step.
You need to implement a round-robin turn system for a multiplayer game with a variable number of players. What structure fits, and why? Answer: A circular linked list — after the last player's turn, next wraps back to the first player automatically, with no special-case wrap-around logic needed.

Analysis

Compare the cost of deleting the last node in a singly linked list versus a doubly linked list (assume no tail pointer in either case initially). Which is cheaper and why? Answer: In a singly linked list you must traverse from head to find the second-to-last node — O(n). In a doubly linked list, if you have a tail pointer, you can jump directly to it and use tail.prev to find the new tail in O(1); without a tail pointer both are O(n), but the doubly linked version still saves the predecessor lookup once you reach the last node.
A student claims "linked lists are always better than arrays because they never need resizing." Evaluate this claim. Answer: False as a blanket statement. Linked lists avoid the cost of reallocation but lose O(1) random access and have worse cache locality and per-node memory overhead. For read-heavy workloads with known size, arrays (or dynamic arrays) usually outperform linked lists in practice.

FAQ

Q: Why would I ever use a linked list instead of just using a dynamic array (like Python's list)? A: When you need frequent insertions/deletions at the front or in the middle without shifting elements, and you don't need random index access — for example, implementing a queue, stack, or LRU cache's usage order.

Q: Is a doubly linked list always better than a singly linked list? A: No — it costs extra memory per node for the prev pointer. Use it only when you genuinely need backward traversal or O(1) deletion given a node reference; otherwise a singly linked list is simpler and leaner.

Q: How do I detect a cycle in a linked list that's supposed to be non-circular? A: Use Floyd's cycle detection algorithm ("tortoise and hare") — advance one pointer one step at a time and another two steps at a time; if they ever meet, there's a cycle.

Q: Why is searching a linked list still O(n) even though insertion can be O(1)? A: Insertion at a known position skips the search step entirely. But finding where to insert, or finding a value, still requires walking node by node from the head — there's no indexing shortcut.

Q: What happens if I forget to set the new tail node's next to None after deleting the last element? A: You'll leave a dangling reference to a now-orphaned node, which can cause incorrect traversal results or, in a circular list, break the "stop when we reach head" termination condition.

Q: Are linked lists used in real production systems, or just in interviews? A: Both. They appear in OS-level process scheduling queues, in LinkedHashMap/LRU cache implementations, in the "chaining" strategy for hash-table collision resolution, and in the internal implementation of collections.deque in Python.

Quick Revision

A node = data + pointer(s) to neighboring node(s); a list is just nodes chained together.
Head marks the start; if head is None, the list is empty.
Singly linked: one next pointer, forward traversal only.
Doubly linked: next and prev pointers, traversal both ways, more memory per node.
Circular linked: last node's next loops back to head — no None terminator, watch for infinite loops.
Insert/delete at the front is O(1) for linked lists, O(n) for arrays.
Random access (get element at index i) is O(n) for linked lists, O(1) for arrays.
Search by value is O(n) regardless of list type.
Keeping a tail pointer makes append O(1) instead of O(n).
Reversal: walk with prev, current, next_node, flipping next each step — O(n) time, O(1) space.
Linked lists trade random access for cheap, localized insertion/deletion.
Real uses: stacks/queues, browser history, LRU caches, round-robin schedulers, hash-table chaining.

Prerequisites

Arrays and basic memory layout concepts
Pointers/references as a general programming concept
Big-O notation basics

Related Topics

Stacks and Queues (often implemented using linked lists)
Hash Tables (chaining uses linked lists to resolve collisions)
Trees (a tree is conceptually a linked structure with multiple "next" pointers per node)

Next Topics

Stacks and Queues
Trees and Binary Search Trees
Hash Tables

Learning Objectives​

Quick Answer​

Basic Concepts​

Types of Linked Lists​

Singly Linked List​

Doubly Linked List​

Circular Linked List​

Common Operations on Linked Lists​

Insertion at the Beginning (Singly Linked List)​

Deletion from the End​

Reversing a Singly Linked List​

Big-O Cost Summary​

Visual: Node Structure and Reversal​

Advantages of Linked Lists​

Disadvantages of Linked Lists​

Key Terms​

Common Mistakes​

Comparison and Connections​

Practice Questions​

FAQ​

Quick Revision​

Related Topics​

Learning Objectives

Quick Answer

Basic Concepts

Types of Linked Lists

Singly Linked List

Doubly Linked List

Circular Linked List

Common Operations on Linked Lists

Insertion at the Beginning (Singly Linked List)

Deletion from the End

Reversing a Singly Linked List

Big-O Cost Summary

Visual: Node Structure and Reversal

Advantages of Linked Lists

Disadvantages of Linked Lists

Key Terms

Common Mistakes

Comparison and Connections

Practice Questions

FAQ

Quick Revision

Related Topics