如何实现双向链表？

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来反向执行操作.

请记住,在添加或删除时,您需要小心处理"簿记"以确保正确的事情.

我总是告诉学生在编写函数时绘制添加和删除链表的每一步.并始终确保通过指针在某处保留对绘图中所有内容的引用,直到删除它为止.