注：这是本人观看B站王卓老师讲的数据结构与算法的学习笔记
2.4 线性表的链式表示和实现 链表的术语 什么是链表 链表的特点链表头节点
链表头节点装的什么
单链表 单链表的定义 单链表上各种操作的实现（重点） 简单操作 判断链表是否为空注：P24集
单链表的销毁注：P25集
算法思路
算法实现
清空链表注：P26集
清空链表算法分析
算法实现
单链表求表长注：P27集
算法分析
算法实现
重要操作 取值注：P28集和部分知识回顾
算法思路
算法步骤
算法实现
查找注：P29集
算法分析
算法步骤
算法实现
查找地址
查找元素位置
插入注：P30集
算法分析
算法步骤
算法实现
删除注：P31集
算法分析
算法步骤
算法实现
重要操作
1.最重要的，怎么把要删除的节点，从指针链上取下来，不要了，将要删除的后继节点(a i+1)链接到删除节点的前一个节点(a i-1)
即 p -> next = q-> next
2.需要一个循环找到第i -1 个节点
单链表的查找、插入、删除算法时间效率注：P32集
1.查找：
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)
2.插入和删除：
因线性链表不需要移动元素，只需要修改指针，一般情况下时间复杂度为O(1)
但是，如果要在单链表中进行前插和删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)
单链表的建立第一种方法：头插法——元素插入在链表头部，也叫前插法 P33集
1.从一个空表开始，重复读入数据
2.生成新结点，将读入数据存放到新结点的数据域中
3.从最后一个结点开始，一次将各结点插入到链表的前端
算法实现
算法的时间复杂度：O(n)
第二种方法：尾插法——元素插入在链表尾部，也叫后插法 P34集
1.从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点
2.初始时，r同l均指向头结点，每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点
算法实现
算法的时间复杂度：O(n)
循环链表注:p35集
循环链表：是一种头尾相接的链表（即：表中最后一个结点的指针 域指向头结点，整个链表形成一个环）
优点：从表中任意结点出发均可找到表中其他结点
头指针的循环链表
尾指针的循环链表
带尾指针的循环链表的合并有以下4步操作 注：p36集
1.先存放Ta链表的表头结点 2.将Ta链表的表尾连接到Tb链表的表头
3.删除Tb链表的表头结点 4.修改Tb链表表尾指针指向Ta链表头结点
算法描述
双向链表注：p37集
什么是双向链表单链表的缺点
单链表的结点—>有指示后继的指针域—>找后继结点方便；
即：查找某结点的后继结点的执行时间为O(1)。
—>无指示前驱的指针域—>找前驱结点难：从表头出发查找
即：查找某结点的前驱结点的执行时间为O(n)
所以：可以用双向链表来客服单链表的这种缺点
双向链表：在单链表的每个结点里面再增加了一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表
双向链表结构定义双向链表的表示如下
空表表示
既然单链表有循环链表，那么双向链表也有，如图
双向循环链表空表
双向链表的结构的对称性某个结点P 它的下一个结点的前驱指向它本身，它上一个结点的后继指向它本身
即: p—>prior—>next = p = p—>next—>prior
在进行链表长度和获取元素操作时，和单链表一样
只有在插入和删除的时候和单链表不一样，每个结点有两个指针域，插入和删除时需要同时修改这两个方向上的指针
双向链表的插入注：p38集
插入操作的步骤
插入的算法实现
注意：if中 p=GetElemP_Dul(L,i) 获取某个元素的位置操作和单链表的查找操作一样，可查看单链表的查找操作。
双向链表的删除注：p39集
删除操作步骤解析
删除算法实现
注意：如果已知删除元素的位置时，那么算法时间复杂度时O(1)，如果位置要删除元素的位置，需要循环查找时，时间复杂度是O(n)，所以算法的时间复杂度是O(n)。
单链表、循环链表、双向链表的比较注：p40集
