单链表

image-20200618221439465 image-20200618221516210

什么是单链表？

image-20200618221658525

单链表的定义

image-20200618221959788

别名

image-20200618222203154 image-20200618222313544

注释：或者可以理解为指向头节点的指针既可以表示整个单链表也可以表示头节点，为了便于区分才建议使用 typedef 进行重命名，以方便区别其不同的含义

头插法建立单链表

image-20200619095117732

单链表的基本操作

单链表的初始化

不带头节点的单链表的初始化

image-20200619095400757

带头节点的单链表的初始化

image-20200619095545238

两者区别是什么？

image-20200619095738329

总结

image-20200619095821536

插入和删除

image-20200619104612536

插入

按位序插入（带头节点的单链表）

image-20200619105030154

具体实现

分析在表头插入

image-20200619105401211

分析为什么不能颠倒

image-20200619105451377

分析在表中插入

image-20200619105800111

分析在表尾插入

image-20200619110039686

分析插入位置超出表长

image-20200619110159253

总结

image-20200619110309541

按位插入（不带头节点）

image-20200619110418752

具体实现

image-20200619110547637

结论：不带头节点的单链表，写代码更不方便，除非特别声明，默认推荐使用带头节点的实现方式，还有要注意在考试中带头、不带头都有可能考察，注意审题。

指定节点的后插操作

image-20200619111032277

指定节点的前插操作

通过传入头指针实现前插

image-20200619111607840

先进行后插，然后交换前后数据，以此实现前插

image-20200619111716141 image-20200619111814873

删除

带有头节点版本

image-20200619111915877

具体实现

image-20200619135048885

删除指定结点

image-20200619135226089

如果P是最后一个节点，咋办？

只能从表头表头依次寻找前驱，时间复杂度O(n)

image-20200619135401028

单链表的局限性：无法逆向检索！！

总结

image-20200619135623242

查找

按位查找(带头节点)

image-20200619152704151

按值查找(带头节点)

image-20200619153147639

求表的长度(带头节点)

image-20200619153411974

总结

image-20200619153525681

单链表的建立方法

image-20200619153742876

PS：找不到对象就娶一个数据元素吧！哈哈

尾插法

第一种方法：

image-20200619154012867

问题：时间复杂度太高！！可以用一个指针记录最后一个数据元素的位置来优化时间。

优化之后:

image-20200619172815577

头插法

image-20200619172945304

具体实现：

image-20200619173800669

总结

image-20200619173925151