Something went wrong. Try again.
Something went wrong. Try again.
5.7 kB · 181 lines
Zig
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182const 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);}