【数据结构与算法】——单链表（上）

✨ 坚持用清晰易懂的图解+代码语言， 让每个知识点都简单直观！
🚀个人主页：不呆头 · CSDN
🌱代码仓库：不呆头 · Gitee
📌专栏系列：

• 📖 《C语言》
• 🧩 《数据结构》
• 💡 《C++》
• 🐧 《Linux》

💬座右铭：“不患无位，患所以立。”

目录

链表的解释

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

“车头” ：plist是个变量，存储的是个地址，说明他是个指针
“车厢” ： 相当于一个结点，不同于顺序表的是，它不仅存储数据，还存储了一个地址（或是个指针，因为指针存储地址）。

这是两个不同类型的数据，只有结构体才能保存不同类型的数据 ————>由图知，每个结点由需要存储的数据和保存下一个结点的地址的指针组成

structSListNode//S->Single SListNode 由结点组成的单链表{intdata;//存储的数据structSListNode*next;//指向下一个结点的指针}

每个结点都是个独立的空间

单链表的打印

//手动构造链表voidtest01(){//创建结点SLTNode*node1=(SLTNode*)malloc(sizeof(SLTNode));//malloc申请空间不用去增容，此处是申请一个结点大小的空间SLTNode*node2=(SLTNode*)malloc(sizeof(SLTNode));SLTNode*node3=(SLTNode*)malloc(sizeof(SLTNode));SLTNode*node4=(SLTNode*)malloc(sizeof(SLTNode));node1->data=1;node2->data=2;node3->data=3;node4->data=4;node1->next=node2;node2->next=node3;node3->next=node4;node4->next=NULL;SLTNode*list=node1;SLTPrint(list);//实参 //形参的改变需要影响实参的时候才需要传地址，这里不需要改变第一个结点所以不用传址调用}

创建一个打印函数

voidSLTPrint(SLTNode*phead)//形参{SLTNode*pcur=phead;while(pcur!=NULL){printf("%d -> ",pcur->data);pcur=pcur->next;}printf("NULL\n");}

phead指向头结点，但是为什么又要用pcur去遍历？
因为我们需要一个值一直指向头结点，如果用phead遍历后，没有指向头结点的指针
且要插入一个结点需要从头结点遍历，所以我们需要创建一个pcur

单链表的数据插入

尾插

把数据存在链表里面，必须给这个数据申请一个结点，然后往链表里面去插入
如图：为数据8创建一个结点，然后往链表里面插，这样4的next指针不指向NULL而是指向保存8这个结点的地址，就是指向newnode，所以首先要找到4这个结点，利用ptail遍历找尾

循环条件：（ptail—>next ！= NULL ）

链表为空：plist = NULL
newnode 就是 头结点，不用找尾

//创建结点SLTNode*SLTbuyNode(SLTDataType x){//根据x创建新结点SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL){perror("malloc fail!");exit(1);}newnode->data=x;newnode->next=NULL;returnnewnode;}//尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x)//pphead为&plist ，*pphead则是plist，**pphead则是*plist，就是结点{assert(pphead);SLTNode*newnode=SLTbuyNode(x);//链表为空if(*pphead==NULL)//plist等于空的时候{*pphead=newnode;}else{//找尾结点SLTNode*ptail=*pphead;while(ptail->next!=NULL){ptail=ptail->next;}//找到了尾结点 ptail newnodeptail->next=newnode;}}

voidtest02(){//创建空链表SLTNode*plist=NULL;SLTPrint(plist);SLTPushBack(&plist,1);//plist是指向结点地址的指针，&plist则是指向结点地址指针的地址SLTPrint(plist);}intmain(){// test01();test02();return0;}

时间复杂度：O(n)

头插

newnode——>next 需要指向第一个结点，头插操作完成了，但是对链表来说还需要从头结点来遍历，还需要将phead移到新结点下面

voidtest02(){//创建空链表SLTNode*plist=NULL;SLTPrint(plist);//SLTPushBack(&plist, 1); //plist是指向结点地址的指针，&plist则是指向结点地址指针的地址SLTPushFront(&plist,1);SLTPushFront(&plist,2);SLTPushFront(&plist,3);SLTPushFront(&plist,4);SLTPrint(plist);}intmain(){// test01();test02();return0;}

//头插voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnode=SLTbuyNode(x);//链表为空和不为空一样newnode->next=*pphead;*pphead=newnode;}

时间复杂度：O(1)

尾删

不仅要找到尾结点删掉，还要找到前一个结点把他的存储下一个结点地址的指针给为NULL
先让prev的指针指向NULL，然后删掉尾结点 prev一定是ptail的前一个结点
注意：只有一个结点和多个结点的操作是不同的 一个结点只需要直接释放掉然后赋NULL

//尾删voidSLTPPopBack(SLTNode**pphead){assert(pphead&&*pphead);//只有一个节点if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode*prev=NULL;SLTNode*ptail=*pphead;//指向第一个结点while(ptail->next!=NULL){prev=ptail;ptail=ptail->next;}//prev和ptail都找到prev->next=NULL;free(ptail);//释放掉ptail=NULL;}}

时间复杂度：O(n)

头删

phead指向第一个结点，第二个结点变成新的结点，所以在删除之前，将头结点的下一个结点存下来，然后将头结点删掉，让phead走到next
只有一个结点的情况：和多结点一样

//头删voidSLTPopFront(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*next=(*pphead)->next;//头结点的下一个结点存下来，然后将头结点删掉free(*pphead);*pphead=next;}

时间复杂度：O(1)

不是呆头将一直坚持用清晰易懂的图解+代码语言，让每个知识点变得简单！
👁️ 【关注】 看一个非典型程序员如何用野路子解决正经问题
👍 【点赞】 给“不写八股文”的技术分享一点鼓励
🔖 【收藏】 把这些“奇怪但有用”的代码技巧打包带走
💬 【评论】 来聊聊——你遇到过最“呆头”的 Bug 是啥？
🗳️ 【投票】 您的投票是支持我前行的动力
技术没有标准答案，让我们一起用最有趣的方式，写出最靠谱的代码！ 🎮💻