Question

双向链表，即链表节点的指针域中既含有指向前驱节点的指针，也含有指向后继节点的指针，如图 8.5 所示。

图 8.5　双向链表

在双向链表中，可以非常方便地通过一个节点来访问它的前驱节点与后继节点，其中头节点指向前驱节点的指针为空，尾节点指向后继节点的指针为空。我们既可以从头节点开始，以顺序方式遍历链表所有节点，也可以从尾节点开始，以逆序方式遍历链表所有节点。

相对于单向链表，双向链表拥有更多、更灵活的节点访问方式，但由于节点指针数量的增加，在节点之间关系的维护上会变得更加复杂。

下面用一个程序案例来展示双向链表的使用。完整的程序代码如下：

大家可以比较一下双向链表与单向链表在使用上的细微差别，尤其在删除链表节点时，要充分考虑到除了释放节点本身，还要维护好它的前驱节点与后继节点之间的关系，以及在建立节点关系时，对各指针进行修改的先后顺序。在掌握好链表节点的删除之后，大家自然也应该知道如何在链表指定位置来插入节点了，读者可自行练习。程序代码中已经给出了很细致的注释，对代码不再做过多解释。

编译运行程序，会得到如下结果：

Print all nodes of the linked list sequentially:
3 2 1 40 50 60
Print all nodes in the linked list in reverse order:
60 50 40 1 2 3
Delete the node at position 3:
Print all nodes of the linked list sequentially:
3 2 40 50 60