本文详细介绍了顺序表和链表两种数据结构。顺序表基于数组实现，通过首地址访问空间。链表分为单向、双向及循环链表，具有插入删除效率高但访问不便的特点。文章涵盖了链表的创建、头插尾插、遍历、删除、查询、销毁等基本操作，以及寻找中间节点、排序、判断环等复杂操作。最后对比了数组与链表在存储空间、元素个数、增删效率及访问便利性上的区别，并提供了相关 C 语言代码示例。
本质等同于数组，通过申请堆区空间存储数据，通过首地址完成对所有空间的访问。
根据元素个数确定数组大小。
概念：由两种区域组成，数据区存放节点的数据，指针区存放相邻节点的地址的一种存储方式。
特点：存储地址不连续。
优点：插入删除效率高，可以利用小空间（空间利用率高）。
缺点：访问元素不方便，增加额外空间（指针区）的开销。
| 链表类型 | 节点结构 |
|---|---|
| 单向链表 | 当前节点数据内容、下一节点地址 |
| 双向链表 | 上一节点地址、当前节点数据内容、下一节点地址 |
| 双向循环链表 | 尾节点地址、头节点数据内容、下一节点地址（循环连接） |
链表操作传参为头节点的地址。
链表可以不设定元素上限，可以嵌套定义，因为指针字节大小固定。
typedef int DataType; //将整型变量重名为 DataType
typedef struct node {
DataType data; //建立数据区 data，存放整型数据
struct node *pNextnode; //建立指针区，存放下一个节点的地址
} LinkNode; //重命名节点为 LinkNode
操作链表需要传入的参数为链表地址（即头节点的地址）。链表操作的函数在头文件定义部分声明为外部函数，在调用头文件时可直接调用。
操作小结：创建、插入（头/尾）、移除、遍历、更改、查询、销毁。
本质：插入（生成）头节点。
实现思路：
LinkNode *CreateEmptyLinkList(void) { //创建链表的本质是创建一个头节点 (空白节点)
//1. 头节点的空间准备
LinkNode *pHeadNode = NULL;
pHeadNode = malloc(sizeof(LinkNode)); //给头节点申请堆区空间，避免函数结束后被释放
if (NULL == pHeadNode) {
perror("fail to malloc");
return NULL;
}
//2. 头节点的内容存放（数据区，指针区）
pHeadNode->pNextnode = NULL; //数据区存放内容随意，但指针区必须为空
return pHeadNode;
}
实现思路：
int HeadInsertNode(LinkNode *pHeadNode, DataType tmpData) { //头插法
//1. 插入节点的空间准备
LinkNode *pInsertNode = NULL;
pInsertNode = malloc(sizeof(LinkNode)); //给插入节点申请一块空间
if (pInsertNode == NULL) {
perror("fail to malloc");
return -1;
}
//2. 插入节点的内容存放（数据区，指针区）
pInsertNode->data = tmpData; //数据区存放插入数值
pInsertNode->pNextnode = pHeadNode->pNextnode; //指针区存放首位有效节点地址
//3. 搭建插入节点和链表的连接关系
pHeadNode->pNextnode = pInsertNode; //头节点的指针区存放插入节点的地址
return 0;
}
实现思路：
int TailInsertNode(LinkNode *pHeadNode, DataType tmpData) { //尾插法
LinkNode *pFlow = NULL;
LinkNode *pInsertNode = NULL;
//1. 插入节点的空间准备
pInsertNode = malloc(sizeof(LinkNode));
if (pInsertNode == NULL) {
perror("fail to malloc");
return -1;
}
//2. 插入节点的内容存放
pInsertNode->data = tmpData;
pInsertNode->pNextnode = NULL;
//3. 流动指针遍历，寻找末尾节点
pFlow = pHeadNode->pNextnode;
while (pFlow->pNextnode != NULL) { //寻找末尾节点的遍历
pFlow = pFlow->pNextnode;
}
//4. 搭建插入节点和链表的连接关系
pFlow->pNextnode = pInsertNode; //原链表末尾节点的指针区存放插入节点的地址
return 0;
}
3 种插入的比较
| 操作 | 生成链表 | 头插入 | 尾插入 |
|---|---|---|---|
| 共同点 | 定义一个指针，申请节点空间（插入必备） | ||
| 数据区 | 不做处理 | 存放插入数值 | 存放插入数值 |
| 地址区 | NULL 地址 | 首位有效节点的地址 | NULL 地址 |
| 插入节点地址的存放 | 函数返回值 | 头节点指针区 | 原末尾节点指针区 |
四步插入法：申请插入空间，寻找插入位置，存放插入内容，建立连接。
遍历方式 1 实现思路：判断指向当前节点的指针是否为 NULL。
while (pNowNode != NULL) {
pNowNode = pNowNode->pNextnode;
}
注：此遍历方式无法找到末尾节点。
遍历方式 2 实现思路：当前节点的指针区为 NULL，则其为末尾节点。
while (pNowNode->pNextnode != NULL) {
pNowNode = pNowNode->pNextnode;
}
| 项目 | 遍历方式 1 | 遍历方式 2 |
|---|---|---|
| 目的 | 实现对每个有效节点数据区内容的遍历 | 遍历至末尾节点 |
| 实现方式 | 指向当前节点的指针是否为 NULL | 当前节点的指针区是否存放 NULL |
| 应用 | 节点数据的显示 | 尾插入法的实现 |
应用：节点数据的显示 实现思路：定义一个流动指针，从链表首个有效节点开始遍历，实现对各有效节点数据区内容的访问，并展示数据区具体内容。
void NodeDataShow(LinkNode *pHeadNode) { //节点数据显示
LinkNode *pFlow = NULL;
pFlow = pHeadNode->pNextnode; //遍历从链表首个有效节点开始
while (pFlow != NULL) { //实现对各有效节点数据区内容的访问
printf("%d ", pFlow->data); //展示节点数据区内容
pFlow = pFlow->pNextnode;
}
printf("\n");
return;
}
实现思路：定义两个指针，流动指针和前节点指针；流动指针用于遍历链表，查询删除节点；前节点指针用于建立删除节点的前后节点的连接关系。
具体过程：
int DeleteNode(LinkNode *pHeadNode, DataType rmData) { //节点删除函数
int cnt = 0;
LinkNode *pPreNode = NULL;
LinkNode *pNowNode = NULL;
pPreNode = pHeadNode;
pNowNode = pHeadNode->pNextnode;
while (pNowNode != NULL) {
if (pNowNode->data == rmData) {
pPreNode->pNextnode = pNowNode->pNextnode;
free(pNowNode);
pNowNode = pPreNode->pNextnode; //避免野指针
cnt++;
} else {
pPreNode = pPreNode->pNextnode;
pNowNode = pNowNode->pNextnode;
}
}
return cnt;
}
*注：无头链表对第一个节点需要特殊处理。
定义两个指针（遍历指针，释放指针），均从头节点开始。遍历指针只要非空，则后移，释放指针释放掉当前的，而后后移。
操作小结：创建、插入、移除、遍历展示、更改、查询、销毁。
实现思路：快慢指针法。快指针走两格，慢指针走一个。快指针先走一格，判断是否为空指针，若为空，停止前进。
实现思路：差额指针法。快指针先走 k 格，随后快慢指针一同前进，快指针到空指针处。
实现思路：头插法实现倒置。定义两个指针（遍历指针/流动，节点插入指针/用于节点插入），使其均指向链表首位有效节点，断开头节点和链表的连接，进入遍历。
定义 2 个遍历（流动）指针，1 个终止指针，1 个暂存数据（用于数据交换）。先判断链表中有效数据的个数，有效数据个数为 0 个或 1 个时，直接退出，无需排序。进入排序，给遍历指针 1 号首位有效节点，给遍历指针 2 号第二位有效节点。
定义指针：遍历节点指针，记录最小值节点的指针，需要交换节点的指针。寻找最小值，比较，交换，后移。设定未排序部分的首位节点为可交换节点，并假设未排序部分的首位节点为最小值节点。遍历从第二位节点开始，若有遍历数据小于最小值节点的数据，则更新最小值节点（非数据交换）。完成一次遍历后，比较最小值节点的数据和未排序部分的首位节点的数据，若小于，则发生数据交换，以完成前小后大的排序。直到未排序部分的首位节点到达链表的最后一个节点。
只能删除中间节点，无法删除末尾节点。后一位节点的数据赋值给目标位节点，删除后一位节点。
有环：链表中的某位节点指向其前侧的节点。
判断是否有环，获得环长，获得环入口。 倍数遍历指针：单倍遍历指针，二倍遍历指针，两指针差值增长，每次增长一（自然增长）。指针重逢，差值即为环长。
判断有环：快走 2，慢走 1，有相遇，则有环。
环长：相遇不一定在环入口。
创建、头插、尾插、遍历、删除、销毁。
创建：一个数据区，两个指针区。
pNewNode。pNewNode->data。pNewNode->next 赋值为空白节点的 next，pNewNode->pre 赋值为空白节点地址。pNext 赋值为新节点。pre 指向新申请的节点。int InsertHeadDouList(LinkNode *pHead, DataType TmpData) {
//1. 插入节点的空间申请
LinkNode *pInsertNode = NULL;
pInsertNode = malloc(sizeof(LinkNode));
if (pInsertNode == NULL) {
perror("fail to malloc");
return -1;
}
//2. 插入节点的数据存放
pInsertNode->data = TmpData;
//3. 建立插入节点对前后节点的单向连接 (插入节点的指针存放)
pInsertNode->pPre = pHead;
pInsertNode->pNext = pHead->pNext;
//4. 建立前后节点对插入节点的回向连接
//4.1 建立头节点对插入节点的顺向连接（插入节点前节点）
pHead->pNext = pInsertNode; //pInsertNode->pPre->pNext = pInsertNode;
//4.2 链表的首位有效节点是否存在 (即插入节点的后节点是否存在)
if (pInsertNode->pNext != NULL) { //注：绝对不能用 pHead->pNext(指向内容发生了改变)
//4.3 存在，则建立链表的首位有效节点对插入节点的逆向连接（插入节点后节点）
pInsertNode->pNext->pPre = pInsertNode;
}
return 0;
}
next 指向删除节点的 next。pre 指向删除节点的 pre。pFree 指向待释放节点。存放数据的类型：遍历和单向无差（可反向遍历）。查找、修改也是（遍历找元素，修改）。销毁也一样。
链表指针区不会存放空指针。遍历终止条件判断更改为是否指向头节点。无需判断后节点为空的情况。寻找末尾节点无需一一顺向遍历，直接取头节点的前节点即可。
创建链表：特点：自己指向自己。
LinkNode *CreateEmptyCirList(void) {
LinkNode *pHead = NULL;
pHead = malloc(sizeof(LinkNode));
if (pHead == NULL) {
perror("fail to malloc");
return NULL;
}
//自我指向
pHead->pPre = pHead;
pHead->pNext = pHead;
return pHead;
}
头插法插入节点
int InsertHeadCirList(LinkNode *pHead, DataType TmpData) {
//1. 插入节点的空间申请
LinkNode *pInsertNode = NULL;
pInsertNode = malloc(sizeof(LinkNode));
if (pInsertNode == NULL) {
perror("fail to malloc");
return -1;
}
//2. 插入节点的数据存放
pInsertNode->data = TmpData;
//3. 建立插入节点对前后节点的单向连接 (插入节点的指针存放)
pInsertNode->pPre = pHead;
pInsertNode->pNext = pHead->pNext;
//4. 建立前后节点对插入节点的回向连接
pInsertNode->pPre->pNext = pInsertNode;
pInsertNode->pNext->pPre = pInsertNode;
//循环链表，指向节点始终存在，无需判断空指针问题
return 0;
}
尾插
int InsertTailCirList(LinkNode *pHead, DataType TmpData) {
//1. 插入节点的空间申请
LinkNode *pInsertNode = NULL;
pInsertNode = malloc(sizeof(LinkNode));
if (pInsertNode == NULL) {
perror("fail to malloc");
return -1;
}
//2. 插入节点的数据存放
pInsertNode->data = TmpData;
//3. 插入节点的指针存放
pInsertNode->pNext = pHead;
pInsertNode->pPre = pHead->pPre; //由于循环指向，无需遍历就可找到末尾节点（即头节点的前位节点）
//4. 前后节点对插入节点的连接建立
pInsertNode->pPre->pNext = pInsertNode;
pInsertNode->pNext->pPre = pInsertNode;
return 0;
}
插入必须通过头节点来建立插入节点和链表的连接关系。
数据展示
int ShowCirList(LinkNode *pHead) {
LinkNode *pFlow = NULL;
pFlow = pHead->pNext;
while (pFlow != pHead) { //判断条件发生变化，即是否回到头节点表示完成一次全节点遍历
printf("%d ", pFlow->data);
pFlow = pFlow->pNext;
}
printf("\n");
return 0;
}
内核链表 目的：设置一种复用性高的链表（数据类型多样，不仅仅是整型）。 数据类型由函数调用者确定。建立结构体，存放链表的节点和数据内容。链表的节点只存放前后指针，只有节点指针，没有数据类型。数据访问的实现：节点的首地址和整个结构体的首地址一样，强制类型转换将节点指针改为结构体指针，从而实现对数据的访问。
数组和链表的区别
| 对比项 | 数组 | 链表 |
|---|---|---|
| 存储空间 | 连续 | 不连续 |
| 元素个数 | 必有限 | 没有上限 |
| 插入、删除元素的效率 | 比较低 | 比较高 |
| 访问元素 | 比较方便 | 不方便 |
数组的空间是连续的，链表的空间可以不连续。数组元素必有限，链表元素是没有上限的。数组插入和删除效率比较低，链表的插入和删除效率比较高。数组访问元素比较方便，链表访问元素不方便。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online