1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
const std = @import("std");
const testing = std.testing;
/// An intrusive doubly-linked list. The type T must have a "next" and "prev"
/// field pointing to itself.
///
/// This is an adaptation of the DoublyLinkedList from the Zig standard
/// library, which is MIT licensed. I've removed functionality that I don't
/// need.
pub fn DoublyLinkedList(comptime T: type) type {
return struct {
const Self = @This();
/// The type of the node in the list. This makes it easy to get the
/// node type from the list type.
pub const Node = T;
first: ?*Node = null,
last: ?*Node = null,
/// Insert a new node after an existing one.
///
/// Arguments:
/// node: Pointer to a node in the list.
/// new_node: Pointer to the new node to insert.
pub inline fn insertAfter(list: *Self, node: *Node, new_node: *Node) void {
new_node.prev = node;
if (node.next) |next_node| {
// Intermediate node.
new_node.next = next_node;
next_node.prev = new_node;
} else {
// Last element of the list.
new_node.next = null;
list.last = new_node;
}
node.next = new_node;
}
/// Insert a new node before an existing one.
///
/// Arguments:
/// node: Pointer to a node in the list.
/// new_node: Pointer to the new node to insert.
pub inline fn insertBefore(list: *Self, node: *Node, new_node: *Node) void {
new_node.next = node;
if (node.prev) |prev_node| {
// Intermediate node.
new_node.prev = prev_node;
prev_node.next = new_node;
} else {
// First element of the list.
new_node.prev = null;
list.first = new_node;
}
node.prev = new_node;
}
/// Insert a new node at the end of the list.
///
/// Arguments:
/// new_node: Pointer to the new node to insert.
pub inline fn append(list: *Self, new_node: *Node) void {
if (list.last) |last| {
// Insert after last.
list.insertAfter(last, new_node);
} else {
// Empty list.
list.prepend(new_node);
}
}
/// Insert a new node at the beginning of the list.
///
/// Arguments:
/// new_node: Pointer to the new node to insert.
pub inline fn prepend(list: *Self, new_node: *Node) void {
if (list.first) |first| {
// Insert before first.
list.insertBefore(first, new_node);
} else {
// Empty list.
list.first = new_node;
list.last = new_node;
new_node.prev = null;
new_node.next = null;
}
}
/// Remove a node from the list.
///
/// Arguments:
/// node: Pointer to the node to be removed.
pub inline fn remove(list: *Self, node: *Node) void {
if (node.prev) |prev_node| {
// Intermediate node.
prev_node.next = node.next;
} else {
// First element of the list.
list.first = node.next;
}
if (node.next) |next_node| {
// Intermediate node.
next_node.prev = node.prev;
} else {
// Last element of the list.
list.last = node.prev;
}
}
/// Remove and return the last node in the list.
///
/// Returns:
/// A pointer to the last node in the list.
pub inline fn pop(list: *Self) ?*Node {
const last = list.last orelse return null;
list.remove(last);
return last;
}
/// Remove and return the first node in the list.
///
/// Returns:
/// A pointer to the first node in the list.
pub inline fn popFirst(list: *Self) ?*Node {
const first = list.first orelse return null;
list.remove(first);
return first;
}
};
}
test "basic DoublyLinkedList test" {
const Node = struct {
data: u32,
prev: ?*@This() = null,
next: ?*@This() = null,
};
const L = DoublyLinkedList(Node);
var list: L = .{};
var one: Node = .{ .data = 1 };
var two: Node = .{ .data = 2 };
var three: Node = .{ .data = 3 };
var four: Node = .{ .data = 4 };
var five: Node = .{ .data = 5 };
list.append(&two); // {2}
list.append(&five); // {2, 5}
list.prepend(&one); // {1, 2, 5}
list.insertBefore(&five, &four); // {1, 2, 4, 5}
list.insertAfter(&two, &three); // {1, 2, 3, 4, 5}
// Traverse forwards.
{
var it = list.first;
var index: u32 = 1;
while (it) |node| : (it = node.next) {
try testing.expect(node.data == index);
index += 1;
}
}
// Traverse backwards.
{
var it = list.last;
var index: u32 = 1;
while (it) |node| : (it = node.prev) {
try testing.expect(node.data == (6 - index));
index += 1;
}
}
_ = list.popFirst(); // {2, 3, 4, 5}
_ = list.pop(); // {2, 3, 4}
list.remove(&three); // {2, 4}
try testing.expect(list.first.?.data == 2);
try testing.expect(list.last.?.data == 4);
}
|
