单链表

参考：https://www.jianshu.com/p/a43a5046399f

• 链表是以节点的方式来存储,是链式存储
• 每个节点包含 data 域， next 域:指向下一个节点.
• 链表分带哨兵节点的链表和没有哨兵节点的链表，根据实际的需求来确定
• 操作：增删改查，清空所有内存

结点结构体的定义：

定义了结点之后，我们就可以把若干个结点连接在一起，形成一个链表：
没有哨兵结点：

带哨兵结点

有时候为了操作方便，我们还会给链表增加一个不存放数据的头结点,即哨兵结点

下面以带头结点的单链表为例，讲解单链表的初始化、创建、取值、查找、插入、删除操作。

1. 单链表初始化
   单链表初始化是指构建一个空表：
   

2. 单链表的创建

创建单链表分为前插法和尾插法两种，前插法创建的单链表和输入顺序正好相反，因此称为逆序建表，尾插法创建的单链表和输入顺序一致，因此称为正序建表。

• 前插法建表如图：
  初始状态
  
  输入数据元素1，创建新结点，把元素1放入新结点数据域：
  
  前插操作，插入到头结点的后面：
  
  输入数据元素2，创建新结点，把元素2放入新结点数据域：
  
  前插操作，插入到头结点的后面：
  
  注意：修改指针顺序的原则：先修改没有指针标记的那一端。
  
  拉直链表之后：
  
  继续依次输入数据元素3，4，5，6，7，8，9，10，前插法创建链表的结果：
  

• 尾插法建表如图：
  初始状态(尾插法需要一个尾指针永远指向链表的尾结点)
  
  输入数据元素1，创建新结点，把元素1放入新结点数据域：
  
  尾插操作，插入到尾结点的后面：

输入数据元素2，创建新结点，把元素2放入新结点数据域：

尾插操作，插入到尾结点的后面：

继续依次输入数据元素3，4，5，6，7，8，9，10，尾插法创建链表的结果：

3. 单链表取值
   单链表只有头指针，各个结点的物理地址是不连续的，要想找到第i个结点，就必须从第一个结点开始按顺序往后数，一直数到第i个结点。

4. 单链表查找
   在一个单链表中查找是否存在元素e，可以定义一个p指针，指向第一个元素结点，比较p指向结点的数据域是否为e，如果相等，查找成功返回true，如果不等，则p指向p的下一个结点，即：
   

5. 单链表插入
   如果要在第i个结点之前插入一个元素，则必须先找到第i-1个结点，想一想：为什么？
   单链表只有一个指针域，是向后操作的，不可以向前处理，第i个结点之前插入一个元素相当于把新结点放在第i-1个结点和第i个结点之间。
   

6. 单链表删除
   删除一个结点，实际上是把这个结点跳过去。如图：
   
   

单向环形链表

参考：https://www.cnblogs.com/jianyingjie/p/12169091.html

双链表

参考：https://www.jianshu.com/p/10a7f84e2094

1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除
   添加节点：
3. 也分带头结点和不带头节点的

双向链表每个结点包含三个域：数据域和两个指针域，指针域分别存储前后两个元素结点的地址，即前驱和后继。因此指针指向的类型也是结点类型
结点结构体的定义：

下面以带头结点的双链表为例，讲解双向链表的初始化、创建、取值、查找、插入、删除操作。

1. 双向链表初始化
   双向链表初始化是指构建一个空表：
   
   2.双向链表的创建
   创建双向链表也可以用前插法和尾插法，前插法创建的链表和输入顺序正好相反，因此称为逆序建表，尾插法创建的链表和输入顺序一致，因此称为正序建表。
   前插法建表如图：
   (1)初始状态

(2)输入数据元素1，创建新结点，把元素1放入新结点数据域：

(3)前插操作，插入到头结点的后面：

(4)输入数据元素2，创建新结点，把元素2放入新结点数据域：

(5)前插操作，插入到头结点的后面：

注意：修改指针顺序的原则：先修改没有指针标记的那一端。

如果要插入结点的两端都有标记，例如再定义一个指针q指向第1个结点，那么先修改哪个指针都无所谓了。
拉直链表之后：

(6)继续依次输入数据元素3，4，5，前插法创建链表的结果：

尾插法建表同单链表的尾插法建表，需要有一个尾指针，不再赘述。

3. 双向链表取值、查找如同单向链表，不再赘述。

4. 双向链表插入
   
   6.双向链表删除
   

双向环形链表

参考：https://www.cnblogs.com/rongweijun/p/8072677.html
从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表，都有一个不含数据的头节点head。
双链表的示意图如下：

表头为空，表头的后继节点为"节点10"(数据为10的节点)；“节点10"的后继节点是"节点20”(数据为10的节点)，“节点20"的前继节点是"节点10”；“节点20"的后继节点是"节点30”，“节点30"的前继节点是"节点20”；…；末尾节点的后继节点是表头。

• 双链表删除节点
  删除"节点30"
  
  删除之前：“节点20"的后继节点为"节点30”，“节点30” 的前继节点为"节点20"。“节点30"的后继节点为"节点40”，“节点40” 的前继节点为"节点30"。
  删除之后：“节点20"的后继节点为"节点40”，“节点40” 的前继节点为"节点20"。

• 双链表添加节点
  在"节点10"与"节点20"之间添加"节点15"
  
  添加之前：“节点10"的后继节点为"节点20”，“节点20” 的前继节点为"节点10"。
  添加之后：“节点10"的后继节点为"节点15”，“节点15” 的前继节点为"节点10"。“节点15"的后继节点为"节点20”，“节点20” 的前继节点为"节点15"。