双链接列表的头(开始)指针以前是否指向尾(最后)节点？

Question

我有一个问题，在循环双链表的情况下，双链表的头指针在逻辑上也指向链表尾节点的下一个指针，尾的下一个指针也指向头的前一个指针。

请回答我这个问题，我有点困惑。

Answer 1

那得看情况。

它是一个圆形列表还是线性列表？

如果它是一个循环列表，那么就没有"head“或"tail”，因为每个元素的next和prev指针都将被设置。您可以在任何地方开始遍历列表，并且必须记住从哪里开始，以便知道何时停止。

如果它是一个线性列表，那么head元素的prev指针将是null，而尾巴元素的next指针将是null。您可以使用这些信息来知道何时停止。

Answer 2

假设您有一个循环双链接列表，其中三个节点位于位置1、2和3：

[1] next->2 prev->3
[2] next->3 prev->1
[3] next->1 prev->2

在某种意义上，循环双链接列表中没有“头”和“尾”。不过，外部将有一个指针作为入口点来访问列表，如head->1，这将与3:next->1相同。

所以头像指的是“尾巴”

后面的尾巴指向“头”。

Answer 3

我使用了这样的循环双链接列表：

typedef struct List {
  struct List *next;
  struct List *prev;
  void *data;
} List;

我决定将列表的头定义为具有数据== NULL的列表。因此，空列表是next和prev指向自身，而data ==为空的列表。然后，你可以随意插入头部之前或之后。你可以从头->下一个开始迭代列表，直到你再次撞到头。

有趣的是:你可以有多个脑袋。没有什么可以阻止您插入带有数据== NULL的第二个列表。现在有两种方法可以对列表进行迭代:可以迭代直到到达下一个头(数据==空值)，或者跳过头，然后继续执行，直到再次命中原始头。