Linked Lists — Nodes, Pointers, and When to Use Them

linked-listsdata-structuresbeginnerfree

Understand how linked lists work — from nodes and pointers to insertions and deletions. See it all happen step by step with interactive animations.

Published: 15/03/2026

Animation linked-list-operations not found in registry.

What Is a Linked List?

A linked list is a chain of nodes, where each node holds a value and a pointer to the next node. Unlike arrays, linked list elements are not stored in contiguous memory — each node can live anywhere in memory, connected only by pointers.

Think of a treasure hunt. Each clue tells you where to find the next one. You can not jump to clue #5 without following clues 1 through 4 first. That is a linked list.

The first node is called the head. The last node points to None (or null), marking the end of the list.

How Linked Lists Work

The Node

Every node has two parts: data (the value it stores) and next (a pointer to the next node). In Python, this is a simple class with two attributes.

Insertion

Inserting at the head is O(1) — create a new node, point it to the current head, update the head pointer. Inserting at the tail requires walking to the end first, making it O(n) unless you maintain a tail pointer.

Deletion

To delete a node, find the node before it and update its next pointer to skip the target. The tricky part is finding the previous node — you need to traverse from the head.

Search

Walk from head to tail, checking each node. O(n) in the worst case — no random access like arrays.

python

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

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

    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def delete(self, value):
        if not self.head:
            return
        if self.head.value == value:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                return
            current = current.next

    def display(self):
        result = []
        current = self.head
        while current:
            result.append(str(current.value))
            current = current.next
        return " -> ".join(result) + " -> None"

ll = LinkedList()
for v in [4, 2, 7, 1, 9]:
    ll.append(v)
print("List:", ll.display())
ll.prepend(0)
print("After prepend 0:", ll.display())
ll.delete(7)
print("After delete 7:", ll.display())

Arrays vs Linked Lists — performance comparison

Operation	Array	Linked List
Access by index	O(1)	O(n)
Search	O(n)	O(n)
Insert at beginning	O(n)	O(1)
Insert at end	O(1) amortised	O(n) or O(1) with tail
Delete by value	O(n)	O(n)
Memory	Contiguous, cache-friendly	Scattered, pointer overhead

Variations

Doubly Linked Lists

Each node has both next and prev pointers. This allows O(1) deletion when you have a reference to the node and enables backward traversal.

Circular Linked Lists

The last node points back to the head instead of None. Useful for round-robin scheduling and buffer implementations.

When to Use Linked Lists

Linked lists shine when you need frequent insertions/deletions at arbitrary positions and do not need random access. They underpin stacks, queues, hash table chaining, and LRU caches.

Key Takeaways

Linked lists store elements as nodes connected by pointers, not in contiguous memory.
Insert at head is O(1) — the main advantage over arrays.
No random access — you must traverse from the head to reach any element.
Doubly linked lists add a prev pointer for bidirectional traversal.
Real-world uses: stacks, queues, hash table chaining, LRU caches, undo history.

Subjects