链表的类型 —— 单向链表、双向链表和环形链表

在学习链表的类型之前，确保你了解链表数据结构

有三种常见的链表类型

1. 单向链表
2. 双向链表
3. 环形链表

---

单向链表

这是最一般的链表类型。每个节点包含一个数据和一个指向下一个节点的指针

节点表示为：

struct node {
    int data;
    struct node *next;
}

一个包含三个节点的单链表可以按如下方式创建：

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;

/* Save address of first node in head */
head = one;

---

双向链表

在双向链表中，我们会添加一个指向前一个节点的指针。这样一来，我们就可以朝任意方向遍历：向前或向后。

节点表示为：

struct node {
    int data;
    struct node *next;
    struct node *prev;
}

一个包含三个节点的双向链表可以按如下方式创建：

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
one->prev = NULL;

two->next = three;
two->prev = one;

three->next = NULL;
three->prev = two;

/* Save address of first node in head */
head = one;

欲知更多，可以访问双向链表及操作

---

环形链表

环形链表是链表的一种变体，在环形链表中，最后一个元素与第一个元素相连接。这就形成了一个循环回路。

环形链表既可以是单向链表，也可以是双向链表。

• 对于单向链表，最后一个节点的下一个指针指向第一个节点。
• 对于双向链表，第一个节点的前一个指针也指向最后一个节点。

一个包含三个节点的循环单链表可以按如下方式创建：

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = one;

/* Save address of first node in head */
head = one;

预知更多，可以访问环形链表及操作