链表是C语言的魅力:5个你必须知道的链表的类型，格式，用法

点击蓝字，关注我们

往期回顾

从零开始学习C语言的结构体，带你掌握结构体的概念，类型，格式，用法和用途（二）

从零开始学习C语言的结构体，带你掌握结构体的概念，类型，格式，用法和用途（一）

指针是C语言的灵魂：一篇文章带你掌握指针的基本概念和用法

01

本节重点

C语言链表

链表是一种非常重要的数据结构，它可以动态地分配内存空间，实现高效的数据操作。链表由一系列的节点构成，每个节点包含了数据和一个指向下一个节点的指针。在本文中，我们将介绍链表的概念，链表的类型，链表的格式，链表的用法和用途，以及一个简单的链表的实现和应用的例子。

链表的概念

链表是一种线性表，但是它不像数组那样在内存中连续存储，而是通过指针将一组零散的内存块串联起来。每个内存块称为一个节点，每个节点包含两部分：数据和指针。数据是节点存储的信息，可以是任意类型的数据，如整数、字符、结构体等。指针是节点的链接信息，它指向下一个节点的地址，从而形成一个链式的结构。

链表的类型

根据节点的指针域的个数和指向的方向，链表可以分为以下几种类型：

- 单向链表：每个节点只有一个指针域，指向下一个节点，链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针域为NULL，表示链表的结束。

- 双向链表：每个节点有两个指针域，一个指向前一个节点，一个指向后一个节点，链表的第一个节点的前驱指针和最后一个节点的后继指针都为NULL，表示链表的边界。

- 循环链表：每个节点只有一个指针域，指向下一个节点，但是尾节点的指针域不为NULL，而是指向头节点，形成一个环状的结构。

- 双向循环链表：每个节点有两个指针域，一个指向前一个节点，一个指向后一个节点，但是头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，形成一个双向的环状的结构。

链表的格式

在C语言中，通常使用结构体来表示链表的节点，结构体中包含数据域和指针域，指针域的类型为结构体指针，用来指向同类型的结构体。例如，一个单向链表的节点的结构体定义如下：

struct ListNode 
{
    int data; // 数据域，用于存储数据
    struct ListNode* next; // 指针域，用于指向下一个节点
};

为了方便操作，我们可以使用typedef关键字为结构体类型起一个别名，例如：

typedef struct ListNode ListNode;

这样，我们就可以用ListNode来代替struct ListNode，简化代码的书写。另外，我们还需要一个头指针，用来指向链表的第一个节点，例如：

ListNode* head = NULL; // 头指针，初始为空

链表的用法主要包括以下几个方面：

- 创建链表：

创建链表的过程就是创建节点并将它们链接起来的过程，可以使用动态内存分配函数，如malloc或calloc，为每个节点分配内存空间，并初始化数据和指针，然后将节点按照一定的顺序连接起来，形成链表。创建链表的方法有多种，如头插法，尾插法，有序插入法等。

- 遍历链表：

遍历链表的过程就是访问链表中的每个节点的过程，可以使用一个循环结构，如while或for，从头指针开始，依次访问每个节点的数据和指针，直到遇到NULL为止。遍历链表的目的可以是输出链表的内容，查找链表中的某个元素，统计链表的长度等。

- 插入节点：

插入节点的过程就是在链表中的某个位置添加一个新的节点的过程，可以使用一个临时指针，如p，先找到要插入的位置，然后将新节点的指针域指向p的下一个节点，再将p的指针域指向新节点，从而完成插入操作。插入节点的位置可以是链表的头部，尾部，中间，或者按照一定的规则，如升序或降序。

- 删除节点：

删除节点的过程就是在链表中删除某个节点的过程，可以使用两个临时指针，如p和q，先找到要删除的节点，然后将q指向p的下一个节点，再将p的前一个节点的指针域指向q，从而断开p与链表的连接，最后释放p所占用的内存空间，完成删除操作。删除节点的条件可以是节点的数据，位置，或者其他特征。

- 销毁链表：

销毁链表的过程就是释放链表中所有节点占用的内存空间的过程，可以使用一个循环结构，如while或for，从头指针开始，依次释放每个节点的内存空间，直到遇到NULL为止，最后将头指针置为NULL，表示链表已经销毁。销毁链表的目的是防止内存泄漏，提高程序的性能。

点赞加关注，学习不迷路

微信公众号｜工控小新

EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中

#记录我的2024#