单链表
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-20200619153742876PS:找不到对象就娶一个数据元素吧!哈哈
尾插法
第一种方法:
image-20200619154012867问题:时间复杂度太高!!可以用一个指针记录最后一个数据元素的位置来优化时间。
优化之后:
image-20200619172815577头插法
image-20200619172945304具体实现:
image-20200619173800669
网友评论