学科分类
目录
数据结构

什么是双向链表

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

图1 双向链表

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

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

图2 在双链表中插入元素

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

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

点击此处
隐藏目录