This struct contains only a next pointer and not any data payload. The
intended usage is to embed it intrusively into another data structure and
access the data with @fieldParentPtr.
pub const Node = structpub const Node = struct {
next: ?*Node = null,
pub fn insertAfter(node: *Node, new_node: *Node) void {
new_node.next = node.next;
node.next = new_node;
}
/// Remove the node after the one provided, returning it.
pub fn removeNext(node: *Node) ?*Node {
const next_node = node.next orelse return null;
node.next = next_node.next;
return next_node;
}
/// Iterate over the singly-linked list from this node, until the final
/// node is found.
///
/// This operation is O(N). Instead of calling this function, consider
/// using a different data structure.
pub fn findLast(node: *Node) *Node {
var it = node;
while (true) {
it = it.next orelse return it;
}
}
/// Iterate over each next node, returning the count of all nodes except
/// the starting one.
///
/// This operation is O(N). Instead of calling this function, consider
/// using a different data structure.
pub fn countChildren(node: *const Node) usize {
var count: usize = 0;
var it: ?*const Node = node.next;
while (it) |n| : (it = n.next) {
count += 1;
}
return count;
}
/// Reverse the list starting from this node in-place.
///
/// This operation is O(N). Instead of calling this function, consider
/// using a different data structure.
pub fn reverse(indirect: *?*Node) void {
if (indirect.* == null) {
return;
}
var current: *Node = indirect.*.?;
while (current.next) |next| {
current.next = next.next;
next.next = indirect.*;
indirect.* = next;
}
}
}