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

✨ 坚持用清晰易懂的图解代码语言 让每个知识点都简单直观个人主页不呆头 · 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-data1;node2-data2;node3-data3;node4-data4;node1-nextnode2;node2-nextnode3;node3-nextnode4;node4-nextNULL;SLTNode*listnode1;SLTPrint(list);//实参 //形参的改变需要影响实参的时候才需要传地址这里不需要改变第一个结点所以不用传址调用}创建一个打印函数voidSLTPrint(SLTNode*phead)//形参{SLTNode*pcurphead;while(pcur!NULL){printf(%d - ,pcur-data);pcurpcur-next;}printf(NULL\n);}phead指向头结点但是为什么又要用pcur去遍历因为我们需要一个值一直指向头结点如果用phead遍历后没有指向头结点的指针且要插入一个结点需要从头结点遍历所以我们需要创建一个pcur单链表的数据插入尾插把数据存在链表里面必须给这个数据申请一个结点然后往链表里面去插入如图为数据8创建一个结点然后往链表里面插这样4的next指针不指向NULL而是指向保存8这个结点的地址就是指向newnode所以首先要找到4这个结点利用ptail遍历找尾循环条件ptail—next NULL 链表为空plist NULLnewnode 就是 头结点不用找尾//创建结点SLTNode*SLTbuyNode(SLTDataType x){//根据x创建新结点SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail!);exit(1);}newnode-datax;newnode-nextNULL;returnnewnode;}//尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x)//pphead为plist *pphead则是plist**pphead则是*plist就是结点{assert(pphead);SLTNode*newnodeSLTbuyNode(x);//链表为空if(*ppheadNULL)//plist等于空的时候{*ppheadnewnode;}else{//找尾结点SLTNode*ptail*pphead;while(ptail-next!NULL){ptailptail-next;}//找到了尾结点 ptail newnodeptail-nextnewnode;}}voidtest02(){//创建空链表SLTNode*plistNULL;SLTPrint(plist);SLTPushBack(plist,1);//plist是指向结点地址的指针plist则是指向结点地址指针的地址SLTPrint(plist);}intmain(){// test01();test02();return0;}时间复杂度O(n)头插newnode——next 需要指向第一个结点头插操作完成了但是对链表来说还需要从头结点来遍历还需要将phead移到新结点下面voidtest02(){//创建空链表SLTNode*plistNULL;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*newnodeSLTbuyNode(x);//链表为空和不为空一样newnode-next*pphead;*ppheadnewnode;}时间复杂度O(1)尾删不仅要找到尾结点删掉还要找到前一个结点把他的存储下一个结点地址的指针给为NULL先让prev的指针指向NULL然后删掉尾结点 prev一定是ptail的前一个结点注意只有一个结点和多个结点的操作是不同的 一个结点只需要直接释放掉然后赋NULL//尾删voidSLTPPopBack(SLTNode**pphead){assert(pphead*pphead);//只有一个节点if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;}else{SLTNode*prevNULL;SLTNode*ptail*pphead;//指向第一个结点while(ptail-next!NULL){prevptail;ptailptail-next;}//prev和ptail都找到prev-nextNULL;free(ptail);//释放掉ptailNULL;}}时间复杂度O(n)头删phead指向第一个结点第二个结点变成新的结点所以在删除之前将头结点的下一个结点存下来然后将头结点删掉让phead走到next只有一个结点的情况和多结点一样//头删voidSLTPopFront(SLTNode**pphead){assert(pphead*pphead);SLTNode*next(*pphead)-next;//头结点的下一个结点存下来然后将头结点删掉free(*pphead);*ppheadnext;}时间复杂度O(1)不是呆头将一直坚持用清晰易懂的图解代码语言让每个知识点变得简单️ 【关注】 看一个非典型程序员如何用野路子解决正经问题 【点赞】 给“不写八股文”的技术分享一点鼓励 【收藏】 把这些“奇怪但有用”的代码技巧打包带走 【评论】 来聊聊——你遇到过最“呆头”的 Bug 是啥️ 【投票】 您的投票是支持我前行的动力技术没有标准答案让我们一起用最有趣的方式写出最靠谱的代码