链表（C 语言）
目录
一、链表的概念
链表是一种顺序表，它由一个一个的节点组成，该节点中存储着该节点的数据 val 和下一个结点的位置 next。最后一个节点的 next 指向NULL。
1. 链表的结构
链表的逻辑结构是连续的，但是物理结构通常是不连续的。因为在逻辑上，好像每个节点都是链接在一起的。
但是实际上，只是 next 存储了下一个结点的地址。
2. 链表的分类
链表通过是否带哨兵位头节点、是否循环还有单向和双向三个标准分为 8 种。
哨兵位头节点：不用来存储数据，仅占位，相当于一个站岗的士兵。有了它就不用判断是不是第一次插入数据。
循环：尾节点的 next 指向头节点，形成一个环。
双向：当前节点既有下一个节点的地址，也有上一个节点的地址。
3. 链表的优势
相比于顺序表，链表具有以下优势：
（1）不需要扩容，不会造成空间的浪费
因为链表插入数据时就申请一个节点，容量刚好。
（2）插入删除数据时不需要移动数据，只需要把新的节点链接进去或者把旧的节点解开释放即可。
二、链表的实现
不管是什么类型的链表，它的基本结构都是一个节点，该节点至少需要数据的值和下一个节点的地址两个成员。
不管是顺序表也好，链表也罢，无非就是增删查改。实现的功能都是一样的，只是使用的方法不同。
下面先实现一个最基本的无头单项非循环链表，然后再实现一个带头双向循环链表。当你完成第一个链表的实现再去看第二个链表时，你会觉得非常简单。等你这两个链表都能实现的时候，你会发现链表也就这样。
1. 无头单项非循环链表的实现
老样子，分成三个文件：头文件、方法实现文件和测试文件。
头文件：ListNode.h
// 头文件
#include <stdio.h>
// 无头单向非循环链表
// 类型声明
typedef int DataType;
// 节点结构声明
typedef struct ListNode
{
DataType val; // 数据
struct ListNode* next; // 下一个结点的位置
}ListNode;
// 方法
// 获得节点
ListNode* BuyNode(DataType data);
// 头插
void ListPushFront(ListNode** pphead, DataType data);
// 头删
void ListPopFront(ListNode** pphead);
// 尾插
void ListPushBack(ListNode** pphead, DataType data);
// 尾删
void ListPopBack(ListNode** pphead);
// 查找
ListNode* ListFind(ListNode** pphead, DataType data);
// 插入
void ListInsert(ListNode* pos, DataType data);
// 删除
void ListErase(ListNode* pos);
// 打印链表
void ListPrint(const ListNode** pphead);
// 销毁链表
void ListDestory(ListNode** pphead);
方法实现文件：ListNode.c
// 头文件
#include "ListNode.h"
#include <assert.h>
#include <stdlib.h>
// 方法
// 获得节点
ListNode* BuyNode(DataType data)
{
// 申请节点
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
if (NULL == new_node)
{
perror("BuyNode::malloc: ");
exit(-1);
}
// 赋值
new_node->val = data;
new_node->next = NULL;
// 返回
return new_node;
}
// 头插
void ListPushFront(ListNode** pphead, DataType data)
{
assert(pphead);
// 获得新节点
ListNode* new_node = BuyNode(data);
// 链接
new_node->next = *pphead;
*pphead = new_node;
}
// 头删
void ListPopFront(ListNode** pphead)
{
assert(pphead);
// 空表
if (NULL == *pphead)
{
printf("Empty List!\n");
exit(-1);
}
// 删除
ListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
// 尾插
void ListPushBack(ListNode** pphead, DataType data)
{
assert(pphead);
// 获得新节点
ListNode* new_node = BuyNode(data);
// 头插判断
if (NULL == *pphead)
{
*pphead = new_node;
}
else
{
// 找尾
ListNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
// 链接
tail->next = new_node;
}
}
// 尾删
void ListPopBack(ListNode** pphead)
{
assert(pphead);
// 空表
if (NULL == *pphead)
{
printf("Empty List!\n");
exit(-1);
}
// 头删判断
if (NULL == (*pphead)->next)
{
free(*pphead);
*pphead = NULL;
}
else
{
// 找尾前节点
ListNode* pre_tail = *pphead;
while (pre_tail->next->next)
{
pre_tail = pre_tail->next;
}
// 释放尾
free(pre_tail->next);
// 新尾后置空
pre_tail->next = NULL;
}
}
// 查找
ListNode* ListFind(ListNode** pphead, DataType data)
{
assert(pphead);
ListNode* cur = *pphead;
while (cur)
{
// 找到了
if (cur->val == data)
return cur;
// 下一个
cur = cur->next;
}
// 没找到
return NULL;
}
// 插入
void ListInsert(ListNode* pos, DataType data)
{
assert(pos);
// 申请新节点
ListNode* new_node = BuyNode(data);
// 链接
new_node->next = pos->next;
pos->next = new_node;
}
// 删除
void ListErase(ListNode* pos)
{
assert(pos);
// 记录删除位
ListNode* del = pos->next;
// 链接
pos->next = pos->next->next;
// 删除
free(del);
}
// 打印链表
void ListPrint(const ListNode** pphead)
{
assert(pphead);
// 打印
const ListNode* cur = *pphead;
while (cur)
{
printf("%d ", cur->val);
// 下一个节点
cur = cur->next;
}
printf("\n");
}
// 销毁链表
void ListDestory(ListNode** pphead)
{
assert(pphead);
// 销毁
ListNode* cur = *pphead;
while (cur)
{
// 存储下一个节点
ListNode* next = cur->next;
// 删除当前节点
free(cur);
// 下一个节点
cur = next;
}
// 置空
*pphead = NULL;
}
测试文件：test.c
// 头文件
#include "ListNode.h"
// 头插头删测试
void test1()
{
ListNode* phead = NULL;
// 头插
int i = 0;
for (i = 0; i < 5; ++i)
{
ListPushFront(&phead, i);
}
ListPrint(&phead);
// 头删
for (i = 0; i < 5; ++i)
{
ListPopFront(&phead);
printf("头删 %d 次: ", i+1);
ListPrint(&phead);
}
// 销毁链表
ListDestory(&phead);
}
// 尾插尾删测试
void test2()
{
ListNode* phead = NULL;
// 尾插
int i = 0;
for (i = 0; i < 5; ++i)
{
ListPushBack(&phead, i);
}
ListPrint(&phead);
// 尾删
for (i = 0; i < 5; ++i)
{
ListPopBack(&phead);
printf("尾删 %d 次: ", i+1);
ListPrint(&phead);
}
// 销毁
ListDestory(&phead);
}
// 插入删除查找测试
void test3()
{
ListNode* phead = NULL;
// 尾插
int i;
for (i = 1; i <= 5; ++i)
{
ListPushBack(&phead, i);
}
ListPrint(&phead);
// 在每个数据后面插入 9
for (i = 1; i <= 5; ++i)
{
// 找位置
ListNode* pos = ListFind(&phead, i);
// 在后面插入 9
ListInsert(pos, 9);
}
ListPrint(&phead);
// 删除 9
for (i = 1; i <= 5; ++i)
{
// 找位置
ListNode* pos = ListFind(&phead, i);
// 在后面插入 9
ListErase(pos);
}
ListPrint(&phead);
// 销毁
ListDestory(&phead);
}
int main()
{
// 头插头删测试
printf("头插头删测试:\n");
test1();
// 尾插尾删测试
printf("\n\n尾插尾删测试:\n");
test2();
// 插入删除查找测试
printf("\n\n插入删除查找测试:\n");
test3();
return 0;
}
程序测试结果：
1.1 代码说明
1. 为什么使用二级指针？
首先，只要是插入操作，当插入第一个节点的时候需要改变头节点的指向，那么只有传入头节点的指针才能改变它的值。删除也是一个道理，当删除最后一个节点时，需要把头节点置空，也需要二级指针。所以这里已经有六个函数需要传递二级指针了，那么干脆把所有函数都设计成传递二级指针，这样既方便又统一。
2. 为什么需要对 pphead 断言？
这里要知道 pphead 是什么，它是头节点指针的地址。这个头节点指针是一定存在的，所以它的地址一定不是 NULL。
3. 为什么 ListInsert() 和 ListErase() 都是在给定位置之后插入删除？
如果在给定位置之前进行插入删除，需要遍历链表，找到前一个位置，这样就消耗了时间。而在给定位置之后插入删除，只需要链接上或者断开链接释放即可。
4. 尾插尾删需要进行判断
尾插需要判断是否是第一次插入，因为第一次插入需要改变头节点的位置。若不是第一次插入就需要寻找尾节点，然后再进行插入。
尾删需要判断是否是最后一个节点，因为删除完最后一个节点需要把头节点置空。若不是最后一个节点，需要找到尾节点的前一个节点，然后进行删除。
2. 带头双向循环链表的实现
有了前面无头单项不循环链表的基础，现在来实现这个带头双向循环链表那就是 so easy！这个新链表的节点在原来的基础上增加了一个 pre 指针，指向前一个节点。由于哨兵位头节点初始状态 pre 和 next 都指向自己，所以该链表的头节点需要使用一个函数来初始化并返回。令人最兴奋的是，该表的尾插和尾删都不要判断，而且所有函数都可以只传一级指针。
头文件：ListNode.h
// 头文件
#include <stdio.h>
// 带头双向循环链表
// 类型声明
typedef int DataType;
// 链表节点声明
typedef struct ListNode
{
DataType val; // 数据
struct ListNode* pre; // 前一个节点的地址
struct ListNode* next; // 下一个节点的地址
}ListNode;
// 方法
// 获得哨兵位头节点
ListNode* ListCreate();
// 获得新节点
ListNode* BuyNode(DataType data);
// 头插
void ListPushFront(ListNode* phead, DataType data);
// 头删
void ListPopFront(ListNode* phead);
// 尾插
void ListPushBack(ListNode* phead, DataType data);
// 尾删
void ListPopBack(ListNode* phead);
// 插入
void ListInsert(ListNode* pos, DataType data);
// 删除
void ListErase(ListNode* pos);
// 打印
void ListPrint(const ListNode* phead);
// 查找
ListNode* ListFind(const ListNode* phead, DataType data);
// 销毁
void ListDestory(ListNode* phead);
方法实现文件：ListNode.c
// 头文件
#include "ListNode.h"
#include <stdlib.h>
#include <assert.h>
// 方法
// 获得哨兵位头节点
ListNode* ListCreate()
{
// 申请新节点
ListNode* phead = BuyNode(0);
// 初始化
phead->next = phead->pre = phead;
phead->val = 0;
// 返回
return phead;
}
// 获得新节点
ListNode* BuyNode(DataType data)
{
// 申请新节点
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
if (NULL == new_node)
{
perror("ListCreate::malloc: ");
exit(-1);
}
// 初始化
new_node->next = new_node->pre = NULL;
new_node->val = data;
// 返回
return new_node;
}
// 头插
void ListPushFront(ListNode* phead, DataType data)
{
assert(phead);
// 获得新节点
ListNode* new_node = BuyNode(data);
// 前后链接
ListNode* next = phead->next;
new_node->next = next;
next->pre = new_node;
new_node->pre = phead;
phead->next = new_node;
}
// 头删
void ListPopFront(ListNode* phead)
{
assert(phead);
// 空表
if (phead->next == phead)
{
printf("Empty List!\n");
exit(-1);
}
// 存储下一个节点
ListNode* next = phead->next->next;
// 删除头节点
free(phead->next);
next->pre = phead;
phead->next = next;
}
// 尾插
void ListPushBack(ListNode* phead, DataType data)
{
assert(phead);
// 申请新节点
ListNode* new_node = BuyNode(data);
// 链接
ListNode* tail = phead->pre;
tail->next = new_node;
new_node->pre = tail;
new_node->next = phead;
phead->pre = new_node;
}
// 尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
// 空表
if (phead->next == phead)
{
printf("Empty List!\n");
exit(-1);
}
// 存储尾前节点
ListNode* new_tail = phead->pre->pre;
free(phead->pre);
new_tail->next = phead;
phead->pre = new_tail;
}
// 插入
void ListInsert(ListNode* pos, DataType data)
{
// 申请新节点
ListNode* new_node = BuyNode(data);
// 链接
ListNode* pre = pos->pre;
pre->next = new_node;
new_node->pre = pre;
new_node->next = pos;
pos->pre = new_node;
}
// 删除
void ListErase(ListNode* pos)
{
// 链接前后
ListNode* pre = pos->pre;
pre->next = pos->next;
pos->next->pre = pre;
// 释放当前结点
free(pos);
}
// 打印
void ListPrint(const ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->val);
// 下一个节点
cur = cur->next;
}
printf("\n");
}
// 查找
ListNode* ListFind(const ListNode* phead, DataType data)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
// 找到了
if (cur->val == data)
return cur;
// 下一个节点
cur = cur->next;
}
// 没找到
return NULL;
}
// 销毁
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
// 存储下一个节点
ListNode* next = cur->next;
// 删除当前节点
free(cur);
// 下一个节点
cur = next;
}
// 释放哨兵位头节点
free(phead);
}
测试文件：test.c
// 头文件
#include "ListNode.h"
// 头插头删测试
void test1()
{
// 创建链表
ListNode* phead = ListCreate();
// 头插
int i = 0;
for (i = 0; i < 5; ++i)
{
ListPushFront(phead, i);
}
ListPrint(phead);
// 头删
for (i = 0; i < 5; ++i)
{
ListPopFront(phead);
printf("头删 %d 次: ", i + 1);
ListPrint(phead);
}
// 销毁
ListDestory(phead);
phead = NULL;
}
// 尾插尾删测试
void test2()
{
ListNode* phead = ListCreate();
// 尾插
int i;
for (i = 0; i < 5; ++i)
{
ListPushBack(phead, i);
}
ListPrint(phead);
// 尾删
for (i = 0; i < 5; ++i)
{
ListPopBack(phead);
printf("尾删 %d 次: ", i+1);
ListPrint(phead);
}
// 销毁
ListDestory(phead);
phead = NULL;
}
// 插入删除查找测试
void test3()
{
// 创建链表
ListNode* phead = ListCreate();
// 尾插
int i;
for (i = 0; i < 5; ++i)
{
ListPushBack(phead, i);
}
ListPrint(phead);
// 插入
for (i = 0; i < 5; ++i)
{
ListNode* pos = ListFind(phead, i);
ListInsert(pos, 9);
}
ListPrint(phead);
// 删除
for (i = 0; i < 5; ++i)
{
ListNode* pos = ListFind(phead, i);
ListErase(pos);
}
ListPrint(phead);
// 销毁
ListDestory(phead);
phead = NULL;
}
int main()
{
头插头删测试
//test1();
尾插尾删测试
//test2();
// 插入删除查找测试
test3();
return 0;
}
程序测试结果：
2.1 代码说明
1. 所有函数都只传一级指针
因为有哨兵位头节点的存在，不管是增删查改哪个功能都只需要一级指针。只是销毁链表需要在外头置空。
2. 尾插和尾删不需要检查和找尾
即使表中没有数据节点，但是还存在哨兵位头节点。且它的前一个就是尾节点，不需要寻找。
3. ListInsert() 和 ListErase() 函数可以在当前位置之前进行操作
由于该链表是双向的，不需要遍历寻找前一个节点。所以可以删除当前位置的节点和在当前节点的前面插入节点。
三、链表和顺序表的区别
上面的图片是偷课件的，下面作者用自己的理解来说明一下：
（1）顺序表是使用数组实现的，在内存中的存储是连续的。而链表是通过申请一个个节点链接在一起的，物理上是不连续的（极低概率的就不要来抬杠了）。
（2）顺序表支持随机访问，时间复杂度为O(1)；而链表不支持随机访问，需要从头节点开始寻找，时间复杂度为O(N)。
（3）顺序表在插入元素的时候可能会触发增容，可能会造成空间浪费；链表没有增容这个说法，每次插入都申请一个新的节点，需要多少就申请多少，不存在浪费。
（4）顺序表在插入和删除元素时，时间复杂度最高为O(N)，最低为O(1)，分别对应头插头删和尾插尾删，平均时间复杂度为O(N)。而链表其实也和顺序表差不多，头插头删为O(1)，尾插尾删为O(N)，平均时间复杂度也是O(N)。但是由于顺序表存在增容，所以链表还是优于顺序表。
（5）顺序表的缓存利用率远高于链表。
关于缓存利用率这个概念，大家就只能自己下去了解一下了，我只能偷张图来帮助大家。
四、链表总结
其实在写完带头双向循环链表的时候，大家心中肯定在想，这个 3 层 buff 的表这么牛逼，为什么还要使用无头单项非循环链表。这是因为出面试题的时候使用的链表基本上是后者，如果给你前者，那么题目就会变得很简单。再者，无头单项非循环链表是一些复杂数据结构的子结构，一般不单独使用。
而带头双向循环链表可以根据使用场景来使用。
原文地址：https://blog.csdn.net/weixin_70742989/article/details/143493747
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！