单链表由一个向前指针作为表头。元素采用单向链接,以尽量减少空间和指针操作开销,代价是删除任意元素需要 O(n)。可在已有元素之后或链表头部插入新元素。
单链表只能向前遍历。
以下条件下适合使用单链表:
- 可以预分配元素,或者要求插入操作不可失败。
- 可以将元素以侵入方式与其他数据一同分配。
- 元素类型一致。
字段
first: ?*Node = null
std.SinglyLinkedList.assert
别名
别名目标 std.debug.assert
std.SinglyLinkedList.debug
别名
别名目标 std.debug
std.SinglyLinkedList.len
函数
遍历所有节点并返回数量。
此操作为 O(N)。可考虑单独跟踪长度, 而非每次计算。
pub fn len(list: SinglyLinkedList) usize
参数
list: SinglyLinkedList
std.SinglyLinkedList.Node
容器
此结构体仅包含 next 指针,没有任何数据载荷。
预期以侵入式方式嵌入其他数据结构,
并通过 @fieldParentPtr 访问数据。
字段
next: ?*Node = null
std.SinglyLinkedList.Node.countChildren
函数
逐个遍历后继节点,返回除起始节点外 的所有节点数。
此操作为 O(N)。可考虑改用其他 数据结构,避免调用此函数。
pub fn countChildren(node: *const Node) usize
参数
node: *const Node
std.SinglyLinkedList.Node.findLast
函数
从此节点开始遍历单向链表,直到找到 最后一个节点。
此操作为 O(N)。可考虑改用其他 数据结构,避免调用此函数。
pub fn findLast(node: *Node) *Node
参数
node: *Node
std.SinglyLinkedList.Node.insertAfter
函数
pub fn insertAfter(node: *Node, new_node: *Node) void
参数
std.SinglyLinkedList.Node.removeNext
函数
移除给定节点之后的节点,并返回它。
pub fn removeNext(node: *Node) ?*Node
参数
node: *Node
std.SinglyLinkedList.Node.reverse
函数
从此节点开始,原地反转列表。
此操作为 O(N)。可考虑使用其他 数据结构,避免调用此函数。
pub fn reverse(indirect: *?*Node) void
参数
indirect: *?*Node
std.SinglyLinkedList.popFirst
函数
移除并返回链表中的首个节点。
pub fn popFirst(list: *SinglyLinkedList) ?*Node
参数
list: *SinglyLinkedList
std.SinglyLinkedList.prepend
函数
pub fn prepend(list: *SinglyLinkedList, new_node: *Node) void
参数
list: *SinglyLinkedList
new_node: *Node
std.SinglyLinkedList.remove
函数
从列表移除 node。
断言 node 位于列表中。
pub fn remove(list: *SinglyLinkedList, node: *const Node) void
参数
list: *SinglyLinkedList
node: *const Node
std.SinglyLinkedList.SinglyLinkedList
别名
别名目标 std.SinglyLinkedList
std.SinglyLinkedList.std
别名
别名目标 std
std.SinglyLinkedList.testing
别名
别名目标 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);
}