跳转到内容

std.SinglyLinkedList

标准库Zig 0.17.0官方原文
源码std/SinglyLinkedList.zig

第 1 行

单链表由一个向前指针作为表头。元素采用单向链接,以尽量减少空间和指针操作开销,代价是删除任意元素需要 O(n)。可在已有元素之后或链表头部插入新元素。

单链表只能向前遍历。

以下条件下适合使用单链表:

  • 可以预分配元素,或者要求插入操作不可失败。
  • 可以将元素以侵入方式与其他数据一同分配。
  • 元素类型一致。

字段

first: ?*Node = null

std.SinglyLinkedList.assert

别名

第 16 行

别名目标 std.debug.assert

std.SinglyLinkedList.debug

别名

第 15 行

别名目标 std.debug

std.SinglyLinkedList.len

函数

第 113 行

遍历所有节点并返回数量。

此操作为 O(N)。可考虑单独跟踪长度, 而非每次计算。

pub fn len(list: SinglyLinkedList) usize

参数

std.SinglyLinkedList.Node

容器

第 25 行

此结构体仅包含 next 指针,没有任何数据载荷。 预期以侵入式方式嵌入其他数据结构, 并通过 @fieldParentPtr 访问数据。

字段

next: ?*Node = null

std.SinglyLinkedList.Node.countChildren

函数

第 57 行

逐个遍历后继节点,返回除起始节点外 的所有节点数。

此操作为 O(N)。可考虑改用其他 数据结构,避免调用此函数。

pub fn countChildren(node: *const Node) usize

参数

node: *const Node

std.SinglyLinkedList.Node.findLast

函数

第 45 行

从此节点开始遍历单向链表,直到找到 最后一个节点。

此操作为 O(N)。可考虑改用其他 数据结构,避免调用此函数。

pub fn findLast(node: *Node) *Node

参数

node: *Node

std.SinglyLinkedList.Node.insertAfter

函数

第 28 行

pub fn insertAfter(node: *Node, new_node: *Node) void

参数

node: *Node
new_node: *Node

std.SinglyLinkedList.Node.removeNext

函数

第 34 行

移除给定节点之后的节点,并返回它。

pub fn removeNext(node: *Node) ?*Node

参数

node: *Node

std.SinglyLinkedList.Node.reverse

函数

第 70 行

从此节点开始,原地反转列表。

此操作为 O(N)。可考虑使用其他 数据结构,避免调用此函数。

pub fn reverse(indirect: *?*Node) void

参数

indirect: *?*Node

std.SinglyLinkedList.popFirst

函数

第 103 行

移除并返回链表中的首个节点。

pub fn popFirst(list: *SinglyLinkedList) ?*Node

参数

std.SinglyLinkedList.prepend

函数

第 83 行

pub fn prepend(list: *SinglyLinkedList, new_node: *Node) void

参数

list: *SinglyLinkedList
new_node: *Node

std.SinglyLinkedList.remove

函数

第 90 行

从列表移除 node。 断言 node 位于列表中。

pub fn remove(list: *SinglyLinkedList, node: *const Node) void

参数

list: *SinglyLinkedList
node: *const Node

std.SinglyLinkedList.SinglyLinkedList

别名

第 18 行

别名目标 std.SinglyLinkedList

std.SinglyLinkedList.std

别名

第 14 行

别名目标 std

std.SinglyLinkedList.testing

别名

第 17 行

别名目标 std.testing

源码

std/SinglyLinkedList.zig

//! 单链表由一个向前指针作为表头。元素采用单向链接,以尽量减少空间和指针操作开销,代价是删除任意元素需要 O(n)。可在已有元素之后或链表头部插入新元素。
//!
//! 单链表只能向前遍历。
//!
//! 以下条件下适合使用单链表:
//! * 可以预分配元素,或者要求插入操作不可失败。
//! * 可以将元素以侵入方式与其他数据一同分配。
//! * 元素类型一致。
//!
//!
//!
//!

