点击展开/收起 文章目录文章目录深入浅出链表一.什么是链表?二.链表的分类2.1单链表2.2双向循环表三.辨析链表与顺序表各有千秋四.经典题目分享希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力深入浅出链表一.什么是链表?链表就是我们用结构体开辟得一个节点,里面包含数据域和指针域,然后再用指针,将一个个节点穿起来,节点地址在内存中间是随机分布的,这使得他的物理结构不是连续的,但逻辑结构连续二.链表的分类由于链表内容还挺多,所以在这里我就讲解一下难点剖析,关于初始化那些可以去看看我的顺序表里面的讲解,下面就来到我们的精彩内容2.1单链表1.节点的定义typedefintSListTypeDate;typedefstructSlistNode{SListTypeDate data;structSListNode*next;}SList;2.节点创建注意在这里创建节点用的是malloc因为节点是单独分散的内存空间的,每次需要就开辟一个节点的空间,注意要检查malloc成功与否,还有就是节点下一个指针最好置为空指针,方便后续的插入节点SList*SLBuyNode(SListTypeDate x){SList*newnode(SList*)malloc(sizeof(SList));if(newnodeNULL){perror(malloc newnode fail!);exit(-1);}newnode-nextNULL;newnode-datax;returnnewnode;}3.链表的尾插在这里有两个难点易错点(1)为什么这里要传二级指针?传一级指针可以吗?答案肯定是否定的,传二级指针主要是要改变头节点的原因,因为如果我们传进来的头结点是空的,也就是链表没有节点,我们就要改变头节点,此时传的一级指针是形参无法改变实参,很抽象吧看一下图片这里传进去如果是一级指针也就是plist,此时我们之函数中间改变phead头节点,是不会影响plist的值的,这就类似于我们在swap(int*pa,int*pb),你要交换数值就必须传指针,传a,b就不会影响a,b值变化,底层原因,把值传过去给函数,函数就是拷贝此值,改变拷贝值比会影响原值所以我们要传指针(2)if (*pphead NULL)这里面*pphead为什么不能是ptail?相信有了前面的铺垫,这里大家也比较懂了吧,ptail是在函数中创建的形参,只是拷贝了*pphead的值改变形参不影响实参改变voidSLPushBack(SList**pphead,SListTypeDate x){assert(pphead);SList*nextSLBuyNode(x);SList*ptail*pphead;if(*ppheadNULL){*ppheadnext;}else{while(ptail-next){ptailptail-next;}ptail-nextnext;nextptail;}}在前面我们插入那么麻烦,我们有什么方法可以简化一下呢,有的兄弟有的,这时,我们将引入新的概念,哨兵位,就是开辟一个新节点,它里面什么都不放只在他的指针域放入头节点,如果链表为空,他的下一个节点也就指向空,也就相当于空的头节点图解如下:有了这个就解决了二级指针的引用问题,本质还是二级指针,只是我们在函数外就把plist的地址给了哨兵位,但比较好理解,代码也简化了,希望大家下来可以去实现一下4.链表的尾删注意删除操作,一定要看表里有数据么,我这里就直接暴力断言了assert(pphead *pphead);,由于我们链表尾删要找尾,我这里用一个prev来记录尾指针的前一个指针,方便后面prev成为新的尾巴voidSLPopBack(SList**pphead){assert(pphead*pphead);SList*prev,*ptail;ptailprev*pphead;if(ptail-nextNULL){free(*pphead);*ppheadNULL;}else{while(ptail-next){prevptail;ptailptail-next;}free(ptail);prev-nextNULL;prevptail;}}其他操作大同小异大家可以下来自主实现,不会的可以私信我,我会在博客上做补充.2.2双向循环表废话不多说直接上图这样我们找上一个节点就很容易了,不用创造一个prev跟着ptail一起跑,效率提高了,且找尾更加方便,phead-prevptail1.双链表的定义typedefintListDataType;typedefstructListNode{ListDataType data;structListNode*prev;structListNode*next;}ListNode;2.节点创建节点创建大同小异,在这里我就不做赘述ListNode*LTBuyNode(ListDataType x){ListNode*node(ListNode*)malloc(sizeof(ListNode));if(nodeNULL){perror(malloc);exit(1);}node-datax;node-nextnode-prevnode;returnnode;}3.链表的插入任意位置注意这里插入有一个顺序问题不然的话还要存节点比较麻烦,只需要记住,先新节点的后,再连新结点的前,再把原来此位置节点的上一个连接新节点,再把prev-next连接到新节点这丫昂,不会出现节点指针覆盖找不到下一个节点,这也是新手容易踩的坑voidLSInsert(ListNode*pos,ListDataType x){assert(pos);ListNode*newnodeLTBuyNode(x);newnode-nextpos-next;newnode-prevpos;pos-next-prevnewnode;pos-nextnewnode;}**剩下的步骤参考单链表,与上一篇顺序表,相信你,可以自主实现出来**三.辨析链表与顺序表各有千秋注意一下缓存污染问题,CPU计算速度极快,内存中拉数据比较慢,所以他每次拉数据都会在多拉一点数据,来计算,链表物理结构不连续,拉取时是拉去那一片连续的存储空间,这是链表离散的分布就会导致,拉入了垃圾数据,造成缓存污染,顺序表物理结构连续就不会产生缓存污染四.经典题目分享由于链表这里经典题目比较多,在这里小编就只举几道简单的,剩下的部分,我将在下一篇博客有详细介绍,敬请期待!(1)给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。解法,我么可以创建一个新节点,只要链表中的值不等于val我们就尾插到新链表中,最后返回newnode-next也就是新的头节点注意:最后出来之后,要把ptail-next置为空不然他还是指向的原链表的位置,会出错/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeListNode;structListNode*removeElements(structListNode*head,intval){ListNode*pcurhead;ListNode*newnode(ListNode*)malloc(sizeof(ListNode));ListNode*ptailnewnode;while(pcur){if(pcur-val!val){ptail-nextpcur;ptailpcur;}pcurpcur-next;}ptail-nextNULL;returnnewnode-next;}(2)给你单链表的头节点 head 请你反转链表并返回反转后的链表。解法一:注意这里一定要把原来的节点1指向的下一个节点置为空,不然会出现1,2节点互相指之后进入else,头插就行了/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeListNode;structListNode*reverseList(structListNode*head){ListNode*pcurhead;ListNode*pheadNULL;ListNode*prevNULL;while(pcur){prevpcur-next;if(pheadNULL){pheadpcur;phead-nextNULL;}else{pcur-nextphead;pheadpcur;}pcurprev;}returnphead;}解法二://利用三个指针反转链表步骤我按照一二三四画在图中间,有不懂的地方私信小编即可typedefstructListNodeListNode;structListNode*reverseList(structListNode*head){ListNode*l1,*l2,*pcur;pcurhead;l1l2NULL;while(pcur){l2pcur;pcurpcur-next;l2-nextl1;l1l2;}returnl1;}希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力