下载掌阅APP，畅读海量书库
立即打开
前面的链表只有一个指向后继元素的引用，我们可以很方便地找到某元素的后继，但是要找到其前驱结点并不容易，要解决这一问题，就要使用双链表。
双向链表也称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。双链表的结点示意图如图2.21所示。
图2.21 双向链表结点
所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，如图2.22所示。
图2.22 带头结点的双向链表
双向链表的结点定义如下：
根据图2.1所示的学生表链式存储结构对应的双链表，实现对该表中数据元素的插入、删除等运算。
双链表的查找操作和单链表基本一样，可以用单链表的查找操作代替双链表的查找操作，具体参见单链表对应部分。
在双链表中某位置插入新结点，有以下3 个操作步骤：
（1）找到插入前位置，如存在则继续，否则结束。
（2）申请、填装新结点。
（3）插入新结点，结束。
【例2.7】在学生双链表中第3 个位置前插入新结点node。
要在第3 个位置前插入新结点node，先找到a 2 结点位置p，再申请新结点node，执行下面4 步指针改变操作：① p->next->prev=node；② node->next=p->next；③ p->next=node；④ node->prev=p；从而插入新结点，如图2.23所示。
图2.23 双向链表插入结点操作
插入链表的第i个位置的数据元素，其中head为链表头结点，node为要插入的数据结点，curlen为表的长度，则插入操作流程图如图2.24所示。
图2.24 双链表插入操作流程图
在双链表中删除某位置的结点，有以下三个操作步骤：
（1）找到删除结点直接前驱对应的位置，若存在则继续，否则结束。
（2）若要删除的结点存在则继续，否则结束。
（3）删除对应位置的结点，结束。
【例2.8】在学生双链表中删除第2 个位置的结点。
要删除第2 个位置的结点，先找到a 1 结点位置p，在p所指结点的下一结点存在的情况下，执行下面两步指针改变操作：① p->next->next->prev=p; ② p->next=p->next->next;从而删除结点a 2 ，如图2.25所示。
图2.25 双向链表删除结点操作
删除链表的第i个位置的数据元素，其中curlen为链表的长度，则删除操作流程图如图2.26所示。
在上面插入代码的基础上，增加删除函数Node* delete(int i) ，实现双链表的删除功能，具体如下：
图2.26 双向链表删除结点操作流程图
