c++ - 如何实现双向链表？

Question

我们在课堂上学习了如何实现单链表。我们的教授有点提到我们做双向链表，但显然它很容易，以至于他真的没有详细解释如何做。我真的很擅长使用单链表，但是有人可以告诉我如何制作双链表吗？

Answer 1

如果你已经对单链表有了一个明确的定义，那么双链表就很简单了。

在你可能有类似的东西之前

struct link{
  struct link* next; //a pointer to the node that comes next
  int value;
}

这将需要更改为

struct link{
  struct link* next; //a pointer to the node that comes next
  struct link* prev; //a pointer to the node that comes before
  int value;
}

现在，您基本上可以通过在遍历列表时使用 previous 而不是 next 来反向执行操作。

请记住，在添加或删除时，您需要小心“簿记”，以使事情指向正确的事情。

我总是告诉学生在编写函数时画出链表中添加和删除的每一步。并始终确保您通过某处的指针保留对绘图中所有内容的引用，直到将其删除。

Answer 2

@kratenko 有一个很好的观点，但为了便于访问，这里是一个简短的描述。

您的单链表具有向一个方向移动的指针：

头部*-> |数据| -> |数据| -> |数据| -> 空

对于双向链表，在两个方向上实现一个单向链表：

头* <-> |数据| <-> |数据| <-> |数据| <-> 尾巴*

其中 HEAD* 和 TAIL* 都是具有指向它们的 node* 成员的节点（在 DoublyLinkedList 类中）。

Answer 3

您应该在头部和尾部添加“虚拟节点”。这将简化您的添加和删除方法（您不必考虑添加和删除头部和尾部，您只会认为“中间情况”）。

在结束程序之前，不要忘记用 NULL 替换您的虚拟节点。