Tim的资源站

单链表的结点中只有一个指向其后继结点的指针域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 的前面，插入示意图如下图所示：

双向链表中的结点插入：

操作如下：

1. s->prior = p->prior;

2. p->prior->next = s;

3. s->next = p;

4. p->prior = s;

指针操作的顺序不是唯一的，但也不是任意的。操作 1 必须放到操作 4 的前面完成，否则，*p的前驱结点的指针就丢掉了。把每条指针操作的含义搞清楚，就不难理解了。

三、双向链表中结点的删除

设 p 指向双向链表中某结点，删除*p。操作示意图如下所示。

双向链表中的结点删除：

操作如下：

1. p->prior->next = p->next;

2. p->next->prior = p->prior;

3. delete p;