Singly and Doubly Linked Lists in Lua
What Are Linked Lists?
A linked list is a linear data structure where elements — called nodes — are stored as individual table objects. Each node holds a value and a reference to the next node in the sequence. You access the whole structure through the head, which is simply a variable pointing to the first node. When a node’s next field is nil, you’ve reached the end.
This is fundamentally different from how Lua tables work. A Lua table is a hash-map-backed array — it gives you O(1) random access by key and manages its own memory layout. A linked list trades that convenience for something else: the ability to insert and delete nodes with only pointer manipulation, without shifting any other elements.
Why Bother When Lua Tables Already Work?
Here’s the honest starting point: Lua’s official guide (Programming in Lua, §11.3) says it plainly — you seldom need linked lists in Lua because there’s usually a simpler way to represent your data. Tables are dynamic, flexible, and already handle most of what you’d reach a linked list for.
So why learn them at all? A few specific scenarios tip the scales in favour of linked lists:
- Frequent insertions or deletions in the middle of a sequence — pointer redirection is O(1), versus O(n) element shifting with tables
- Stable iterators during modification — iterating over a table while deleting from it is unsafe in Lua; a linked list’s structural isolation prevents iterator-invalidation bugs
- Custom memory management — you control exactly when nodes are allocated and freed
- Algorithms that need splice operations — cutting and pasting a sublist is just a few pointer reassignments
- Teaching the fundamentals — linked lists are the canonical example of pointer-based data structures, and building them deepens your understanding of how structures like stacks and queues work
In practice, you’ll reach for a linked list rarely. But when you need one, nothing else will do.
Singly Linked Lists
In a singly linked list, each node has exactly two fields: value (the data you care about) and next (a reference to the following node, or nil if it’s the tail).
Node Structure
-- A node is just a table with a value and a next pointer
local node = { value = 42, next = nil }
-- An empty list is just nil
local list = nil
```lua
Because Lua tables are reference types, assigning a table to multiple variables doesn't copy the data — all variables point to the same table object. This is what makes linked lists work: the `next` field stores a reference to the next node table, not a copy of it.
### Building a List
You can build a list by inserting at the front, which is O(1):
```lua
-- Insert at front: new node points to current head, becomes new head
local function insert_front(list, value)
return { value = value, next = list }
end
local list = nil
list = insert_front(list, 30)
list = insert_front(list, 20)
list = insert_front(list, 10)
-- List is now: 10 -> 20 -> 30
```lua
To build a list in order from an array, insert at the back:
```lua
local function insert_back(list, value)
local new_node = { value = value, next = nil }
if list == nil then return new_node end
local current = list
while current.next do
current = current.next
end
current.next = new_node
return list
end
local list = nil
for _, v in ipairs({ 10, 20, 30 }) do
list = insert_back(list, v)
end
-- List is now: 10 -> 20 -> 30
```lua
### Traversing and Searching
Traverse by following `next` pointers until you hit `nil`. The idiomatic Lua loop uses the truthiness of `nil` to terminate:
```lua
local function traverse(list)
local current = list
while current do
print(current.value)
current = current.next
end
end
traverse(list)
-- > 10
-- > 20
-- > 30
```lua
Search is a linear scan — O(n) time:
```lua
local function search(list, target)
local current = list
while current do
if current.value == target then
return current
end
current = current.next
end
return nil
end
```lua
### Deleting a Node
Deletion requires finding the node and patching the predecessor's `next` pointer:
```lua
local function delete(list, value)
local current = list
local prev = nil
while current do
if current.value == value then
if prev then
prev.next = current.next
else
list = current.next -- deleting the head
end
return list
end
prev = current
current = current.next
end
return list
end
```lua
### A Complete Example: Stack Using a Singly Linked List
Here's a working stack implementation that uses a singly linked list internally:
```lua
local function create_stack()
return { top = nil, size = 0 }
end
local function push(stack, value)
stack.top = { value = value, next = stack.top }
stack.size = stack.size + 1
end
local function pop(stack)
if not stack.top then return nil end
local value = stack.top.value
stack.top = stack.top.next
stack.size = stack.size - 1
return value
end
local s = create_stack()
push(s, "first")
push(s, "second")
push(s, "third")
print(pop(s)) -- > third
print(pop(s)) -- > second
print(pop(s)) -- > first
```lua
## Doubly Linked Lists
A doubly linked list adds a `prev` field to each node, pointing to the preceding node. This costs a little more memory per node but gives you bidirectional traversal and — critically — O(1) deletion when you already have a reference to the node.
### Node Structure
```lua
local node = {
value = 42,
prev = nil,
next = nil
}
```lua
### Sentinel Nodes
A common pattern is to use **sentinel nodes** (dummy head and tail) to eliminate boundary checks:
```lua
local function create_list()
local head = { value = nil, next = nil, prev = nil }
local tail = { value = nil, next = nil, prev = head }
head.next = tail
return head, tail
end
local function insert_after(node, value)
local new_node = { value = value, next = node.next, prev = node }
node.next.prev = new_node
node.next = new_node
return new_node
end
local function remove_node(node)
node.prev.next = node.next
node.next.prev = node.prev
return node.value
end
```lua
### O(1) Deletion with a Node Reference
The key advantage of doubly linked lists is deleting a node when you already have a reference to it — no traversal required:
```lua
local function delete_node(node)
if not node or not node.prev or not node.next then return end
node.prev.next = node.next
node.next.prev = node.prev
end
```lua
Compare this to singly linked lists, where you'd need to search for the predecessor first.
### A Complete Example: Queue Using a Doubly Linked List
```lua
local function create_queue()
local head = { value = nil, next = nil, prev = nil }
local tail = { value = nil, next = nil, prev = head }
head.next = tail
return { head = head, tail = tail, size = 0 }
end
local function enqueue(q, value)
local new_node = { value = value, next = q.tail, prev = q.tail.prev }
q.tail.prev.next = new_node
q.tail.prev = new_node
q.size = q.size + 1
end
local function dequeue(q)
if q.head.next == q.tail then return nil end
local node = q.head.next
q.head.next = node.next
node.next.prev = q.head
q.size = q.size - 1
return node.value
end
local q = create_queue()
enqueue(q, "alpha")
enqueue(q, "beta")
enqueue(q, "gamma")
print(dequeue(q)) -- > alpha
print(dequeue(q)) -- > beta
```lua
## Circular Linked Lists
A circular linked list's last node points back to the head, eliminating the `nil` terminator. This is useful for round-robin scheduling, circular buffers, and any problem where you need to loop continuously through a sequence.
### Singly Circular
```lua
local function create_circular_slist(values)
local head = nil
local prev = nil
for _, v in ipairs(values) do
local node = { value = v, next = nil }
if not head then head = node end
if prev then prev.next = node end
prev = node
end
if prev then prev.next = head end -- close the loop
return head
end
-- Traverse with a count limit to avoid an infinite loop
local function traverse_circular(head, limit)
local count = 0
local current = head
while current and count < limit do
print(current.value)
current = current.next
count = count + 1
end
end
local h = create_circular_slist({ "a", "b", "c" })
traverse_circular(h, 6)
-- > a
-- > b
-- > c
-- > a
-- > b
-- > c
```lua
### Doubly Circular
In a doubly circular list, the head and tail point to each other:
```lua
local function create_circular_dll(values)
local head = nil
for _, v in ipairs(values) do
local node = { value = v }
if not head then
head = node
node.next = node
node.prev = node
else
node.next = head
node.prev = head.prev
head.prev.next = node
head.prev = node
end
end
return head
end
```lua
## Garbage Collection and Reference Cycles
One of Lua's strengths is automatic garbage collection. When you remove a node from a linked list by overwriting the reference to it, Lua's GC automatically frees the unreferenced table — provided no other variable still holds a reference to it.
```lua
current.next = nil -- node is now eligible for GC
```lua
With doubly linked lists, you can create **reference cycles** — node A's `next` points to node B, and node B's `prev` points back to node A. Lua's GC handles cycles correctly as long as no external reference points into the cycle. If you store a node reference in a variable and then lose all other references to the cycle, you may need to explicitly break the cycle before GC can collect it:
```lua
-- Break a cycle before GC can act
node.prev.next = nil
node.prev = nil
node.next = nil
```lua
For singly linked lists, cycles aren't possible since each `next` pointer only goes forward.
## Performance Trade-offs
Here's how linked lists compare to Lua tables (which act like dynamic arrays) across common operations:
| Operation | Singly Linked (head) | Singly Linked (tail) | Lua Table Array |
|---|---|---|---|
| Insert at head | **O(1)** | O(n) | O(n) — shift elements |
| Insert at tail | O(n) | O(n) (or O(1) with tail ptr) | O(1) amortised |
| Delete at head | **O(1)** | O(n) | O(n) — shift elements |
| Delete by value | O(n) | O(n) | O(n) |
| Delete with node ref | O(n) (need prev) | O(n) | N/A |
| Search by value | O(n) | O(n) | O(n) (unsorted) / O(log n) (sorted) |
| Random access by index | O(n) | O(n) | **O(1)** |
| Key-value lookup | O(n) | O(n) | **O(1)** |
For read-heavy workloads with random access, Lua tables win decisively. For write-heavy workloads with frequent insertions and deletions at arbitrary positions — especially when the cost of copying large elements matters — linked lists have a genuine advantage.
## When Linked Lists Beat Lua Tables
Tables are the right default. But linked lists genuinely outperform in a few specific cases:
**Frequent middle insertions and deletions.** Pointer redirection is O(1) regardless of position. With a table, inserting at index 5 means shifting every element after index 5. If your elements are large objects rather than numbers, this copying cost becomes significant.
**Stable iterators during modification.** When you use `pairs` or `ipairs` on a table and delete the current element, the iterator breaks or skips elements. A linked list iterator operates on a fixed node reference — deleting the current node mid-iteration is safe.
**Splice and cut-paste operations.** Moving a contiguous subsequence of nodes to a different position is a handful of pointer reassignments. With a table, you'd need to identify the range, remove it, and insert it — involving multiple O(n) shifts.
**Custom memory layout and object pooling.** Linked lists let you pre-allocate nodes and recycle them. This is useful in game development when you need to manage a pool of entities (bullets, particles, enemies) with deterministic allocation and deallocation.
## Custom Iterators
One underappreciated feature of linked lists in Lua is the ability to write custom iterators that can pause, resume, or filter mid-traversal. Here's an iterator that skips `nil` values and one that stops early:
```lua
local function list_iter(list)
local current = list
return function()
if not current then return nil end
local value = current.value
current = current.next
return value
end
end
local list = { value = 1, next = { value = 2, next = { value = 3, next = nil } } }
for v in list_iter(list) do
print(v)
end
-- > 1
-- > 2
-- > 3
```lua
You could extend this pattern to create iterators that filter by a predicate, skip to a condition, or yield intermediate results — all without rebuilding the list.
## Summary
Linked lists are pointer-based data structures that give you O(1) insertions and deletions at known positions, stable iterators during modification, and explicit control over memory layout. In Lua, you build them using ordinary tables — `nil` is the natural terminator, and garbage collection handles cleanup automatically.
For most programs, Lua tables are the better choice. But when you're dealing with large elements that are expensive to copy, need to iterate safely while modifying, or want to splice sublists without copying, linked lists earn their place. The canonical example — a singly linked list used to implement a stack — is worth memorizing, because stacks and queues are the foundation of many algorithms you'll encounter.
## See Also
- [Arrays and Lists in Lua](/tutorials/ds-arrays-and-lists/) — the natural predecessor in this series, covering how Lua tables function as dynamic arrays
- [Stacks and Queues in Lua](/tutorials/ds-stacks-and-queues/) — the natural follow-on, showing how linked list concepts power these higher-level abstractions