2.6.2　双向链表的插入和删除操作

在双向链表中，有些操作如求链表的长度、查找链表的第i个结点等，仅涉及一个方向的指针，与单链表中的算法实现基本没什么区别，而对于双向链表的插入和删除操作，涉及前驱结点和后继结点的指针，因此需要修改两个方向上的指针。

1．在第i个位置插入元素值为e的结点

首先找到第i个结点，用p指向该结点；再申请一个新结点，由s指向该结点，将e放入数据域；然后修改p和s指向的结点的指针域，修改s的prior域，使其指向p的直接前驱结点，即s->prior=p->prior；修改p的直接前驱结点的next域，使其指向s指向的结点，即p->prior->next=s；修改s的next域，使其指向p指向的结点，即s->next=p；修改p的prior域，使其指向s指向的结点，即p->prior=s。插入操作指针修改情况如图2-28所示。

图2-28　双向循环链表的插入结点操作过程

插入操作算法实现如下：

2．删除第i个结点

首先找到第i个结点，用p指向该结点；然后修改p指向的结点的直接前驱结点和直接后继结点的指针域，从而将p与链表断开。将p指向的结点与链表断开需要两步，第一步，修改p的前驱结点的next域，使其指向p的直接后继结点，即p->prior->next=p->next；第二步，修改p的直接后继结点的prior域，使其指向p的直接前驱结点，即p->next->prior=p->prior。删除操作指针修改情况如图2-29所示。

图2-29　双向循环链表的删除结点操作过程

删除操作算法实现如下：

插入和删除操作的时间耗费主要在查找结点上，两者的时间复杂度都为O（n）。