链表的类型 - 单链表、双链表和循环链表

提示

1. 单向链表：每个节点包含数据和一个指向下一个节点的指针，形成一条单向链。
2. 双向链表：与单向链表相比，增加了指向前一个节点的指针，允许双向遍历。
3. 循环链表：最后一个节点指向第一个节点，形成一个循环，可以是单向或双向的。

在学习链表的类型之前，请确保您已经了解了链表数据结构。

常见的链表类型有三种：

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

单向链表

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

节点表示为：

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

可以创建一个三个成员的单向链表：

/* 初始化节点 */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* 分配内存 */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* 赋值数据 */
one->data = 1;
two->data = 2;
three->data = 3;

/* 连接节点 */
one->next = two;
two->next = three;
three->next = NULL;

/* 把第一个节点的地址保存在 head 中 */
head = one;

双向链表

在双向链表中，我们添加了一个指向前一个节点的指针。因此，我们可以向前或向后遍历。

节点表示为：

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

可以创建一个三个成员的双向链表：

/* 初始化节点 */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* 分配内存 */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* 赋值数据 */
one->data = 1;
two->data = 2;
three->data = 3;

/* 连接节点 */
one->next = two;
one->prev = NULL;

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

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

/* 把第一个节点的地址保存在 head 中 */
head = one;

循环链表

循环链表是链表的一种变体，其中最后一个元素链接到第一个元素。这形成了一个循环。

循环链表可以是单向的也可以是双向的。

• 对于单向链表，最后一个项的 next 指针指向第一个项
• 在双向链表中，第一个项的 prev 指针也指向最后一个项。

可以创建一个三个成员的单向循环链表：

/* 初始化节点 */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* 分配内存 */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* 赋值数据 */
one->data = 1;
two->data = 2;
three->data = 3;

/* 连接节点 */
one->next = two;
two->next = three;
three->next = one;

/* 把第一个节点的地址保存在 head 中 */
head = one;