什么是双向链表

双向链表，顾名思义就是可以向两个方向走的链表。它的每一个结点有两个指针，一个指向后继结点，一个指向前驱结点。如图1所示。

图1 双向链表

图1中的双向链表，第一个结点的前驱指针pre指向了NULL，当然，读者在设计时也可以将它指向头结点；最后一个结点的后继结点next指向了NULL，这和单链表是一样的。在双向链表中，通过一个结点可以找到它的后继结点，也可以找到它的前驱结点。

双向链表在结构和算法描述上和单链表相同，只是某些算法实现比单链表复杂一些。例如，在插入元素时，需要同时修改两个方向的指针指向。以图1中的双向链表为例，在元素12与99之间插入新元素33，其过程如图2所示。

图2 在双链表中插入元素

从图2演示的过程中，可以看出，在插入元素时，需要同时修改两个方向的指针指向。同理，在删除元素时，也要修改两个指针，这里我们就不再做相应的图解演示。

前面已学习过单链表的实现过程，双向链表的实现与单链表的实现大同小异，因此在本节学习完双链表之后，读者可以试着自己来实现一下双链表的基本操作，然后再对比与本书中双向链表的实现有何异同。