双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后继节点和直接前驱节点，如图1-5所示。所以，从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点。

 

（1）双向链表的基本运算

1）插入：在双向链表的第i个元素前插入一个新节点的时候，首先，找到待插入的位置，用指针p指向该节点；然后，将新节点的前驱指针指向p节点的前一个节点；之后，将p节点的前一个节点的后驱指针指向新的节点；接下来，将新节点的后驱指针指向p节点；最后，将p节点的前驱指针指向新节点。

2）删除：在双向链表中删除一个节点时，可用指针p指向该节点。首先，将p节点的前一个节点的Next指向p节点的下一个节点；然后，将p的下一个节点的前驱指针指向p的上一个节点。

（2）双链表的结构及其基本运算

在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个节点的处理必须单独考虑，使空表与非空表的运算不统一。

因此，可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存储空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。从单链表可知，最后一个节点的指针域为NULL，表示单链表已经结束。如果将单链表最后一个节点的指针域改为存放链表中头节点（或第一个节点）的地址，就使得整个链表构成一个环，又没有增加额外的存储空间，而满足这样条件的链表叫循环链表。

循环链表具有以下两个特点：

1）在循环链表中增加了一个表头节点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的节点。循环链表的头指针指向表头节点。

2）循环链表中最后一个节点的指针域不是空，而是指向表头节点。即在循环链表中，所有节点的指针构成了一个环状链。

在循环链表中，只要指出表中任何一个节点的位置，就可以从它出发访问到表中其他所有的节点，而线性单链表做不到这一点。

由于在循环链表中设置了一个表头节点，因此，在任何情况下，循环链表中至少有一个节点存在，从而使空表的运算与非空表统一。