master
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: *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 the last node in the list.
131///
132/// Returns:
133/// A pointer to the last node in the list.
134pub fn pop(list: *DoublyLinkedList) ?*Node {
135 const last = list.last orelse return null;
136 list.remove(last);
137 return last;
138}
139
140/// Remove and return the first node in the list.
141///
142/// Returns:
143/// A pointer to the first node in the list.
144pub fn popFirst(list: *DoublyLinkedList) ?*Node {
145 const first = list.first orelse return null;
146 list.remove(first);
147 return first;
148}
149
150/// Iterate over all nodes, returning the count.
151///
152/// This operation is O(N). Consider tracking the length separately rather than
153/// computing it.
154pub fn len(list: DoublyLinkedList) usize {
155 var count: usize = 0;
156 var it: ?*const Node = list.first;
157 while (it) |n| : (it = n.next) count += 1;
158 return count;
159}
160
161test "basics" {
162 const L = struct {
163 data: u32,
164 node: DoublyLinkedList.Node = .{},
165 };
166 var list: DoublyLinkedList = .{};
167
168 var one: L = .{ .data = 1 };
169 var two: L = .{ .data = 2 };
170 var three: L = .{ .data = 3 };
171 var four: L = .{ .data = 4 };
172 var five: L = .{ .data = 5 };
173
174 list.append(&two.node); // {2}
175 list.append(&five.node); // {2, 5}
176 list.prepend(&one.node); // {1, 2, 5}
177 list.insertBefore(&five.node, &four.node); // {1, 2, 4, 5}
178 list.insertAfter(&two.node, &three.node); // {1, 2, 3, 4, 5}
179
180 // Traverse forwards.
181 {
182 var it = list.first;
183 var index: u32 = 1;
184 while (it) |node| : (it = node.next) {
185 const l: *L = @fieldParentPtr("node", node);
186 try testing.expect(l.data == index);
187 index += 1;
188 }
189 }
190
191 // Traverse backwards.
192 {
193 var it = list.last;
194 var index: u32 = 1;
195 while (it) |node| : (it = node.prev) {
196 const l: *L = @fieldParentPtr("node", node);
197 try testing.expect(l.data == (6 - index));
198 index += 1;
199 }
200 }
201
202 _ = list.popFirst(); // {2, 3, 4, 5}
203 _ = list.pop(); // {2, 3, 4}
204 list.remove(&three.node); // {2, 4}
205
206 try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?)).data == 2);
207 try testing.expect(@as(*L, @fieldParentPtr("node", list.last.?)).data == 4);
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}