Zig’s standard library provides both doubly and singly linked list implementations.
DoublyLinkedList
pub fn DoublyLinkedList(comptime T: type) type
Node Structure
pub const Node = struct {
prev: ?*Node,
next: ?*Node,
data: T,
};
Pointer to the previous node, or null if this is the first node.
Pointer to the next node, or null if this is the last node.
List Structure
pub const DoublyLinkedList(T) = struct {
first: ?*Node,
last: ?*Node,
len: usize,
};
Methods
prepend
pub fn prepend(list: *DoublyLinkedList(T), node: *Node) void
append
pub fn append(list: *DoublyLinkedList(T), node: *Node) void
insertAfter
pub fn insertAfter(list: *DoublyLinkedList(T), node: *Node, new_node: *Node) void
new_node after the specified node.
insertBefore
pub fn insertBefore(list: *DoublyLinkedList(T), node: *Node, new_node: *Node) void
new_node before the specified node.
remove
pub fn remove(list: *DoublyLinkedList(T), node: *Node) void
pop
pub fn pop(list: *DoublyLinkedList(T)) ?*Node
popFirst
pub fn popFirst(list: *DoublyLinkedList(T)) ?*Node
Usage Example
const std = @import("std");
const DoublyLinkedList = std.DoublyLinkedList;
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list = DoublyLinkedList(i32){};
// Create and add nodes
var node1 = try allocator.create(DoublyLinkedList(i32).Node);
node1.data = 1;
list.append(node1);
var node2 = try allocator.create(DoublyLinkedList(i32).Node);
node2.data = 2;
list.append(node2);
var node3 = try allocator.create(DoublyLinkedList(i32).Node);
node3.data = 3;
list.prepend(node3);
// Iterate forward
var it = list.first;
while (it) |node| : (it = node.next) {
std.debug.print("{} ", .{node.data});
}
// Output: 3 1 2
// Iterate backward
it = list.last;
while (it) |node| : (it = node.prev) {
std.debug.print("{} ", .{node.data});
}
// Output: 2 1 3
// Clean up
while (list.popFirst()) |node| {
allocator.destroy(node);
}
}
SinglyLinkedList
pub fn SinglyLinkedList(comptime T: type) type
Node Structure
pub const Node = struct {
next: ?*Node,
data: T,
};
Pointer to the next node, or null if this is the last node.
List Structure
pub const SinglyLinkedList(T) = struct {
first: ?*Node,
};
Methods
prepend
pub fn prepend(list: *SinglyLinkedList(T), node: *Node) void
popFirst
pub fn popFirst(list: *SinglyLinkedList(T)) ?*Node
insertAfter
pub fn insertAfter(list: *SinglyLinkedList(T), node: *Node, new_node: *Node) void
new_node after the specified node. O(1) operation.
removeAfter
pub fn removeAfter(list: *SinglyLinkedList(T), node: *Node) ?*Node
node, or null if there is none. O(1) operation.
findFirst
pub fn findFirst(list: SinglyLinkedList(T)) ?*Node
Usage Example
const std = @import("std");
const SinglyLinkedList = std.SinglyLinkedList;
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list = SinglyLinkedList(i32){};
// Create and add nodes
var node1 = try allocator.create(SinglyLinkedList(i32).Node);
node1.data = 1;
list.prepend(node1);
var node2 = try allocator.create(SinglyLinkedList(i32).Node);
node2.data = 2;
list.prepend(node2);
// Iterate
var it = list.first;
while (it) |node| : (it = node.next) {
std.debug.print("{} ", .{node.data});
}
// Output: 2 1
// Clean up
while (list.popFirst()) |node| {
allocator.destroy(node);
}
}
When to Use
DoublyLinkedList
✓ Need to traverse in both directions
✓ Need to remove nodes efficiently from anywhere in the list
✓ Implementing a deque or LRU cache
SinglyLinkedList
✓ Only need forward traversal
✓ Memory is constrained (smaller node size)
✓ Implementing a stack or queue
✓ Need simple LIFO ordering
| Operation | DoublyLinkedList | SinglyLinkedList |
|---|
| Prepend | O(1) | O(1) |
| Append | O(1) | O(n) |
| Insert After | O(1) | O(1) |
| Remove | O(1) | O(n) |
| Access by index | O(n) | O(n) |
| Memory per node | 2 pointers + data | 1 pointer + data |
For most use cases requiring a dynamic collection, consider ArrayList which provides better cache locality and performance.
- ArrayList - Contiguous dynamic array (usually preferred)
- HashMap - Hash-based key-value storage