跳转到内容

std.DoublyLinkedList

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

第 1 行

双链表有一对分别指向表头与表尾的指针。每个元素都具有指向前一个和后一个元素的指针,因此可向前或向后遍历。 某些在单链表中需要线性 O(n) 时间的操作,在双链表中无需遍历,只需常数 O(1) 时间:

  • 删除元素。
  • 在已有元素之前插入新元素。
  • 在链表尾部压入或弹出元素。

字段

first: ?*Node = null
last: ?*Node = null

std.DoublyLinkedList.append

函数

第 80 行

在列表末尾插入新节点。

参数: new_node:指向待插入新节点的指针。

pub fn append(list: *DoublyLinkedList, new_node: *Node) void

参数

list: *DoublyLinkedList
new_node: *Node

std.DoublyLinkedList.assert

别名

第 14 行

别名目标 std.debug.assert

std.DoublyLinkedList.concatByMoving

函数

第 62 行

将 list2 拼接到 list1 末尾,并移除 list2 中的所有条目。

参数: list1:接收拼接内容的列表。 list2:要拼接过去的列表。

pub fn concatByMoving(list1: *DoublyLinkedList, list2: *DoublyLinkedList) void

参数

std.DoublyLinkedList.debug

别名

第 13 行

别名目标 std.debug

std.DoublyLinkedList.DoublyLinkedList

别名

第 16 行

别名目标 std.DoublyLinkedList

std.DoublyLinkedList.insertAfter

函数

第 29 行

pub fn insertAfter(list: *DoublyLinkedList, existing_node: *Node, new_node: *Node) void

参数

list: *DoublyLinkedList
existing_node: *Node
new_node: *Node

std.DoublyLinkedList.insertBefore

函数

第 43 行

pub fn insertBefore(list: *DoublyLinkedList, existing_node: *Node, new_node: *Node) void

参数

list: *DoublyLinkedList
existing_node: *Node
new_node: *Node

std.DoublyLinkedList.len

函数

第 151 行

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

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

pub fn len(list: DoublyLinkedList) usize

参数

std.DoublyLinkedList.Node

容器

第 24 行

此结构体仅包含 prev 和 next 指针,不包含任何数据 载荷。预期用途是将其侵入式嵌入其他数据 结构,再通过 @fieldParentPtr 访问数据。

字段

prev: ?*Node = null
next: ?*Node = null

std.DoublyLinkedList.pop

别名

第 138 行

已弃用,请改用 popLast

别名目标 std.DoublyLinkedList.popLast

std.DoublyLinkedList.popFirst

函数

第 141 行

移除并返回指向列表中第一个节点的指针。

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

参数

std.DoublyLinkedList.popLast

函数

第 131 行

移除列表最后一个节点,并返回指向它的指针。

pub fn popLast(list: *DoublyLinkedList) ?*Node

参数

std.DoublyLinkedList.prepend

函数

第 94 行

在列表开头插入新节点。

参数: new_node:指向待插入新节点的指针。

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

参数

list: *DoublyLinkedList
new_node: *Node

std.DoublyLinkedList.remove

函数

第 112 行

从列表中移除节点。 假定节点位于列表中。

参数: node:指向待移除节点的指针。

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

参数

list: *DoublyLinkedList
node: *const Node

std.DoublyLinkedList.std

别名

第 12 行

别名目标 std

std.DoublyLinkedList.testing

别名

第 15 行

别名目标 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;
        }
    }
}