A linked list is a linear data structure in which each element, called a node, stores a value and a reference to the next node, instead of sitting in one block like an array. Inserting next to a node you already hold is O(1), but reaching the nth element takes O(n). The main types are singly, doubly and circular.
A linked list is one of the first data structures taught and one of the most common interview topics, mostly because it tests whether you can handle pointers without losing the rest of the list. This page gives the definition, the types, a complexity table, an honest comparison with arrays and the four patterns that solve most questions.
Every code block was run on Python 3.9 and Node 24 on 11 November 2026 and the output shown is the real output. Claims about Java, Python and the Linux kernel were checked against their official documentation on the same date.
Linked list definition
A linked list is a chain of nodes. Each node holds a value and a next reference that points to the following node. The first node is the head, and the last node's next is empty (None in Python, null in JavaScript). Unlike an array, the nodes do not need to sit next to each other in memory: the references hold the chain together.
Think of a treasure hunt. Each clue tells you where the next clue is, so you cannot jump straight to clue 7. You must follow clues 1 to 6 first. That is why reading the nth item is O(n), while adding a new clue between two existing ones only means changing two pointers.
Types of linked lists
| Type | Each node stores | What it allows | Typical use |
|---|---|---|---|
| Singly linked list | Value and next | Move forward only | Stacks, simple queues, interview questions |
| Doubly linked list | Value, prev and next | Move both ways; remove a node you hold in O(1) | Caches, undo history, browser tabs |
| Circular linked list | The last node points back to the first | Loop around forever | Round-robin scheduling, game turns |
| Circular doubly linked list | Both of the above | Loop in either direction | Playlists, rotating buffers |
These are used in production code. Java's LinkedList is a doubly-linked list implementation of the List and Deque interfaces. The Linux kernel documents its doubly linked lists. Python's collections.deque is a doubly-linked list of 64-slot blocks, according to the comments in CPython's source.
Operations and complexity
A small singly linked list in Python with the three operations you are asked for most: add at the front, add at the end and delete a value.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def push_front(self, value): # O(1): only the head changes
self.head = Node(value, self.head)
def append(self, value): # O(n): walk to the last node first
node = Node(value)
if self.head is None:
self.head = node
return
cur = self.head
while cur.next:
cur = cur.next
cur.next = node
def delete(self, value): # O(n) to find, O(1) to unlink
if self.head and self.head.value == value:
self.head = self.head.next
return True
cur = self.head
while cur and cur.next:
if cur.next.value == value:
cur.next = cur.next.next # skip over the removed node
return True
cur = cur.next
return False
def to_list(self):
out, cur = [], self.head
while cur:
out.append(cur.value)
cur = cur.next
return out
ll = LinkedList()
for v in (2, 3, 4):
ll.append(v)
ll.push_front(1)
print(ll.to_list())
print(ll.delete(3), ll.to_list(), ll.delete(99))Output:
[1, 2, 3, 4]
True [1, 2, 4] False| Operation | Singly linked list | Doubly linked list | Dynamic array |
|---|---|---|---|
| Read the item at index i | O(n) | O(n) | O(1) |
| Search for a value | O(n) | O(n) | O(n) |
| Insert or delete at the head | O(1) | O(1) | O(n), items shift |
| Insert at the tail | O(n), or O(1) with a tail pointer | O(1) with a tail pointer | O(1) amortised |
| Insert after a node you already hold | O(1) | O(1) | O(n) |
| Delete a node you already hold | O(n), you need the previous node | O(1) | O(n) |
The important phrase is "a node you already hold". Finding the node still costs O(n), so a linked list wins only when you keep references to nodes, as a least recently used (LRU) cache does with a hash map pointing into a doubly linked list.
Linked list vs array: an honest comparison
| Array (or Python list) | Linked list | |
|---|---|---|
| Memory layout | One contiguous block | Separate nodes, each with a pointer |
| Access by position | O(1) | O(n) |
| Insert or delete in the middle | O(n) | O(1) once you are at the node |
| Size | Fixed, or resized by copying | Grows one node at a time |
| Extra memory per item | None | One or two pointers |
| CPU cache behaviour | Good, items sit together | Poor, nodes are scattered |
Textbooks stop at the Big-O table, but in practice arrays usually win. The Linux kernel documentation says linked lists are rarely the best choice where a plain array would do and that, because of poor data locality, they are a bad choice where performance matters. The Java documentation for ArrayDeque says it is likely to be faster than LinkedList when used as a queue, and Python's own FAQ says CPython lists are variable-length arrays, not linked lists. Choose a linked list when you hold node references and splice often, or when the question asks for one. See the applications of array page for where arrays shine.
Interview patterns, with code
| Pattern | Idea | Problems that use it |
|---|---|---|
| In-place reversal | Flip each next pointer while walking forward | Reverse Linked List, Palindrome Linked List, Reverse Nodes in k-Group |
| Slow and fast pointers | One pointer moves 1 step, the other 2 | Middle of the Linked List, Linked List Cycle, Linked List Cycle II |
| Dummy head node | A fake first node removes the "head might change" special case | Merge Two Sorted Lists, Remove Nth Node From End of List |
| Two pointers with a gap | Start the second pointer n steps ahead | Remove Nth Node From End of List |
| Hash map plus doubly linked list | The map finds a node, the list reorders it in O(1) | LRU Cache |
Python: reverse a list, find the middle, detect a cycle and merge two sorted lists.
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
def make(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def to_list(head):
out = []
while head:
out.append(head.value)
head = head.next
return out
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next # flip one pointer per step
return prev
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # moves 1 step
fast = fast.next.next # moves 2 steps
return slow.value
def has_cycle(head): # Floyd's tortoise and hare
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
def merge_sorted(a, b):
dummy = tail = Node(0) # a dummy head removes the "empty list" special case
while a and b:
if a.value <= b.value:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
print(to_list(reverse(make([1, 2, 3, 4]))))
print(middle(make([1, 2, 3, 4, 5])), middle(make([1, 2, 3, 4])))
loop = make([1, 2, 3, 4])
loop.next.next.next.next = loop.next # the tail points back to the second node
print(has_cycle(make([1, 2, 3])), has_cycle(loop))
print(to_list(merge_sorted(make([1, 4, 6]), make([2, 3, 7]))))Output:
[4, 3, 2, 1]
3 3
False True
[1, 2, 3, 4, 6, 7]For a list with an even number of nodes, middle returns the second of the two middle nodes, which is why [1, 2, 3, 4] gives 3. Floyd's cycle detection works because the fast pointer gains one step on the slow pointer each round. If there is a loop they must meet inside it, and if there is none the fast pointer reaches the end. It uses O(1) extra memory, where storing visited nodes in a set would use O(n).
JavaScript: reverse a list and detect a cycle.
class ListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
const make = (values) => values.reduceRight((next, v) => new ListNode(v, next), null);
function toArray(head) {
const out = [];
for (let cur = head; cur; cur = cur.next) out.push(cur.value);
return out;
}
function reverse(head) {
let prev = null;
while (head) {
const next = head.next; // remember the rest of the list
head.next = prev; // flip this pointer
prev = head;
head = next;
}
return prev;
}
function hasCycle(head) { // Floyd's tortoise and hare
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
console.log(toArray(reverse(make([1, 2, 3, 4]))));
const loop = make([1, 2, 3, 4]);
loop.next.next.next.next = loop.next; // the tail points back to the second node
console.log(hasCycle(make([1, 2, 3])), hasCycle(loop));Output:
[ 4, 3, 2, 1 ]
false trueDoubly and circular lists in code
In a doubly linked list a node knows both neighbours, so once you hold it you can unlink it without searching. In a circular list the last node points back to the first, so a round robin never runs out of turns.
class DNode:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
# Doubly linked list: with the node in hand, removing it is O(1)
a, b, c = DNode("a"), DNode("b"), DNode("c")
a.next, b.prev, b.next, c.prev = b, a, c, b
def remove(node):
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
remove(b)
print(a.next.value, c.prev.value) # a and c now point at each other
# Circular list: the last node points back to the first, so a round robin never ends
x, y, z = DNode("P1"), DNode("P2"), DNode("P3")
x.next, y.next, z.next = y, z, x
turn, order = x, []
for _ in range(7):
order.append(turn.value)
turn = turn.next
print(order)Output:
c a
['P1', 'P2', 'P3', 'P1', 'P2', 'P3', 'P1']After removing b, node a points forward to c and c points back to a. This is the move behind an LRU cache. For queues built on the same idea, see applications of queue.
Common mistakes and practice problems
Common mistakes
- Losing the rest of the list. Save
node.nextbefore you changenode.next, or the remaining nodes are unreachable. - Not handling the empty list or a single node. A dummy head node removes most of these special cases.
- Off-by-one with slow and fast pointers. Check
fast and fast.nextbefore moving two steps. - Printing a list that has a cycle. The loop never ends. Detect the cycle first.
- Forgetting to update
previn a doubly linked list. One missed pointer leaves a one-way list that looks fine until you walk it backwards. - Using a linked list for a stack or queue in Python. A list or
collections.dequeis simpler and faster.
Practice problems, in order
- Reverse Linked List
- Middle of the Linked List
- Linked List Cycle
- Merge Two Sorted Lists
- Remove Nth Node From End of List
- Palindrome Linked List
- Add Two Numbers
- Reorder List
- LRU Cache
- Merge k Sorted Lists
Masai's longer guides: Linked List in Data Structure: Types, Operations, Code and Array vs Linked List: Differences, Big-O and When to Use. Related pages: applications of stack, hash maps (the other half of an LRU cache) and the tree data structure, which is a linked structure with two pointers per node.
Frequently asked questions
What is a linked list in data structure?
A linear data structure in which each element, called a node, holds a value and a reference to the next node. The nodes need not be next to each other in memory, so inserting or removing near a known node is cheap but reading the nth item takes O(n).
What is the difference between a singly and a doubly linked list?
A singly linked list node points only to the next node, so you can only move forward. A doubly linked list node also points to the previous node, so you can move both ways and remove a node you hold in O(1), at the cost of extra memory.
Why use a linked list instead of an array?
When you often insert or delete next to nodes you already hold, or want to add items one at a time without resizing. In most everyday code arrays or dynamic arrays are faster because their items sit together in memory, so use a linked list for a clear reason.
Is a Python list a linked list?
No. CPython lists are variable-length arrays of references, as the Python FAQ states. That is why indexing is O(1) and inserting at the front is O(n). Use collections.deque for fast operations at both ends.
How do you detect a cycle in a linked list?
Use Floyd's tortoise and hare: move one pointer one step and another two steps at a time. If they ever meet, there is a cycle. If the fast pointer reaches the end, there is none. It takes O(n) time and O(1) memory.
What is the time complexity of searching a linked list?
O(n), because you must follow the nodes one by one from the head. Sorting a list does not help, since there is no way to jump to the middle.
Sources checked
- Java LinkedList is a doubly-linked list implementation of List and Deque
- ArrayDeque likely faster than LinkedList when used as a queue
- Linux kernel doubly linked lists; poor data locality caveat
- deque stored as a doubly-linked list of fixed-length blocks (BLOCKLEN 64)
- CPython lists are variable-length arrays, not linked lists
- deque O(1) appends and pops at both ends
- Existing Masai post (HTTP 200 on 11 Nov 2026)
Learn this with mentors
Programmes for builders and engineers with admissions open: live classes, mentors and project work.


