数据结构之双向链表

双向链表

双向链表(double linkedlist)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。

定义:

typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior; /*直接前驱指针*/
    struct DuLNode *next; /*直接后继指针*/
} DulNode, *DuLinkList;

HakXSPmmYL.png!large

p->next->prior = p = p->prior->next

假设存储元素 e 的结点为 s,要实现将结点 s 插入到结点 p 和 p-next 之间需要下面几步:

ewoIW7iScJ.png!large

插入操作

/*把 p 赋值给 s 的前驱,如上图中①*/
s->prior = p;
/*把 p->next 赋值给 s 的后继,如上图中②*/
s->next = p->next;
/*把 s 赋值给 p->next 的前驱,如上图中③*/
p->next->prior = s;
/*把 s 赋值给 p 的后继,如图中④*/
p-next = s;

这个插入操作关键在于它们的顺序,由于第 2 步和第 3 步都用到了 p->next。如果第 4 步先执行,则会使得 p->next 提前变成了 s,使得插入的工作完不成。

顺序是先指定 s 的前驱和后继,再指定后结点的前驱,最后解决前结点的后继。

删除操作

ODNJHcsmPx.png!large

/*把 p->next 赋值给 p->prior 的后继,如图中①*/
p->prior->next = p->next;
/*把 p->prior 赋值给 p->next 的前驱,如上图中②*/
p->next->prior = p->prior;
/*释放结点*/
free(p);

双向链表相对于单链表来说,更复杂一些,毕竟它多了 prior 指针,对于插入和删除时,需要格外注意顺序。
由于双向链表每个结点都需要记录两份指针,所以再空间上占用略多一些。
不过由于双向链表良好的对称性,使得对某个结点的前后结点的操作,带来了方便,可以有效提高算法的时间性能。实际就是用空间来换时间。

ai
本作品采用《CC 协议》,转载必须注明作者和本文链接
不要试图用百米冲刺的方法完成马拉松比赛。
本帖由 Galois 于 1个月前 加精
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!