1//! A singly-linked list is headed by a single forward pointer. The elements
2//! are singly-linked for minimum space and pointer manipulation overhead at
3//! the expense of O(n) removal for arbitrary elements. New elements can be
4//! added to the list after an existing element or at the head of the list.
5//!
6//! A singly-linked list may only be traversed in the forward direction.
7//!
8//! Singly-linked lists are useful under these conditions:
9//! * Ability to preallocate elements / requirement of infallibility for
10//! insertion.
11//! * Ability to allocate elements intrusively along with other data.
12//! * Homogenous elements.
13
14const std = @import("std.zig");
15const debug = std.debug;
16const assert = debug.assert;
17const testing = std.testing;
18const SinglyLinkedList = @This();
19
20first: ?*Node = null,
21
22/// This struct contains only a next pointer and not any data payload. The
23/// intended usage is to embed it intrusively into another data structure and
24/// access the data with `@fieldParentPtr`.
25pub const Node = struct {
26 next: ?*Node = null,
27
28 pub fn insertAfter(node: *Node, new_node: *Node) void {
29 new_node.next = node.next;
30 node.next = new_node;
31 }
32
33 /// Remove the node after the one provided, returning it.
34 pub fn removeNext(node: *Node) ?*Node {
35 const next_node = node.next orelse return null;
36 node.next = next_node.next;
37 return next_node;
38 }
39
40 /// Iterate over the singly-linked list from this node, until the final
41 /// node is found.
42 ///
43 /// This operation is O(N). Instead of calling this function, consider
44 /// using a different data structure.
45 pub fn findLast(node: *Node) *Node {
46 var it = node;
47 while (true) {
48 it = it.next orelse return it;
49 }
50 }
51
52 /// Iterate over each next node, returning the count of all nodes except
53 /// the starting one.
54 ///
55 /// This operation is O(N). Instead of calling this function, consider
56 /// using a different data structure.
57 pub fn countChildren(node: *const Node) usize {
58 var count: usize = 0;
59 var it: ?*const Node = node.next;
60 while (it) |n| : (it = n.next) {
61 count += 1;
62 }
63 return count;
64 }
65
66 /// Reverse the list starting from this node in-place.
67 ///
68 /// This operation is O(N). Instead of calling this function, consider
69 /// using a different data structure.
70 pub fn reverse(indirect: *?*Node) void {
71 if (indirect.* == null) {
72 return;
73 }
74 var current: *Node = indirect.*.?;
75 while (current.next) |next| {
76 current.next = next.next;
77 next.next = indirect.*;
78 indirect.* = next;
79 }
80 }
81};
82
83pub fn prepend(list: *SinglyLinkedList, new_node: *Node) void {
84 new_node.next = list.first;
85 list.first = new_node;
86}
87
88/// Remove `node` from the list.
89/// Asserts that `node` is in the list.
90pub fn remove(list: *SinglyLinkedList, node: *const Node) void {
91 if (list.first == node) {
92 list.first = node.next;
93 } else {
94 var current_elm = list.first.?;
95 while (current_elm.next != node) {
96 current_elm = current_elm.next.?;
97 }
98 current_elm.next = node.next;
99 }
100}
101
102/// Remove and return the first node in the list.
103pub fn popFirst(list: *SinglyLinkedList) ?*Node {
104 const first = list.first orelse return null;
105 list.first = first.next;
106 return first;
107}
108
109/// Iterate over all nodes, returning the count.
110///
111/// This operation is O(N). Consider tracking the length separately rather than
112/// computing it.
113pub fn len(list: SinglyLinkedList) usize {
114 if (list.first) |n| {
115 return 1 + n.countChildren();
116 } else {
117 return 0;
118 }
119}
120
121test "basics" {
122 const L = struct {
123 data: u32,
124 node: SinglyLinkedList.Node = .{},
125 };
126 var list: SinglyLinkedList = .{};
127
128 try testing.expect(list.len() == 0);
129
130 var one: L = .{ .data = 1 };
131 var two: L = .{ .data = 2 };
132 var three: L = .{ .data = 3 };
133 var four: L = .{ .data = 4 };
134 var five: L = .{ .data = 5 };
135
136 list.prepend(&two.node); // {2}
137 two.node.insertAfter(&five.node); // {2, 5}
138 list.prepend(&one.node); // {1, 2, 5}
139 two.node.insertAfter(&three.node); // {1, 2, 3, 5}
140 three.node.insertAfter(&four.node); // {1, 2, 3, 4, 5}
141
142 try testing.expect(list.len() == 5);
143
144 // Traverse forwards.
145 {
146 var it = list.first;
147 var index: u32 = 1;
148 while (it) |node| : (it = node.next) {
149 const l: *L = @fieldParentPtr("node", node);
150 try testing.expect(l.data == index);
151 index += 1;
152 }
153 }
154
155 _ = list.popFirst(); // {2, 3, 4, 5}
156 _ = list.remove(&five.node); // {2, 3, 4}
157 _ = two.node.removeNext(); // {2, 4}
158
159 try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?)).data == 2);
160 try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?.next.?)).data == 4);
161 try testing.expect(list.first.?.next.?.next == null);
162
163 SinglyLinkedList.Node.reverse(&list.first);
164
165 try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?)).data == 4);
166 try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?.next.?)).data == 2);
167 try testing.expect(list.first.?.next.?.next == null);
168}