1. 顺序表的缺陷
为什么会有链表？
我们都有顺序表来存储数据了，
因为顺序表是有缺陷的：
1. 中间头部插入删除数据，需要挪动数据，效率低下。
2. 空间不够需要扩容，扩容会有一定的消耗，也可能会造成空间的浪费。
这时候，我们就要用到链表。
2. 单链表
链表是一种物理存储结构上非连续、非顺序的存储结构，
数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
如下图：
2.1 单链表的基本结构与接口函数
基本结构：
#pragma once #include #include #include typedef int SLDataType; typedef struct SListNode { SLDataType data; struct SListNode* next; }SLNode; //打印链表 void SLPrint(SLNode* phead); //尾插 void SLPushBack(SLNode** pphead, SLDataType x); //头插 void SLPushFront(SLNode** pphead, SLDataType x); //尾删 void SLPopBack(SLNode** ppheadx); //头删 void SLPopFront(SLNode** pphead); //查找 SLNode* SLFind(SLNode* phead, SLDataType x); //插入 void SLInsert(SLNode** phead, SLNode* pos, SLDataType x); //删除 void SLErase(SLNode** phead, SLNode* pos); //从pos后面插入 void SLInsertAfter(SLNode* pos, SLDataType x); //从pos后面删除 void SLEraseAfter(SLNode* pos);
2.2 重要接口
创建新节点的函数：
//建立一个新节点（重复操作写成函数复用） SLNode* BuyNewNode(SLDataType x) { //malloc一个链表节点大小的空间 SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); //检查 if (newnode == NULL) { perror("malloc::fail"); return; } //赋值 newnode->data = x; newnode->next = NULL; return newnode; }
2.2.1 尾插
//尾插 void SLPushBack(SLNode** pphead, SLDataType x) { //检查二级指针pphead地址是否为空 //方便检查是否传空指针了 assert(pphead); //创建节点 SLNode* newnode = BuyNewNode(x); //如果链表为空 if (*pphead == NULL) { *pphead = newnode; } else//如果链表不为空 { //找尾 SLNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } //尾插 tail->next = newnode; } }
2.2.2 头插
//头插 void SLPushFront(SLNode** pphead, SLDataType x) { //检查二级指针pphead地址是否为空 //方便检查是否传空指针了 assert(pphead); //创建节点 SLNode* newnode = BuyNewNode(x); //头插 newnode->next = *pphead; *pphead = newnode; }
2.2.3 尾删
//尾删 void SLPopBack(SLNode** pphead) { //检查二级指针pphead地址是否为空 //方便检查是否传空指针了 assert(pphead); //检查链表是否为空 assert(*pphead); //头删的情况（链表只有一个数据） if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //找尾 SLNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } //尾删 free(tail->next); tail->next = NULL; } }
2.2.4 头删
//头删 void SLPopFront(SLNode** pphead) { //检查二级指针pphead地址是否为空 //方便检查是否传空指针了 assert(pphead); //检查链表是否为空 assert(*pphead); //头删 SLNode* cur = (*pphead)->next; free(*pphead); *pphead = NULL; *pphead = cur; }
2.2.5 查找
//查找 SLNode* SLFind(SLNode* phead, SLDataType x) { //创建指针遍历链表 SLNode* cur = phead; //查找 while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
2.2.6 插入
//插入 void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) { //检查查找的地址是否为空 assert(pos); //pos的位置 if (pos == *pphead) { SLPushFront(pphead, x); } else//在链表中间 { SLNode* prev = *pphead; //查找pos对应位置 while (prev->next != pos) { prev = prev->next; } //插入 SLNode* newnode = BuyNewNode(x); prev->next = newnode; newnode->next = pos; } }
2.2.7 删除
//删除 void SLErase(SLNode** pphead, SLNode* pos) { //检查二级指针pphead地址是否为空 //方便检查是否传空指针了 assert(pphead); //检查查找的地址是否为空 assert(pos); //检查链表是否为空（这里其实不断言也可以） assert(*pphead); //头删的情况 if (*pphead == pos) { SLPopFront(pphead); } else { //查找 SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //删除 prev->next = pos->next; free(pos); pos = NULL; } }
2.2.8 从pos后面插入
//从pos后面插入 void SLInsertAfter(SLNode* pos, SLDataType x) { //检查查找的地址是否为空 assert(pos); //创建节点 SLNode* newnode = BuyNewNode(x); //再pos后面插入 newnode->next = pos->next; pos->next = newnode; }
2.2.9 从pos后面删除
//从pos后面删除 void SLEraseAfter(SLNode* pos) { //检查查找的地址和要删除的地址是否为空 assert(pos); assert(pos->next); //在pos后面删除，prev记住要删除的节点，然后free SLNode* prev = pos->next; pos->next = prev->next; free(pos->next); prev = NULL; }
这就是单链表的基本框架和接口了，
如果感兴趣，你也可以使用接口函数玩一玩。
3. 链表的缺陷与优势：
但是链表是有缺陷的，
我们可以看到，
1. 链表想要访问一个节点，就得遍历链表，
2. 链表的尾删也需要遍历链表，
3. 而链表的优势是头删很方便是O(1)。
4. 链表与顺序表比较
我们就能跟顺序表比较一下，
1. 顺序表头插需要挪动数据是O(N)，
2. 但是顺序表能随机访问。
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
