Day 56: std.doubly_linked_list模块：双向链表

1. 引言：动态节点

与ArrayList这样的连续内存数据结构不同，链表（Linked List）是由一系列分散在内存中的节点组成的。每个节点包含数据以及一个或多个指向其他节点的指针。双向链表（Doubly Linked List）的每个节点都有两个指针：一个指向前一个节点（prev），一个指向后一个节点（next）。

这使得在列表的任意位置进行插入和删除操作都非常高效（O(1)），前提是你已经有了一个指向该位置节点的指针。然而，访问一个特定索引的元素则需要O(n)时间，因为必须从头或尾开始遍历。std.DoublyLinkedList是Zig标准库对此数据结构的实现。

2. 定义：`DoublyLinkedList(T)`

std.DoublyLinkedList(T)是一个泛型类型，其中T是你想要存储的数据类型。要使用它，你的类型T必须嵌入一个std.DoublyLinkedList(T).Node字段，该字段包含了prev和next指针。

const std = @import("std");

const MyData = struct {
    data: i32,
    // 必须嵌入Node字段
    node: std.DoublyLinkedList(MyData).Node = .{}
};

// 初始化一个空的双向链表
var list = std.DoublyLinkedList(MyData){};

这种设计意味着节点本身（MyData）负责存储链接信息，而不是由链表来包装它。这避免了额外的内存分配。

3. 操作：`append`, `prepend`, `remove`

双向链表提供了一系列在两端或中间操作节点的方法。

append(node: *T): 将一个节点添加到列表的末尾。
prepend(node: *T): 将一个节点添加到列表的开头。
remove(node: *T): 从列表中移除一个节点。
popFirst(): 移除并返回第一个节点。
popLast(): 移除并返回最后一个节点。

const std = @import("std");

// ... MyData定义 ...

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

    var list = std.DoublyLinkedList(MyData){};

    var node1 = try allocator.create(MyData);
    node1.* = .{ .data = 10 };

    var node2 = try allocator.create(MyData);
    node2.* = .{ .data = 20 };

    list.append(node1);
    list.prepend(node2);

    // 移除node1
    list.remove(node1);
    allocator.destroy(node1);

    // ... 必须手动释放所有剩余节点的内存
    while (list.popFirst()) |node| {
        std.debug.print("Destroying node with data: {d}\n", .{node.data});
        allocator.destroy(node);
    }
}

4. 迭代：向前和向后

双向链表最强大的特性之一是能够双向遍历。

first(): 返回指向第一个节点的指针，或null。
last(): 返回指向最后一个节点的指针，或null。
next(node: *T): 返回给定节点的下一个节点。
prev(node: *T): 返回给定节点的前一个节点。

// 正向迭代
var current = list.first();
while (current) |node| {
    std.debug.print("Data: {d}\n", .{node.data});
    current = list.next(node);
}

// 反向迭代
var current_rev = list.last();
while (current_rev) |node| {
    std.debug.print("Data (reversed): {d}\n", .{node.data});
    current_rev = list.prev(node);
}

5. 示例：LRU缓存中的节点移动

在LRU（最近最少使用）缓存中，双向链表用于维护项目的访问顺序。当一个项目被访问时，它会被移动到链表的头部。DoublyLinkedList的remove和prepend操作使得这个过程非常高效。

fn markAsRecentlyUsed(list: *std.DoublyLinkedList(MyData), node: *MyData) {
    // 从当前位置移除
    list.remove(node);
    // 添加到头部
    list.prepend(node);
}

6. 实践练习：浏览器历史记录

使用DoublyLinkedList来模拟一个简化的浏览器历史记录。你需要实现以下功能：

visit(url: []const u8): 访问一个新页面，将其添加到历史记录的“当前”位置。
goBack(): 返回到前一个页面。
goForward(): 前进到下一个页面。

7. 常见问题

为什么需要手动管理内存？ 这是Zig“显式就是更好”哲学的一部分。通过将内存管理责任交给用户，DoublyLinkedList变得更加灵活。它可以与任何分配器策略（或无分配器，用于栈上节点）一起使用。
如何处理空列表？ 对空列表调用popFirst或popLast会返回null，这是安全的。在迭代之前，总是检查first()或last()的返回值是否为null。
与单向链表（Singly Linked List）的比较 双向链表的主要优势是能够高效地进行反向遍历和在给定节点前插入。其代价是每个节点需要额外存储一个prev指针，占用了更多内存。

8. 总结：灵活的节点管理

std.DoublyLinkedList为需要频繁在列表中间进行插入、删除和重新排序操作的场景提供了一个强大而灵活的工具。虽然它要求用户手动管理内存，但这种设计提供了极大的灵活性，并避免了隐藏的性能开销。它是实现LRU缓存、任务队列和许多其他高级数据结构的关键组成部分。