单链表的结点中只有一个指向其后继结点的指针域next,因此若已知某结点的指针为p,其后继结点的指针则为p->next,而找其前驱则只能从该链表的头指针开始,顺着各结点的next域进行。
也就是说,找后继的时间复杂度是 O(1),找前驱的时间复杂度是 O(n)。如果也希望找前驱的时间复杂度达到 O(1),则只能付出空间的代价:每个结点再加一个指向前驱的指针域,结点的结构如下图所示。用这种结点组成的链表称为双向链表。
双向链表结点的结构:
一、双向链表结点的定义
typedef int DataType;
class DualItem {
public:
DataType data;
DualItem *next;
DualItem *prior;
DualItem(){
next = NULL;
prior = NULL;
}
}
和单链表类似,双向链表通常也是用头指针标识,也可以带空白头结点和做成循环结构。下图是带头结点的双向循环链表示意图。显然,通过某结点的指针 p 既可以直接得到它的后继结点的指针 p->next,也可以直接得到它的前驱结点的指针 p->prior。这样在有些操作中需要找前驱结点时,无须再用循环。从下面的插入删除运算中,可以看到这一点。
带头结点的双向循环链表:
设 p 指向双向循环链表中的某一结点,即 p 是该结点的指针,则 p->prior->next 表示的是*p
结点的前驱结点的后继结点的指针,即与 p 相等;类似,p->next->prior 表示的是*p
结点的后继结点的前驱结点的指针,也与 p 相等。所以有等式:p->prior->next = p = p->next->prior
。
二、双向链表中结点的插入
设 p 指向双向链表中某结点,s 指向待插入的值为 x 的新结点,将s 插入p 的前面,插入示意图如下图所示:
双向链表中的结点插入:
操作如下:
-
s->prior = p->prior
; -
p->prior->next = s;
-
s->next = p;
-
p->prior = s;
指针操作的顺序不是唯一的,但也不是任意的。操作 1 必须放到操作 4 的前面完成,否则,*p
的前驱结点的指针就丢掉了。把每条指针操作的含义搞清楚,就不难理解了。
三、双向链表中结点的删除
设 p 指向双向链表中某结点,删除*p
。操作示意图如下所示。
双向链表中的结点删除:
操作如下:
-
p->prior->next = p->next;
-
p->next->prior = p->prior;
-
delete p;