双向链表
-
概念及简介：
-
单链表是指结点中只有一个指向其后继的指针，具有单向性，但是有时需要搜索大量数据的时候，就需要多次进行从头开始的遍历，这样的搜索就不是很高效了。
-
在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表，就产生了双向链表的概念了。
-
双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
-
双向链表的节点设计
对于每一个结点而言，有：
其中，DATA表示数据，其可以是简单的类型也可以是复杂的结构体；
pre代表的是前驱指针，它总是指向当前结点的前一个结点，如果当前结点是头结点，则pre指针为空；
next代表的是后继指针，它总是指向当前结点的下一个结点，如果当前结点是尾结点，则next指针为空
-
双向链表的插入操作
如图所示：
对于每一次的双向链表的插入操作，首先需要创建一个独立的结点，并通过malloc操作开辟相应的空间；
其次我们选中这个新创建的独立节点，将其的pre指针指向所需插入位置的前一个结点；
同时，其所需插入的前一个结点的next指针修改指向为该新的结点，该新的结点的next指针将会指向一个原本的下一个结点，而修改下一个结点的pre指针为指向新结点自身，这样的一个操作我们称之为双向链表的插入操作。
-
双向链表的删除操作
如图：
删除操作的过程是：选择需要删除的结点->选中这个结点的前一个结点->将前一个结点的next指针指向自己的下一个结点->选中该节点的下一个结点->将下一个结点的pre指针修改指向为自己的上一个结点。
在进行遍历的时候直接将这一个结点给跳过了，之后，我们释放删除结点，归还空间给内存，这样的操作我们称之为双链表的删除操作。
循环链表：
-
循环链表的概念：
对于单链表以及双向链表，就像一个小巷，无论怎么走最终都能从一端走到另一端，顾名思义，循环链表则像一个有传送门的小巷，当你以为你走到结尾的时候，其实这就是开头。
循环链表和非循环链表其实创建的过程唯一不同的是，非循环链表的尾结点指向空（NULL），而循环链表的尾指针指向的是链表的开头。
通过将单链表的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）
一个完整的循环单链表如图：
-
循环链表结点设计（以单循环链表为例）:
对于循环单链表的结点，可以完全参照于单链表的结点设计，如图：
data表示数据；
next表示指针，它总是指向自身的下一个结点，对于只有一个结点的存在，这个next指针则永远指向自身，对于一个链表的尾部结点，next永远指向开头。
-
循环链表的创建操作
如图所示：
通过逐步的插入操作，创建一个新的节点，将原有链表尾结点的next指针修改指向到新的结点，新的结点的next指针再重新指向头部结点，然后逐步进行这样的插入操作，最终完成整个单项循环链表的创建。
-
循环链表的插入操作
如图，对于插入数据的操作，可以创建一个独立的结点，通过将需要插入的结点的上一个结点的next指针指向该节点，再由需要插入的结点的next指针指向下一个结点的方式完成插入操作。
-
循环链表的删除操作
如下图所示，循环单链表的删除操作是先找到需要删除的结点，将其前一个结点的next指针直接指向删除结点的下一个结点即可。
需要注意的是尾结点，因为删除尾节点后，尾节点前一个结点就成了新的尾节点，这个新的尾节点需要指向的是头结点而不是空。
单链表、双链表、循环单链表、循环双链表的对比
-
单链表：拥有指向下一节点的指针。查找元素需要从头结点遍历
-
双链表：拥有指向上一节点和下一节点的指针。相对于单链表，在找当前节点的前一节点时比较方便，占用空间比单链表大。
-
单循环链表：单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
-
双循环链表：可以从任何结点开始任意向前向后双向访问。
-
单链表和单循环链表：只能在当前结点后插入和删除。
-
双链表：可以在当前结点前面或者后面插入，可以删除前趋和后继（包括结点自己）。
-
存储：单链表和单循环链表存储密度大于双链表。