双向链表的结构
单链表和环形链表都是属于有方向的链表，每个节点都只有向后的一个指针，所以都只能单向遍历。而且要想查找某个节点的前驱节点会很不方便，因为没有直接指针指向前驱节点。为了解决这些问题，在单链表的每个节点中，再加一个指针指向它的前驱节点，就形成了双向链表，双向链表同样也有一个头节点和一个尾节点。头节点的前驱指针始终为null，尾节点的后驱指针始终为null，双向链表还有一个巨大的优势，就是它不需要反转，因为它可以从头节点向后遍历，也可以从尾节点向前遍历。具体结构图如下： 
所以说，双向链表的每个节点包含三个字段：前驱指针、数据字段、后驱指针。
双向链表的定义
我们的程序中声明双向链表的节点类为DoubleNode，封装算法的类为DoubleLinkedList，DoubleLinkedList类中声明了两个变量First和Last分别代表头指针变量和尾指针变量。 具体代码如下：
public class DoubleNode
{
public int Data;
public DoubleNode PreNode;
public DoubleNode NextNode;
public DoubleNode(int data, DoubleNode pre = null, DoubleNode next = null)
{
Data = data;
PreNode = pre;
NextNode = next;
}
}
public class DoubleLinkedList
{
public DoubleNode first;//头节点指针
public DoubleNode last;//尾指针
int _length;//链表长度
}
这里大家要注意，再DoubleLinkedList类中我们声明了一个变量_length，它表示链表的长度，也就是链表中节点的数量。其实这个_length是非常方便的，尤其是在按照索引删除、查找、删除、甚至是插入的时候(插入到尾部)的时候，在单链表和双向链表中，我们并没有添加这个变量，当大家写完单链表、环形链表和环形链表的算法之后能深刻的感受到这个变量给我们带来的方便。 当然这个变量也会给程序稍微带来一点麻烦，因为每次新增、删除的时候修需要维护这个变量。
算法1:创建双向链表
创建双向链表指创建包含一组节点的双向链表。如依次输入0,1,2,3,4,5来创建双向链表，和单链表、环形链表一样，双向链表的创建也有两种方法，前插法和后插法。 前插法是每次都将新节点作为头节点插入到链表中，后插法是每次都将新节点作为尾节点插入到链表中。当首次插入的时候前插法和后插法的指针操作都一样，只需要将First和Last都指向新节点即可，即:First=newNode;Last=newNode;,但是链表中已经有多个节点的情况下，前插法和后插法的指针操作有所差异。
前插法每次插入新节点需要修改的指针伪代码如下：
1、新节点后驱指针指向头节点First：newNode.Next=First
2、头节点First的前驱指针指向新节点：First.Pre=newNode
3、头节点指针First指向新节点：First=newNode
具体请看如下示例图，三个红箭头代表需要新增或者修改的指针：
前插法的具体示例代码如下：
public void InsertInHead(int data)
{
DoubleNode newNode = new DoubleNode(data);
if (first == null)//首次插入节点
{
first = newNode;
last = newNode;
_length++;
return;
}
newNode.Next = first; //步骤1 新节点后驱指针指向头节点First
first.Pre = newNode; //步骤2 头节点First的前驱指针指向新节点
first = newNode; //步骤3 头节点指针First指向新节点
_length++;
}
代码中的步骤1、步骤2、步骤3分别代表我们上面描述的三个伪代码。
后插法每次插入新节点需要修改的指针伪代码如下：
1、尾指针后驱指针指向新节点： Last.Next=newNode
2、新节点前驱指针指向尾节点： newNode.Pre=Last
3、尾节点Last指向新节点： Last=newNode
具体请看如下示例图，三个红箭头代表需要新增或者修改的指针： 
后插法的具体示例代码如下：
public void InsertInLast(int data)
{
DoubleNode newNode = new DoubleNode(data);
if (first == null)
{
first = newNode;
last = newNode;
_length++;
return;
}
last.Next = newNode;//步骤1、尾指针后驱指针指向新节点
newNode.Pre = last; //步骤2、新节点前驱指针指向尾节点
last = newNode; //步骤3、尾节点Last指向新节点
_length++;
}
代码中的步骤1、步骤2、步骤3分别代表我们上面描述的三个伪代码。
算法2：查找
双向链表的查找和数组的查找类似，它可以从头节点开始遍历，也可以从尾节点开始遍历。 双向链表的查找有两种算法，一种是按照索引查找(查找链表中的第n个节点)，一种是按照值查找(查找链表中，节点值等于给定值的节点)。
按照索引查找的具体代码如下：
public DoubleNode GetByIndex(int index)
{
var currentNode = first;
int i = 1;
while (i != index)
{
currentNode = currentNode.Next;
i++;
}
return currentNode;
}
按照值查找的具体示例代码如下：
public DoubleNode GetByData(int data)
{
DoubleNode currentNode = first;
while (currentNode != null && currentNode.Data != data)
{
currentNode = currentNode.Next;
}
return currentNode;
}
算法3：插入新节点
插入新节点分为三种情况：在链表头插入、链表中间插入、链表尾部插入。其实在创建链表的时候头插法和尾插法的示例就是在链表头部和链表尾部插入。 双向链表中间插入一个节点需要修改四个指针，图中红色节点表示要插入的节点，红色箭头代表需要调整的指针。
1、指定位置前一个节点的后去指针指向新节点：preNode.Next=newNode
2、新节点的前驱指针指向指定位置的前一个节点：newNode.Pre=preNode
3、新节点的后去指针指向指定位置的节点：newNode.Next=current
4、指定位置节点的前驱指针指向新节点：current.Pre=newNode
插入节点的具体示例代码如下。这个代码中，我们可以在链表的任何一个位置插入新的节点，包括链表头部位置和尾部位置。
public void Insert(int index, int data)
{
//头部插入
if (index == 1)
{
InsertInHead(data);
return;
}
//尾部插入
if (index > _length)
{
InsertInLast(data);
return;
}
//中间插入
int i = 1;
DoubleNode currentNode = first;
DoubleNode preNode = null;
while (i != index)
{
preNode = currentNode;
currentNode = currentNode.Next;
i++;
}
DoubleNode newNode = new DoubleNode(data);
preNode.Next = newNode; //步骤1、指定位置的前一个节点的后驱动指针指向新节点
newNode.Pre = preNode; //步骤2、新节点的前驱指针指向指定位置的前一个节点:
newNode.Next = currentNode; //步骤3、新节点的后去指针指向指定位置的节点
currentNode.Pre = newNode; //步骤4、指定位置节点的前驱指针指向新节点
_length++;
}
算法4:删除节点
删除双向链表分为两种算法：按照索引删除和按照值删除。按照索引删除指删除双向链表中的第n个节点，按照值删除指的是删除双向链表中节点值为指定值的节点。删除双向链表中的某个节点分为以下几种情况：
1、当环形链表只有一个节点的时候，如果第一个节点符合删除条件，直接将First和Last变量赋值为null即可First=null和Last=null。
2、当删除双向链表中第一个节点的时候，需要修改两个指针First=First.Next和First.Pre=null具体的示意图如下：
3、当删除双向链表中间节点的时候，需要修改两个指针：preNode.Next=current.Next和current.Next.Pre=preNode;具体的示意图如下： 
4、删除尾部节点就比较简单了，修改两个指针:Last=Last.pre和Last.next=null；具体的示意图如下：
按照索引删除的具体代码如下：
public void DeleteByIndex(int index)
{
//删除第一个节点
if (index == 1)
{
if (_length == 1)//只有一个节点
{
first = null;
last = null;
_length--;
return;
}
//有多个节点
first = first.Next;
first.Pre = null;
_length--;
return;
}
//删除最后一个节点
if (index == _length)
{
last = last.Pre;
last.Next = null;
_length--;
return;
}
//删除中间节点
DoubleNode currentNode = first;
DoubleNode preNode = null;
int i = 1;
//找到第i个节点
while (i != index)
{
preNode = currentNode;
currentNode = currentNode.Next;
i++;
}
preNode.Next = currentNode.Next;
currentNode.Next.Pre = preNode;
_length--;
}
按照值删除的具体代码如下：
public void DeleteByValue(int data)
{
if (first == null)
{
return;
}
DoubleNode currentNode = first;
DoubleNode pre = null;
while (currentNode != null && currentNode.Data != data)
{
pre = currentNode;
currentNode = currentNode.Next;
}
//没有找到要删除的节点
if (currentNode == null)
{
return;
}
//删除头节点
if (currentNode == first)
{
if (_length == 1)
{
first = null;
last = null;
_length--;
return;
}
first = first.Next;
first.Pre = null;
_length--;
return;
}
//删除尾节点
if (currentNode == last)
{
last = last.Pre;
last.Next = null;
_length--;
return;
}
//删除中间节点
pre.Next = currentNode.Next;
currentNode.Next.Pre = pre;
_length--;
}
其他算法
除了上面几个主要的算法之外，双向链表也有获取链表长度、清空链表、链表是否为空、链表反转、链表合并等算法，这里就不给给大家一一实现了，大家可以自行实现。
示例代码地址
https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/04DoubleLinkedList.cs
总结
单链表有的优势，双向链表都有，并且循环链表可以从两个方向遍历。方便了链表的查询。缺点是需要 增加额外的指针域，占用更多的内存空间。
