A linked list is a data structure in which each element (node) stores a value and a pointer to the next node, forming a chain that allows O(1) insertion and deletion at the head but requires O(n) traversal to access an element by position.
A linked list is a chain of nodes where each node holds a value and a pointer to the next — you can add or remove nodes at the front in one step, but finding the 100th element requires walking 100 steps.
Structure of a node
Each node contains two things: the data it holds, and a pointer (memory address) to the next node. The last node's pointer is null. A linked list is a chain of these nodes, held together by pointers rather than contiguous memory. You only need to know the address of the first node (the head) to traverse the whole list.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next; /* pointer to next node */
} Node;
/* Insert at head: O(1) */
Node* insert_head(Node* head, int val) {
Node* node = malloc(sizeof(Node));
node->value = val;
node->next = head; /* point to old head */
return node; /* new head */
}
void print_list(Node* head) {
while (head != NULL) {
printf("%d -> ", head->value);
head = head->next;
}
printf("NULL\n");
}
int main() {
Node* head = NULL;
head = insert_head(head, 30);
head = insert_head(head, 20);
head = insert_head(head, 10);
print_list(head); /* 10 -> 20 -> 30 -> NULL */
return 0;
}Complexity table
| Operation | Average | Worst | Notes |
|---|---|---|---|
| Access by index | O(n) | O(n) | Must traverse from head |
| Search | O(n) | O(n) | Linear scan required |
| Insert at head | O(1) | O(1) | Pointer update only |
| Insert at tail (with tail ptr) | O(1) | O(1) | If tail pointer maintained |
| Insert at index i | O(n) | O(n) | Must traverse to position i |
| Delete at head | O(1) | O(1) | Pointer update only |
| Delete at known node | O(1) | O(1) | For doubly-linked list; O(n) singly |
| Space | O(n) | O(n) | Plus pointer overhead per node |
Pointer overhead: 8 bytes per pointer on 64-bit systems.
Singly vs. doubly linked
A singly linked list has a next pointer only — traversal is one direction. A doubly linked list has both next and prev pointers — traversal in both directions, and O(1) deletion of any node (without finding it first, given a pointer to it). Python's collections.deque is implemented as a doubly-linked list of fixed-size blocks.
Why linked lists exist: the insertion advantage
Inserting at the head of a linked list is O(1): allocate one node, set its next pointer to the current head, update the head pointer. The same operation on an array is O(n): every element must shift right. When insertion frequency is high and random access is rare, linked lists outperform arrays. Real uses: LRU cache (doubly linked list + hash map), job scheduling queues, undo/redo history.
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def prepend(self, val): # O(1)
self.head = Node(val, self.head)
def to_list(self): # O(n)
result, curr = [], self.head
while curr:
result.append(curr.val)
curr = curr.next
return result
ll = LinkedList()
for v in [30, 20, 10]:
ll.prepend(v)
print(ll.to_list()) # [10, 20, 30]Reversing a singly linked list
A classic interview problem demonstrating pointer manipulation. The key insight: traverse the list once, reversing each link as you go. Three pointers: previous, current, next.
def reverse(head):
prev, curr = None, head
while curr:
nxt = curr.next # save next
curr.next = prev # reverse link
prev = curr # advance prev
curr = nxt # advance curr
return prev # new headCircular linked lists
The last node's next pointer points back to the head rather than null. Useful for round-robin scheduling (CPU round-robin, token ring networks) where processing wraps continuously. Detecting a cycle in a linked list: Floyd's tortoise-and-hare algorithm — two pointers advancing at different speeds. If there is a cycle, the fast pointer will eventually lap the slow pointer: O(n) time, O(1) space.
collections.deque.Memory allocation and fragmentation
Each linked list node is allocated separately by malloc (C) or the garbage collector (Python, Java). Over time, nodes may be scattered throughout the heap — a process called heap fragmentation. A defragmented heap has large contiguous free blocks; a fragmented heap has many small non-contiguous ones. Java's generational garbage collector compacts the heap periodically, improving locality. Custom allocators (arena allocators, slab allocators) allocate many small objects from a pre-allocated block to improve locality.
Floyd's cycle detection algorithm
Given a linked list that may have a cycle, detect it in O(n) time and O(1) space. Two pointers: slow advances one node per step; fast advances two. Claim: if a cycle exists, fast eventually equals slow. Proof: let λ = cycle length, μ = tail before cycle. After slow enters the cycle, fast is μ mod λ steps ahead. Each step reduces the gap by 1 (mod λ). After at most λ steps, gap = 0. Total steps: O(μ + λ) = O(n).
CLRS (4th ed.), Ch. 10.2 — Linked lists. Knuth, D. E. (1997). TAOCP Vol. 1, §2.2.3 — Linked allocation. Floyd, R. W. (1967). "Non-deterministic algorithms." JACM 14(4) — cycle detection.