1//! A doubly-linked list has a pair of pointers to both the head and
2//! tail of the list. List elements have pointers to both the previous
3//! and next elements in the sequence. The list can be traversed both
4//! forward and backward. Some operations that take linear O(n) time
5//! with a singly-linked list can be done without traversal in constant
6//! O(1) time with a doubly-linked list:
7//!
8//! * Removing an element.
9//! * Inserting a new element before an existing element.
10//! * Pushing or popping an element from the end of the list.
11
12const std = @import("std.zig");
13const debug = std.debug;
14const assert = debug.assert;
15const testing = std.testing;
16const DoublyLinkedList = @This();
17
18first: ?*Node = null,
19last: ?*Node = null,
20
21/// This struct contains only the prev and next pointers and not any data
22/// payload. The intended usage is to embed it intrusively into another data
23/// structure and access the data with `@fieldParentPtr`.
24pub const Node = struct {
25 prev: ?*Node = null,
26 next: ?*Node = null,
27};
28
29pub fn insertAfter(list: *DoublyLinkedList, existing_node: *Node, new_node: *Node) void {
30 new_node.prev = existing_node;
31 if (existing_node.next) |next_node| {
32 // Intermediate node.
33 new_node.next = next_node;
34 next_node.prev = new_node;
35 } else {
36 // Last element of the list.
37 new_node.next = null;
38 list.last = new_node;
39 }
40 existing_node.next = new_node;
41}
42
43pub fn insertBefore(list: *DoublyLinkedList, existing_node: *Node, new_node: *Node) void {
44 new_node.next = existing_node;
45 if (existing_node.prev) |prev_node| {
46 // Intermediate node.
47 new_node.prev = prev_node;
48 prev_node.next = new_node;
49 } else {
50 // First element of the list.
51 new_node.prev = null;
52 list.first = new_node;
53 }
54 existing_node.prev = new_node;
55}
56
57/// Concatenate list2 onto the end of list1, removing all entries from the former.
58///
59/// Arguments:
60/// list1: the list to concatenate onto
61/// list2: the list to be concatenated
62pub fn concatByMoving(list1: *DoublyLinkedList, list2: *DoublyLinkedList) void {
63 const l2_first = list2.first orelse return;
64 if (list1.last) |l1_last| {
65 l1_last.next = list2.first;
66 l2_first.prev = list1.last;
67 } else {
68 // list1 was empty
69 list1.first = list2.first;
70 }
71 list1.last = list2.last;
72 list2.first = null;
73 list2.last = null;
74}
75
76/// Insert a new node at the end of the list.
77///
78/// Arguments:
79/// new_node: Pointer to the new node to insert.
80pub fn append(list: *DoublyLinkedList, new_node: *Node) void {
81 if (list.last) |last| {
82 // Insert after last.
83 list.insertAfter(last, new_node);
84 } else {
85 // Empty list.
86 list.prepend(new_node);
87 }
88}
89
90/// Insert a new node at the beginning of the list.
91///
92/// Arguments:
93/// new_node: Pointer to the new node to insert.
94pub fn prepend(list: *DoublyLinkedList, new_node: *Node) void {
95 if (list.first) |first| {
96 // Insert before first.
97 list.insertBefore(first, new_node);
98 } else {
99 // Empty list.
100 list.first = new_node;
101 list.last = new_node;
102 new_node.prev = null;
103 new_node.next = null;
104 }
105}
106
107/// Remove a node from the list.
108/// Assumes the node is in the list.
109///
110/// Arguments:
111/// node: Pointer to the node to be removed.
112pub fn remove(list: *DoublyLinkedList, node: *const Node) void {
113 if (node.prev) |prev_node| {
114 // Intermediate node.
115 prev_node.next = node.next;
116 } else {
117 // First element of the list.
118 list.first = node.next;
119 }
120
121 if (node.next) |next_node| {
122 // Intermediate node.
123 next_node.prev = node.prev;
124 } else {
125 // Last element of the list.
126 list.last = node.prev;
127 }
128}
129
130/// Remove and return a pointer to the last node in the list.
131pub fn popLast(list: *DoublyLinkedList) ?*Node {
132 const last = list.last orelse return null;
133 list.remove(last);
134 return last;
135}
136
137/// Deprecated in favor of `popLast`
138pub const pop = popLast;
139
140/// Remove and return a pointer to the first node in the list.
141pub fn popFirst(list: *DoublyLinkedList) ?*Node {
142 const first = list.first orelse return null;
143 list.remove(first);
144 return first;
145}
146
147/// Iterate over all nodes, returning the count.
148///
149/// This operation is O(N). Consider tracking the length separately rather than
150/// computing it.
151pub fn len(list: DoublyLinkedList) usize {
152 var count: usize = 0;
153 var it: ?*const Node = list.first;
154 while (it) |n| : (it = n.next) count += 1;
155 return count;
156}
157
158test "basics" {
159 const L = struct {
160 data: u32,
161 node: DoublyLinkedList.Node = .{},
162 };
163 var list: DoublyLinkedList = .{};
164
165 var one: L = .{ .data = 1 };
166 var two: L = .{ .data = 2 };
167 var three: L = .{ .data = 3 };
168 var four: L = .{ .data = 4 };
169 var five: L = .{ .data = 5 };
170
171 list.append(&two.node); // {2}
172 list.append(&five.node); // {2, 5}
173 list.prepend(&one.node); // {1, 2, 5}
174 list.insertBefore(&five.node, &four.node); // {1, 2, 4, 5}
175 list.insertAfter(&two.node, &three.node); // {1, 2, 3, 4, 5}
176
177 // Traverse forwards.
178 {
179 var it = list.first;
180 var index: u32 = 1;
181 while (it) |node| : (it = node.next) {
182 const l: *L = @fieldParentPtr("node", node);
183 try testing.expect(l.data == index);
184 index += 1;
185 }
186 }
187
188 // Traverse backwards.
189 {
190 var it = list.last;
191 var index: u32 = 1;
192 while (it) |node| : (it = node.prev) {
193 const l: *L = @fieldParentPtr("node", node);
194 try testing.expect(l.data == (6 - index));
195 index += 1;
196 }
197 }
198
199 _ = list.popFirst(); // {2, 3, 4, 5}
200 _ = list.popLast(); // {2, 3, 4}
201 list.remove(&three.node); // {2, 4}
202
203 // peek first and last elements of the list
204 try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?)).data == 2);
205 try testing.expect(@as(*L, @fieldParentPtr("node", list.last.?)).data == 4);
206
207 // list length
208 try testing.expect(list.len() == 2);
209}
210
211test "concatenation" {
212 const L = struct {
213 data: u32,
214 node: DoublyLinkedList.Node = .{},
215 };
216 var list1: DoublyLinkedList = .{};
217 var list2: DoublyLinkedList = .{};
218
219 var one: L = .{ .data = 1 };
220 var two: L = .{ .data = 2 };
221 var three: L = .{ .data = 3 };
222 var four: L = .{ .data = 4 };
223 var five: L = .{ .data = 5 };
224
225 list1.append(&one.node);
226 list1.append(&two.node);
227 list2.append(&three.node);
228 list2.append(&four.node);
229 list2.append(&five.node);
230
231 list1.concatByMoving(&list2);
232
233 try testing.expect(list1.last == &five.node);
234 try testing.expect(list1.len() == 5);
235 try testing.expect(list2.first == null);
236 try testing.expect(list2.last == null);
237 try testing.expect(list2.len() == 0);
238
239 // Traverse forwards.
240 {
241 var it = list1.first;
242 var index: u32 = 1;
243 while (it) |node| : (it = node.next) {
244 const l: *L = @fieldParentPtr("node", node);
245 try testing.expect(l.data == index);
246 index += 1;
247 }
248 }
249
250 // Traverse backwards.
251 {
252 var it = list1.last;
253 var index: u32 = 1;
254 while (it) |node| : (it = node.prev) {
255 const l: *L = @fieldParentPtr("node", node);
256 try testing.expect(l.data == (6 - index));
257 index += 1;
258 }
259 }
260
261 // Swap them back, this verifies that concatenating to an empty list works.
262 list2.concatByMoving(&list1);
263
264 // Traverse forwards.
265 {
266 var it = list2.first;
267 var index: u32 = 1;
268 while (it) |node| : (it = node.next) {
269 const l: *L = @fieldParentPtr("node", node);
270 try testing.expect(l.data == index);
271 index += 1;
272 }
273 }
274
275 // Traverse backwards.
276 {
277 var it = list2.last;
278 var index: u32 = 1;
279 while (it) |node| : (it = node.prev) {
280 const l: *L = @fieldParentPtr("node", node);
281 try testing.expect(l.data == (6 - index));
282 index += 1;
283 }
284 }
285}