const std = @import("std.zig");
const debug = std.debug;
const assert = debug.assert;
const testing = std.testing;
const SinglyLinkedList = @This();

first: ?*Node = null,

/// 此结构体仅包含 next 指针,没有任何数据载荷。
/// 预期以侵入式方式嵌入其他数据结构,
/// 并通过 `@fieldParentPtr` 访问数据。
pub const Node = struct {
    next: ?*Node = null,

    pub fn insertAfter(node: *Node, new_node: *Node) void {
        new_node.next = node.next;
        node.next = new_node;
    }

    /// 移除给定节点之后的节点,并返回它。
    pub fn removeNext(node: *Node) ?*Node {
        const next_node = node.next orelse return null;
        node.next = next_node.next;
        return next_node;
    }

    /// 从此节点开始遍历单向链表,直到找到
    /// 最后一个节点。
    ///
    /// 此操作为 O(N)。可考虑改用其他
    /// 数据结构,避免调用此函数。
    pub fn findLast(node: *Node) *Node {
        var it = node;
        while (true) {
            it = it.next orelse return it;
        }
    }

    /// 逐个遍历后继节点,返回除起始节点外
    /// 的所有节点数。
    ///
    /// 此操作为 O(N)。可考虑改用其他
    /// 数据结构,避免调用此函数。
    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;
    }

    /// 从此节点开始,原地反转列表。
    ///
    /// 此操作为 O(N)。可考虑使用其他
    /// 数据结构,避免调用此函数。
    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;
        }
    }
};

pub fn prepend(list: *SinglyLinkedList, new_node: *Node) void {
    new_node.next = list.first;
    list.first = new_node;
}

/// 从列表移除 `node`。
/// 断言 `node` 位于列表中。
pub fn remove(list: *SinglyLinkedList, node: *const Node) void {
    if (list.first == node) {
        list.first = node.next;
    } else {
        var current_elm = list.first.?;
        while (current_elm.next != node) {
            current_elm = current_elm.next.?;
        }
        current_elm.next = node.next;
    }
}

/// 移除并返回链表中的首个节点。
pub fn popFirst(list: *SinglyLinkedList) ?*Node {
    const first = list.first orelse return null;
    list.first = first.next;
    return first;
}

/// 遍历所有节点并返回数量。
///
/// 此操作为 O(N)。可考虑单独跟踪长度,
/// 而非每次计算。
pub fn len(list: SinglyLinkedList) usize {
    if (list.first) |n| {
        return 1 + n.countChildren();
    } else {
        return 0;
    }
}

test "basics" {
    const L = struct {
        data: u32,
        node: SinglyLinkedList.Node = .{},
    };
    var list: SinglyLinkedList = .{};

    try testing.expect(list.len() == 0);

    var one: L = .{ .data = 1 };
    var two: L = .{ .data = 2 };
    var three: L = .{ .data = 3 };
    var four: L = .{ .data = 4 };
    var five: L = .{ .data = 5 };

    list.prepend(&two.node); // {2}
    two.node.insertAfter(&five.node); // {2, 5}
    list.prepend(&one.node); // {1, 2, 5}
    two.node.insertAfter(&three.node); // {1, 2, 3, 5}
    three.node.insertAfter(&four.node); // {1, 2, 3, 4, 5}

    try testing.expect(list.len() == 5);

    // 向前遍历。
    {
        var it = list.first;
        var index: u32 = 1;
        while (it) |node| : (it = node.next) {
            const l: *L = @fieldParentPtr("node", node);
            try testing.expect(l.data == index);
            index += 1;
        }
    }

    _ = list.popFirst(); // {2, 3, 4, 5}
    _ = list.remove(&five.node); // {2, 3, 4}
    _ = two.node.removeNext(); // {2, 4}

    try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?)).data == 2);
    try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?.next.?)).data == 4);
    try testing.expect(list.first.?.next.?.next == null);

    SinglyLinkedList.Node.reverse(&list.first);

    try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?)).data == 4);
    try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?.next.?)).data == 2);
    try testing.expect(list.first.?.next.?.next == null);
}