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: *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}