1单链表的插入删除

本节内容单链表插入和删除研/CSKAOYAN知识总览研/CSKAOYAN关于简化图示的说明单链表LLNode

*p=(LNode

*)malloc(sizeof(LNode));单链表L（带头结点）（不带头结点）Lfree(p);pNULLp内存内存头结点a1a2a4NULLa3头a1a2a3a4a1a2a4NULLa3研/CSKAOYAN按位序插入（带头结点）ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。找到第

i-1

个结点，将新结点插入其后头结点可以看作“第0个”结点LNULL头a1a2a3a4smalloce研/CSKAOYAN按位序插入（带头结点）分析：①如果

i=1（插在表头）i-1=0LNULLp最好时间复杂度：O(1)s头ea1a2a3a4注意：绿绿和黄黄顺序不能颠倒鸭！研/CSKAOYAN按位序插入（带头结点）分析：①如果

i=1（插在表头）i-1=0LNULL头a1a2a3a4pse注意：绿绿和黄黄顺序不能颠倒鸭！研/CSKAOYAN按位序插入（带头结点）分析：②如果

i=3（插在表中）i-1=2LNULL头a1a2a3a4pse研/CSKAOYAN按位序插入（带头结点）分析：③如果

i=5（插在表尾）i-1=4LNULL头a1a2a3a4p最坏时间复杂度：O(n)se研/CSKAOYAN按位序插入（带头结点）分析：④如果

i=6（i>Lengh）i-1=5LNULL头a1a2a3a4p研/CSKAOYAN按位序插入（带头结点）平均时间复杂度：O(n)研/CSKAOYAN按位序插入（不带头结点）ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。找到第

i-1

个结点，不存在“第0个”将新结点插入其后结点，因此

i=1

时需要特殊处理LNULLa1a2a3a4smalloce研/CSKAOYAN按位序插入（不带头结点）分析：①如果

i=1（插在表头）如果不带头结点，则插入、删除第1个元素时，需要更改头指针LsLNULLea1a2a3a4研/CSKAOYAN按位序插入（不带头结点）分析：②如果

i>1…La1a2a3a4NULLp后续逻辑和带头结点的一样除非特别声明，之后的代码默认带头结点结论：不带头结点写代码更不方便，推荐用带头结点注意：考试中带头、不带头都有可能考察，注意审题研/CSKAOYAN指定结点的后插操作某些情况下有可能分配失败（如内存不足）神秘未知区域…………神秘可知区域xyps时间复杂度：O(1)e研/CSKAOYAN指定结点的后插操作研/CSKAOYAN指定结点的前插操作如何找到

p

结点的前驱结点？神秘未知区域…………神秘可知区域xyp传入头指针LNULL高清无码拒绝神秘头a1a2a3a4时间复杂度：O(n)循环查找p的前驱qpq，再对q后插研/CSKAOYAN指定结点的前插操作时间复杂度：O(1)神秘未知区域…………神秘可知区域psxexy研/CSKAOYAN指定结点的前插操作版本tempx神秘未知区域…………神秘可知区域psxey研/CSKAOYAN按位序删除（带头结点）ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。找到第

i-1

个结点，将其指针指向第i+1个结点，并释放第i个结点头结点可以看作“第0个”结点LNULL头a1a2a3a4i=1p研/CSKAOYAN按位序删除（带头结点）i-1=3分析：e如果

i=4…LNULLp最坏、平均时间复杂度：O(n)q头a1a2a3a4最好时间复杂度：O(1)如果不带头结点，删除第1个元素，是否需要特殊处理？研/CSKAOYAN指定结点的删除神秘未知区域…………神秘可知区域xyp删除结点p，需要修改其前驱结点的

next

指针方法1：传入头指针，循环寻找

p

的前驱结点方法2：偷天换日（类似于结点前插的实现）研/CSKAOYAN指定结点的删除可能是指向一个结点，也可能是指向NULL神秘未知区域…………神秘可知区域时间复杂度：O(1)pqxyy研/CSKAOYAN指定结点的删除❌单链表的局限性：无法逆向检索，有时候不太方便如果p是最后一个结点…神秘未知区域……NULL只能从表头开始依pq次寻找p的前驱，时间复杂度

O(n)x研/CSKAOYAN知识回顾与重要考点注意审题：带头否？有坑：指定结点是最后一个结点时，需要特殊处理Tips：1.

这些代码都要会写，都重要2.

打牢基础，慢慢加速3.

体会带头结点、不带头结点的代码区别4.

体会“封装”的好处研/CSKAOYAN小功能模块化，封装的好处代码逻辑清晰也可以称为“基本操作”。对书本的概念理解不要教条化指针p指向第

i-1个结点p后插入新元素e研/CSKAOYAN知识