链表类型 （数据结构）

数据结构中共有四种类型的链表，下面将进行讨论。

• 单向链表
• 双向链表
• 循环链表
• 双向循环链表

1) 单向链表

这是程序中最常用的链表。如果我们谈论链表，那就是指单向链表。单向链表是一种数据结构，它包含两部分：一部分是数据域，另一部分是地址域，它包含下一个或后继节点的地址。节点中的地址域也称为 **指针**。

假设我们有三个节点，它们的地址分别是 100、200 和 300。下面图示了将三个节点表示为链表的样子。

从上图可以看出，有三个不同的节点，地址分别为 100、200 和 300。第一个节点包含下一个节点的地址，即 200；第二个节点包含最后一个节点的地址，即 300；第三个节点在其地址域中包含 NULL 值，因为它不指向任何节点。保存初始节点地址的指针称为 **头指针**。

上图所示的链表称为单向链表，因为它只有一个链接。在此列表中，只能向前遍历；我们无法向后遍历，因为它在列表中只有一个链接。

单向链表中节点的表示

在上图表示中，我们定义了一个名为 **node** 的用户自定义结构，它包含两个成员：第一个是整型数据，另一个是节点类型的指针（next）。

要了解更多关于单向链表的信息，请点击 单向链表

2) 双向链表

顾名思义，双向链表包含两个指针。我们可以将双向链表定义为一种线性数据结构，它包含三个部分：数据域和另外两个地址域。换句话说，双向链表是一个在单个节点中包含三个部分的列表，包括一个数据域，指向其前一个节点的指针，以及指向下一个节点的指针。

假设我们有三个节点，它们的地址分别是 100、200 和 300。下面显示了在双向链表中表示这些节点的图。

从上图可以看出，双向链表中的节点有两个地址域：一个域存储 **下一个节点的地址**，而节点的另一个域存储 **前一个节点的地址**。双向链表中的初始节点在地址域中具有 **NULL** 值，该值提供了前一个节点的地址。

双向链表中节点的表示

在上图表示中，我们定义了一个名为 **a node** 的用户自定义结构，它包含三个成员：一个是整型 **data**，另外两个是节点类型的指针，即 **next 和 prev**。**next 指针** 变量存储下一个节点的地址，**prev 指针** 存储前一个节点的地址。这两个指针（**next 和 prev**）的类型都是 **struct node**，因为这两个指针都存储着 **struct node** 类型节点的地址。

要了解更多关于双向链表的信息，请点击 双向链表

3) 循环链表

循环链表是单向链表的一种变体。**单向链表** 和 **循环链表** 之间的唯一区别在于，单向链表中的最后一个节点不指向任何节点，因此其链接部分包含 NULL 值。另一方面，循环链表是一个列表，其中最后一个节点连接到第一个节点，因此最后一个节点的链接部分包含第一个节点的地址。循环链表没有起始节点和结束节点。我们可以向任何方向遍历，即向前或向后遍历。下面显示了循环链表的图示表示。

循环链表是元素的序列，其中每个节点都有一个指向下一个节点的链接，最后一个节点具有指向第一个节点的链接。循环链表的表示将类似于单向链表，如下所示。

要了解更多关于循环链表的信息，请点击 循环链表

4) 双向循环链表

双向循环链表具有 **循环链表** 和 **双向链表** 的所有特性。

上图显示了双向循环链表的表示，其中最后一个节点连接到第一个节点，从而形成一个圆。它也是双向链表，因为每个节点也保存了前一个节点的地址。双向链表和双向循环链表之间的主要区别在于，双向循环链表的前向域不包含 NULL 值。由于双向循环链表包含三个部分，即两个地址域和一个数据域，因此其表示与双向链表相似。

要了解更多关于双向循环链表的信息，请点击 双向循环链表