【数据结构】万字深入浅出讲解单链表（附原码 | 超详解）

🚀write in front🚀
📝个人主页：认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏：C语言实现数据结构
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
✉️如果无聊的话，就来逛逛我的博客栈吧stack-frame.cn

---

前言

这几天看了数据结构的单链表这一节，真的收获很大，第一次看没有动手敲代码就是感觉学了和没学一样，今天也是从新又看了一遍，并且边学边敲代码，终于算是非常理解单链表这个东西了，今天就把我所学到的知识给大家分享一下。

---

一、链表概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的 。

二、链表的分类

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1.无头单向链表

2.双向循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

三、链表的实现

函数接口汇总SList.h

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印
void SLTPrint(SLTNode* phead);
SLTNode* BuySLTNode(SLTDataType x);
//增
void SLTPushBack(SLTNode** pphead,SLTDataType x);
void SLTPushFront(SLTNode** pphead,SLTDataType x);
//删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x);
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos);
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos);

函数接口实现SList.c

//--------------------------手动分割线---------------------------
//打印
void SLTPrint(SLTNode* phead)
{assert(phead);SLTNode* cur=phead;while(cur){printf("%d ",cur->data);cur=cur->next;}printf("NULL\n");
}
//--------------------------手动分割线-----------------------------
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL) {printf("malloc fail\n");return NULL;}newnode->data=x;newnode->next=NULL;return newnode;
}
//--------------------------手动分割线-----------------------------
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{assert(pphead);SLTNode* newnode=BuySLTNode(x);if(*pphead==NULL){*pphead=newnode;}else{//找尾SLTNode* cur=*pphead;while(cur->next!=NULL){cur=cur->next;}cur->next=newnode;}
}
//--------------------------手动分割线-----------------------------
//前插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{assert(pphead);SLTNode* newnode=BuySLTNode(x);newnode->next=*pphead;*pphead=newnode;
}
//--------------------------手动分割线-----------------------------
//尾删
void SLTPopBack(SLTNode** pphead)
{// 暴力检查assert(pphead);assert(*pphead);SLTNode* cur=*pphead;if(*pphead->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode* cur=*pphead;while(cur->next->next!=NULL){cur=cur->next;}SLTNode* tmp=cur->next;free(tmp);cur->next=NULL;}
}
//--------------------------手动分割线-----------------------------
//前删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);if(*pphead->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode* tmp=*pphead;free(tmp);tmp=NULL;*pphead=*pphead->next;}
}
//--------------------------手动分割线-----------------------------
//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{SLTNode* cur=phead;while(cur){if(cur->data==x) return cur;cur=cur->next;}return NULL;
}
//--------------------------手动分割线-----------------------------
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);assert(pphead);SLTNode* newnode=BuySLTNode(x);if(*pphead==pos){SLTPushFront(pphead, x);}else{SLTNode* prev=*pphead;while(prev->next!=pos){prev=prev->next;}prev->next=newnode;newnode->next=pos;}
}
//--------------------------手动分割线-----------------------------
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);SLTNode* cur=*pphead;if(*pphead==pos){SLTPopFront(pphead);}else{while(cur->next!=pos){cur=cur->next;}cur->next=pos->next;free(pos);pos=NULL;}
}
//--------------------------手动分割线-----------------------------
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}
//--------------------------手动分割线-----------------------------
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
//--------------------------手动分割线-----------------------------

代码实践Test.c

#include"SList.h"void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);
}void TestSList2()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);
}void TestSList3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);
}int main()
{TestSList3();return 0;
}

代码汇总

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//--------------------------手动分割线---------------------------
//打印
void SLTPrint(SLTNode* phead)
{assert(phead);SLTNode* cur=phead;while(cur){printf("%d ",cur->data);cur=cur->next;}printf("NULL\n");
}
//--------------------------手动分割线-----------------------------
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL) {printf("malloc fail\n");return NULL;}newnode->data=x;newnode->next=NULL;return newnode;
}
//--------------------------手动分割线-----------------------------
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{SLTNode* newnode=BuySLTNode(x);if(*pphead==NULL){*pphead=newnode;}else{//找尾SLTNode* cur=*pphead;while(cur->next!=NULL){cur=cur->next;}cur->next=newnode;}
}
//--------------------------手动分割线-----------------------------
//前插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{SLTNode* newnode=BuySLTNode(x);newnode->next=*pphead;*pphead=newnode;
}
//--------------------------手动分割线-----------------------------
//尾删
void SLTPopBack(SLTNode** pphead)
{//暴力检查assert(*pphead);SLTNode* cur=*pphead;if(*pphead->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode* cur=*pphead;while(cur->next->next!=NULL){cur=cur->next;}SLTNode* tmp=cur->next;free(tmp);cur->next=NULL;}
}
//--------------------------手动分割线-----------------------------
//前删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);if(*pphead->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode* tmp=*pphead;free(tmp);tmp=NULL;*pphead=*pphead->next;}
}
//--------------------------手动分割线-----------------------------
//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{SLTNode* cur=phead;while(cur){if(cur->data==x) return cur;cur=cur->next;}return NULL;
}
//--------------------------手动分割线-----------------------------
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{SLTNode* newnode=BuySLTNode(x);if(*pphead==pos){SLTPushFront(pphead, x);}else{SLTNode* prev=*pphead;while(prev->next!=pos){prev=prev->next;}prev->next=newnode;newnode->next=pos;}
}
//--------------------------手动分割线-----------------------------
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{SLTNode* cur=*pphead;if(*pphead==pos){SLTPopFront(pphead);}else{while(cur->next!=pos){cur=cur->next;}cur->next=pos->next;free(pos);pos=NULL;}
}
//--------------------------手动分割线-----------------------------
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}
//--------------------------手动分割线-----------------------------
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
//--------------------------手动分割线-----------------------------void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);
}void TestSList2()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);
}void TestSList3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);
}int main()
{TestSList3();return 0;
}

总结

  今天学习了单链表的知识，初次写数据结构的知识，给我的感觉就是，学三遍不如手敲代码一遍来的实在，所以数据结构的学习我将多画图，多敲代码来学习，希望大家吸取经验和我一起学习数据结构，为后面打比赛刷题打下坚实基础。

  我是夏目浅石，希望和你一起学习进步，刷题无数！！！希望各位大佬能一键三连支持一下博主，hhhh~我们下期见喽

如果无聊的话，就来逛逛我的博客栈吧stack-frame.cn

✨$原创不易，还希望各位大佬支持一下$

👍 $点赞，你的认可是我创作的动力！$

⭐️ $收藏，你的青睐是我努力的方向！$

✏️ $评论，你的意见是我进步的财富！$