python - Python中的链接矩阵实现？

Question

我知道在链表中有一个头节点和一个尾节点。好吧，对于我的数据结构分配，我们假设创建一个链接矩阵，其中引用了北、南、东和西节点。我不知道如何实现这一点。困扰我的一个持久问题是头节点和尾节点。用户输入行数和列数。我应该在每行的开头有多个头节点，在每行的末尾有多个尾节点吗？如果是这样，我应该将多个头/尾节点存储在一个列表中吗？

谢谢你。

Answer 1

这实际上取决于您想要/需要有效支持的选项。

例如，只有一个头指针的单链表可以是一个堆栈（在头插入和删除）。如果添加尾指针，则可以在任一端插入，但只能在头部（堆栈或队列）移除。双向链表可以支持在任一端（deque）插入或删除。如果您尝试实现您的数据结构不是为您设计的操作，则会导致 O(N) 损失。

因此，我将从指向 (0,0) 元素的单个指针开始，然后开始处理您的讲师要求的操作。你可能会发现你需要额外的指针，你可能不需要。我的猜测是你会用一个头指针没问题。

Answer 2

解释这一点的方法不止一种，但一种选择是：

在左上角有一个“头”节点，在右下角有一个“尾”节点。然后会有 row-head、row-tail、column-head 和 column-tail 节点，但这些节点都可以从整体 head 和 tail 访问，所以你不需要跟踪它们，它们是已经是链接矩阵的一部分，因此它们不需要成为单独链接列表的一部分。

（当然，构建零的 RxC 矩阵的函数可能具有表示当前行的头/尾的局部变量，但这不是问题。）