双链表有一对分别指向表头与表尾的指针。每个元素都具有指向前一个和后一个元素的指针,因此可向前或向后遍历。 某些在单链表中需要线性 O(n) 时间的操作,在双链表中无需遍历,只需常数 O(1) 时间:
- 删除元素。
- 在已有元素之前插入新元素。
- 在链表尾部压入或弹出元素。
字段
std.DoublyLinkedList.append
函数
在列表末尾插入新节点。
参数: new_node:指向待插入新节点的指针。
pub fn append(list: *DoublyLinkedList, new_node: *Node) void
参数
list: *DoublyLinkedList
new_node: *Node
std.DoublyLinkedList.assert
别名
别名目标 std.debug.assert
std.DoublyLinkedList.concatByMoving
函数
将 list2 拼接到 list1 末尾,并移除 list2 中的所有条目。
参数: list1:接收拼接内容的列表。 list2:要拼接过去的列表。
pub fn concatByMoving(list1: *DoublyLinkedList, list2: *DoublyLinkedList) void
参数
list1: *DoublyLinkedList
list2: *DoublyLinkedList
std.DoublyLinkedList.debug
别名
别名目标 std.debug
std.DoublyLinkedList.DoublyLinkedList
别名
别名目标 std.DoublyLinkedList
std.DoublyLinkedList.insertAfter
函数
pub fn insertAfter(list: *DoublyLinkedList, existing_node: *Node, new_node: *Node) void
参数
std.DoublyLinkedList.insertBefore
函数
pub fn insertBefore(list: *DoublyLinkedList, existing_node: *Node, new_node: *Node) void
参数
std.DoublyLinkedList.len
函数
遍历所有节点并返回数量。
此操作为 O(N)。可考虑单独跟踪长度, 而非每次计算。
pub fn len(list: DoublyLinkedList) usize
参数
list: DoublyLinkedList
std.DoublyLinkedList.Node
容器
此结构体仅包含 prev 和 next 指针,不包含任何数据
载荷。预期用途是将其侵入式嵌入其他数据
结构,再通过 @fieldParentPtr 访问数据。
字段
std.DoublyLinkedList.pop
别名
已弃用,请改用 popLast
std.DoublyLinkedList.popFirst
函数
移除并返回指向列表中第一个节点的指针。
pub fn popFirst(list: *DoublyLinkedList) ?*Node
参数
list: *DoublyLinkedList
std.DoublyLinkedList.popLast
函数
移除列表最后一个节点,并返回指向它的指针。
pub fn popLast(list: *DoublyLinkedList) ?*Node
参数
list: *DoublyLinkedList
std.DoublyLinkedList.prepend
函数
在列表开头插入新节点。
参数: new_node:指向待插入新节点的指针。
pub fn prepend(list: *DoublyLinkedList, new_node: *Node) void
参数
list: *DoublyLinkedList
new_node: *Node
std.DoublyLinkedList.remove
函数
从列表中移除节点。 假定节点位于列表中。
参数: node:指向待移除节点的指针。
pub fn remove(list: *DoublyLinkedList, node: *const Node) void
参数
list: *DoublyLinkedList
node: *const Node
std.DoublyLinkedList.std
别名
别名目标 std
std.DoublyLinkedList.testing
别名
别名目标 std.testing
源码
std/DoublyLinkedList.zig
//! 双链表有一对分别指向表头与表尾的指针。每个元素都具有指向前一个和后一个元素的指针,因此可向前或向后遍历。
//! 某些在单链表中需要线性 O(n) 时间的操作,在双链表中无需遍历,只需常数 O(1) 时间:
//!
//! * 删除元素。
//! * 在已有元素之前插入新元素。
//! * 在链表尾部压入或弹出元素。
//!
//!
//!
//!
const std = @import("std.zig");
const debug = std.debug;
const assert = debug.assert;
const testing = std.testing;
const DoublyLinkedList = @This();
first: ?*Node = null,
last: ?*Node = null,
/// 此结构体仅包含 prev 和 next 指针,不包含任何数据
/// 载荷。预期用途是将其侵入式嵌入其他数据
/// 结构,再通过 `@fieldParentPtr` 访问数据。
pub const Node = struct {
prev: ?*Node = null,
next: ?*Node = null,
};
pub fn insertAfter(list: *DoublyLinkedList, existing_node: *Node, new_node: *Node) void {
new_node.prev = existing_node;
if (existing_node.next) |next_node| {
// 中间节点。
new_node.next = next_node;
next_node.prev = new_node;
} else {
// 列表中的最后一个元素。
new_node.next = null;
list.last = new_node;
}
existing_node.next = new_node;
}
pub fn insertBefore(list: *DoublyLinkedList, existing_node: *Node, new_node: *Node) void {
new_node.next = existing_node;
if (existing_node.prev) |prev_node| {
// 中间节点。
new_node.prev = prev_node;
prev_node.next = new_node;
} else {
// 列表的第一个元素。
new_node.prev = null;
list.first = new_node;
}
existing_node.prev = new_node;
}
/// 将 list2 拼接到 list1 末尾,并移除 list2 中的所有条目。
///
/// 参数:
/// list1:接收拼接内容的列表。
/// list2:要拼接过去的列表。
pub fn concatByMoving(list1: *DoublyLinkedList, list2: *DoublyLinkedList) void {
const l2_first = list2.first orelse return;
if (list1.last) |l1_last| {
l1_last.next = list2.first;
l2_first.prev = list1.last;
} else {
// list1 为空
list1.first = list2.first;
}
list1.last = list2.last;
list2.first = null;
list2.last = null;
}
/// 在列表末尾插入新节点。
///
/// 参数:
/// new_node:指向待插入新节点的指针。
pub fn append(list: *DoublyLinkedList, new_node: *Node) void {
if (list.last) |last| {
// 在末项之后插入。
list.insertAfter(last, new_node);
} else {
// 空列表。
list.prepend(new_node);
}
}
/// 在列表开头插入新节点。
///
/// 参数:
/// new_node:指向待插入新节点的指针。
pub fn prepend(list: *DoublyLinkedList, new_node: *Node) void {
if (list.first) |first| {
// 在首项之前插入。
list.insertBefore(first, new_node);
} else {
// 空列表。
list.first = new_node;
list.last = new_node;
new_node.prev = null;
new_node.next = null;
}
}
/// 从列表中移除节点。
/// 假定节点位于列表中。
///
/// 参数:
/// node:指向待移除节点的指针。
pub fn remove(list: *DoublyLinkedList, node: *const Node) void {
if (node.prev) |prev_node| {
// 中间节点。
prev_node.next = node.next;
} else {
// 列表的第一个元素。
list.first = node.next;
}
if (node.next) |next_node| {
// 中间节点。
next_node.prev = node.prev;
} else {
// 列表中的最后一个元素。
list.last = node.prev;
}
}
/// 移除列表最后一个节点,并返回指向它的指针。
pub fn popLast(list: *DoublyLinkedList) ?*Node {
const last = list.last orelse return null;
list.remove(last);
return last;
}
/// 已弃用,请改用 `popLast`
pub const pop = popLast;
/// 移除并返回指向列表中第一个节点的指针。
pub fn popFirst(list: *DoublyLinkedList) ?*Node {
const first = list.first orelse return null;
list.remove(first);
return first;
}
/// 遍历所有节点并返回数量。
///
/// 此操作为 O(N)。可考虑单独跟踪长度,
/// 而非每次计算。
pub fn len(list: DoublyLinkedList) usize {
var count: usize = 0;
var it: ?*const Node = list.first;
while (it) |n| : (it = n.next) count += 1;
return count;
}
test "basics" {
const L = struct {
data: u32,
node: DoublyLinkedList.Node = .{},
};
var list: DoublyLinkedList = .{};
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.append(&two.node); // {2}
list.append(&five.node); // {2, 5}
list.prepend(&one.node); // {1, 2, 5}
list.insertBefore(&five.node, &four.node); // {1, 2, 4, 5}
list.insertAfter(&two.node, &three.node); // {1, 2, 3, 4, 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;
}
}
// 向后遍历。
{
var it = list.last;
var index: u32 = 1;
while (it) |node| : (it = node.prev) {
const l: *L = @fieldParentPtr("node", node);
try testing.expect(l.data == (6 - index));
index += 1;
}
}
_ = list.popFirst(); // {2, 3, 4, 5}
_ = list.popLast(); // {2, 3, 4}
list.remove(&three.node); // {2, 4}
// 查看链表的首尾元素
try testing.expect(@as(*L, @fieldParentPtr("node", list.first.?)).data == 2);
try testing.expect(@as(*L, @fieldParentPtr("node", list.last.?)).data == 4);
// 列表长度
try testing.expect(list.len() == 2);
}
test "concatenation" {
const L = struct {
data: u32,
node: DoublyLinkedList.Node = .{},
};
var list1: DoublyLinkedList = .{};
var list2: DoublyLinkedList = .{};
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 };
list1.append(&one.node);
list1.append(&two.node);
list2.append(&three.node);
list2.append(&four.node);
list2.append(&five.node);
list1.concatByMoving(&list2);
try testing.expect(list1.last == &five.node);
try testing.expect(list1.len() == 5);
try testing.expect(list2.first == null);
try testing.expect(list2.last == null);
try testing.expect(list2.len() == 0);
// 向前遍历。
{
var it = list1.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;
}
}
// 向后遍历。
{
var it = list1.last;
var index: u32 = 1;
while (it) |node| : (it = node.prev) {
const l: *L = @fieldParentPtr("node", node);
try testing.expect(l.data == (6 - index));
index += 1;
}
}
// 将它们交换回来,以验证向空列表拼接内容能正确工作。
list2.concatByMoving(&list1);
// 向前遍历。
{
var it = list2.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;
}
}
// 向后遍历。
{
var it = list2.last;
var index: u32 = 1;
while (it) |node| : (it = node.prev) {
const l: *L = @fieldParentPtr("node", node);
try testing.expect(l.data == (6 - index));
index += 1;
}
}
}