单链表

什么是单链表？

单链表的定义

别名

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

头插法建立单链表

单链表的基本操作

单链表的初始化

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

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

两者区别是什么？

总结

插入和删除

插入

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

具体实现

分析在表头插入

分析为什么不能颠倒

分析在表中插入

分析在表尾插入

分析插入位置超出表长

总结

按位插入（不带头节点）

具体实现

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

指定节点的后插操作

指定节点的前插操作

通过传入头指针实现前插

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

删除

带有头节点版本

具体实现

删除指定结点

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

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

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

总结

查找

按位查找(带头节点)

#####按值查找(带头节点)

求表的长度(带头节点)

总结

单链表的建立方法

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

尾插法

第一种方法：

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

优化之后:

头插法

具体实现：

总结