数据结构之双向链表

双向链表

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

定义：

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

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

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

插入操作

/*把 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 的前驱和后继，再指定后结点的前驱，最后解决前结点的后继。

删除操作

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

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

本作品采用《CC 协议》，转载必须注明作者和本文链接