顺序表（顺序存储）
定义：
基本操作的实现：
内存分配：
静态分配（数组）：
动态分配[malloc-free（头文件stdlib.h）/new-delete（面向对象）]：
示例代码：
顺序表的特点：
总结：
插入与删除：
插入：
删除：
总结：
查找：
按位查找：
按值查找：
总结：
链式表（链式结构）
单链表
什么是单链表：
不带头节点的单链表：
带头结点的单链表：
不带头节点VS带头节点：
总结1：
单链表的插入和删除：
头节点插入：
不带头节点（对插入第一个结点做特殊处理）：
指定结点的后插操作（给定结点p）：
通过调用函数可简化前面的代码
指定结点的前插操作：（给定结点p，寻找其前驱结点）
①首先要遍历列表，找到要插入位置的前一个结点在哪，然后就可以进行插入操作。时间复杂度为O(N)
②这里介绍一种插入方法，要插入结点的数据复制一个新的结点，此节点的数据改为要插入的数据，然后将复制数据插入列表。这样不需要知道前驱节点。且时间复杂度位O(1)（此方法不需要查找p的前驱结点）
删除指定位序的结点：
指定结点删除，复制后面的结点数据给要删除的结点，然后删除后面结点,时间复杂度为O(1)：
如果是最后一个结点的删除，上述代码会报错，只能遍历列表寻找前驱：
单链表的建立：
步骤（具体代码请看前面笔记，这里只介绍一些新的知识）：
①建立一个链表，一般建立带头节点的链表
②执行前插或者后插操作
A.尾插：
双尾指针法：
s虽然在过程中指向了其他空间，但是最后r,s始终指向末尾数据。输入9999时会将末尾设置为null，结束后返回L指针
B.头插
思考：不带头节点的头插法
去掉会出现野指针（指向未知区域）的情况，最终导致数据异常，因此要习惯于初始化链表时将头节点指向null
头插法的重要运用：链表的逆置
①创建一个新的链表逆置，使用头插法（旧链表的第一个元素变为了新链表的最后一个元素），逆指旧的链表，最终让头指针指向新的链表。
②原地逆置，将链表的后面数据前插到链表前面
注：使用指针来扫描链表获取数据
总结2：
双链表
带头结点的双链表的的初始化：
双链表的插入：
双链表的删除：
双链表的遍历操作：
双链表不支持随机存取（什么是随机存取见知识补充），按位查找（找到指定位置上的结点）、按值查找（找到指定的值）都需要遍历链表，其时间复杂度为O(N)。
总结：
循环列表：
在链表的基础上是最后一个结点的指针不指向null，而指向头节点
循环单链表：
初始化：将头节点的next指针指向自己，判断循环单链表是否为空时判断头结点的指针是否与L指向的地址相同（都指向头节点）。
判断一个结点是否是尾部结点时判断指针是否指向头节点
循环双链表：
初始化循环双链表及判断链表是否为空和尾结点：
循环双链表的插入：
非循环链表在尾结点后插时由于尾结点会出现一定的问题，而循环链表则没有该类问题
循环双链表的删除：
非循环链表在删除尾结点时由于尾结点会出现一定的问题，而循环链表则没有该类问题
总结：
静态链表：
若有收获，就点个赞吧
0 人点赞
