Zig implementation of singly linked list.

main.zig

const std = @import("std");
const Allocator = std.mem.Allocator;

pub const LinkedList = struct {
    head: ?*Node,
    tail: ?*Node,
    count: usize,
    allocator: Allocator,

    const Node = struct {
        next: ?*Node,
        value: i32,
    };

    pub fn init(allocator: Allocator) LinkedList {
        return .{
            .head = null,
            .tail = null,
            .count = 0,
            .allocator = allocator,
        };
    }

    pub fn deinit(self: *LinkedList) void {
        var current = self.head;
        while (current) |cur| {
            current = cur.next;
            self.allocator.destroy(cur);
        }
        self.head = undefined;
        self.tail = undefined;
    }

    pub fn addLast(self: *LinkedList, value: i32) !void {
        const node = try self.allocator.create(Node);
        node.* = .{
            .next = null,
            .value = value,
        };

        if (self.tail) |t| {
            t.next = node;
        }
        self.tail = node;
        if (self.head == null) {
            self.head = node;
        }

        self.count += 1;
    }

    pub fn addFirst(self: *LinkedList, value: i32) !void {
        const node = try self.allocator.create(Node);
        node.* = .{
            .next = null,
            .value = value,
        };

        if (self.head) |h| {
            node.next = h;
        }
        self.head = node;
        if (self.tail == null) {
            self.tail = node;
        }
        self.count += 1;
    }

    pub fn addAfter(self: *LinkedList, after: i32, value: i32) !bool {
        var find_node = self.head;
        while (find_node) |n| {
            if (n.value == after) break;
            find_node = n.next;
        }

        if (find_node) |n| {
            const node = try self.allocator.create(Node);
            node.* = .{
                .next = n.next,
                .value = value,
            };
            n.next = node;

            if (n == self.tail) {
                self.tail = node;
            }

            self.count += 1;
            return true;
        }
        return false;
    }

    pub fn remove(self: *LinkedList, value: i32) bool {
        var prev_node: ?*Node = null;
        var find_node = self.head;
        while (find_node) |n| {
            if (n.value == value) break;
            prev_node = n;
            find_node = n.next;
        }

        if (find_node) |n| {
            // We have 3 possibilities:
            // 1. find_node is a head. Remove head, change head reference to new head.
            // 2. find_node is a middle node. Change the next of previous node to the next of find_node.
            // 3. find node is a tail. Change the next of previous to null, then change tail reference.
            // Generally for case 2, and 3, we can use same code to change the reference,
            // but had to check if find_node is tail, then change tail reference to previous node.
            if (prev_node) |prev| {
                prev.next = n.next;
                if (n == self.tail) {
                    self.tail = prev;
                }
            } else {
                self.head = n.next;
                n.next = null;

                if (self.head == null) {
                    self.tail = null;
                }
            }

            // don't forget to deallocate the find_node.
            self.allocator.destroy(n);
            self.count -= 1;
            return true;
        }
        return false;
    }

    pub fn removeAll(self: *LinkedList) void {
        var current = self.head;
        while (current) |c| {
            current = c.next;
            self.allocator.destroy(c);
        }
        self.head = null;
        self.tail = null;
        self.count = 0;
    }

    pub fn toOwnedSlice(self: *LinkedList) ![]i32 {
        const result: []i32 = try self.allocator.alloc(i32, self.count);
        if (self.count > 0) {
            var current = self.head;
            var count: usize = 0;
            while (current) |c| {
                current = c.next;
                result[count] = c.value;
                count += 1;
            }
        }
        return result;
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    var list = LinkedList.init(allocator);
    defer list.deinit();

    try list.addLast(10);
    try list.addLast(5);
    try list.addLast(7);
    try list.addLast(1);
    try list.addLast(8);

    _ = list.remove(10);
    _ = list.remove(7);
    _ = list.remove(8);

    var items = try list.toOwnedSlice();
    defer allocator.free(items);
    std.log.debug("{any}\n", .{items});
}

const testing = std.testing;
const test_allocator = std.testing.allocator;

test "LinkedList addLast" {
    var list = LinkedList.init(test_allocator);
    defer list.deinit();

    try list.addLast(10);
    try list.addLast(5);
    try list.addLast(7);
    try list.addLast(1);
    try list.addLast(8);

    try testing.expectEqual(@as(usize, 5), list.count);
    const i = try list.toOwnedSlice();
    defer test_allocator.free(i);
    try testing.expectEqualSlices(i32, &[_]i32{ 10, 5, 7, 1, 8 }, i);
}

test "LinkedList removing items random order" {
    var list = LinkedList.init(test_allocator);
    defer list.deinit();

    try list.addLast(10);
    try list.addLast(5);
    try list.addLast(7);
    try list.addLast(1);
    try list.addLast(8);

    try testing.expect(list.remove(10) == true);
    try testing.expectEqual(@as(usize, 4), list.count);
    const o = try list.toOwnedSlice();
    defer test_allocator.free(o);
    try testing.expectEqualSlices(i32, &[_]i32{ 5, 7, 1, 8 }, o);

    try testing.expect(list.remove(7) == true);
    try testing.expectEqual(@as(usize, 3), list.count);
    const p = try list.toOwnedSlice();
    defer test_allocator.free(p);
    try testing.expectEqualSlices(i32, &[_]i32{ 5, 1, 8 }, p);

    try testing.expect(list.remove(8) == true);
    try testing.expectEqual(@as(usize, 2), list.count);
    const q = try list.toOwnedSlice();
    defer test_allocator.free(q);
    try testing.expectEqualSlices(i32, &[_]i32{ 5, 1 }, q);

    try testing.expect(list.remove(109) == false);
    try testing.expectEqual(@as(usize, 2), list.count);

    const items = try list.toOwnedSlice();
    defer test_allocator.free(items);
    try testing.expectEqualSlices(i32, &[_]i32{ 5, 1 }, items);
}

test "LinkedList removing all items" {
    var list = LinkedList.init(test_allocator);
    defer list.deinit();

    try list.addLast(10);
    try list.addLast(5);
    try list.addLast(7);
    try list.addLast(1);
    try list.addLast(8);

    try testing.expect(list.remove(10) == true);
    try testing.expect(list.remove(7) == true);
    try testing.expect(list.remove(8) == true);
    try testing.expect(list.remove(5) == true);
    try testing.expect(list.remove(1) == true);
    try testing.expectEqual(@as(usize, 0), list.count);
    try testing.expect(list.head == null);
    try testing.expect(list.tail == null);

    const o = try list.toOwnedSlice();
    defer test_allocator.free(o);
    try testing.expectEqualSlices(i32, &[_]i32{}, o);
}

test "LinkedList removeAll" {
    var list = LinkedList.init(test_allocator);
    defer list.deinit();

    try list.addLast(10);
    try list.addLast(5);
    try list.addLast(7);
    try list.addLast(1);
    try list.addLast(8);

    list.removeAll();

    try testing.expectEqual(@as(usize, 0), list.count);
    try testing.expect(list.head == null);
    try testing.expect(list.tail == null);

    const o = try list.toOwnedSlice();
    defer test_allocator.free(o);
    try testing.expectEqualSlices(i32, &[_]i32{}, o);
}

test "LinkedList addFirst" {
    var list = LinkedList.init(test_allocator);
    defer list.deinit();

    try list.addFirst(10);
    try list.addFirst(5);
    try list.addFirst(7);
    try list.addFirst(1);
    try list.addFirst(8);

    try testing.expectEqual(@as(usize, 5), list.count);
    const i = try list.toOwnedSlice();
    defer test_allocator.free(i);
    try testing.expectEqualSlices(i32, &[_]i32{ 8, 1, 7, 5, 10 }, i);
}

test "LinkedList addAfter" {
    var list = LinkedList.init(test_allocator);
    defer list.deinit();

    try list.addLast(10);
    try testing.expect(try list.addAfter(10, 5) == true);
    try testing.expect(try list.addAfter(5, 8) == true);
    try testing.expect(try list.addAfter(5, 7) == true);
    try testing.expect(try list.addAfter(10, 1) == true);

    try testing.expectEqual(@as(usize, 5), list.count);
    const i = try list.toOwnedSlice();
    defer test_allocator.free(i);
    try testing.expectEqualSlices(i32, &[_]i32{ 10, 1, 5, 7, 8 }, i);
}