双向链表结构

单链表的结点中只有一个指向其后继结点的指针域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;

用户头像
登录后发表评论