我们在单链表中,有了next指针,
这就使得我们要查找下一结点的时间复杂度为O(1)。
可是如果我们要查找的是上一结点的话,那最坏的时间复杂度就是O(n)了,因为我们每次都要从头开始遍历查找。
为了克服单向性这一缺点,我们的老科学家们,设计出了双向链表。
双向链表(double linkedlist)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。
/* 线性表的双向链表存储结构 */
typedef struct DulNode
{
ElemType data;
struct DuLNode *prior; /* 直接前驱指针 */
struct DuLNode *next; /* 直接后继指针 */
} DulNode, *DuLinkList;
既然单链表也可以有循环链表,那么双向链表当然也可以是循环表。
双向链表的循环带头结点的空链表如图3-14-3所示。
图3-14-3
非空的循环的带头结点的双向链表如图3-14-4所示。
图3-14-4
由于这是双向链表,那么对于链表中的某一个结点p,它的后继的前驱是谁?当然还是它自己。它的前驱的后继自然也是它自己,即:
p->next->prior = p = p->prior->next
双向链表是单链表中扩展出来的结构,
所以它的很多操作是和单链表相同的,比如求长度的ListLength,查找元素的GetElem,获得元素位置的LocateElem等,这些操作都只要涉及一个方向的指针即可,另一指针多了也不能提供什么帮助。
就像人生一样,想享乐就得先努力,欲收获就得付代价。
双向链表既然是比单链表多了如可以反向遍历查找等数据结构,那么也就需要付出一些小的代价:在插入和删除时,需要更改两个指针变量。
插入操作时,其实并不复杂,不过顺序很重要,千万不能写反了。
我们现在假设存储元素e的结点为s,要实现将结点s插入到结点p和p->next之间需要下面几步,如图3-14-5所示。
图3-14-5
/* 把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,只需要下面两步骤,如图3-14-6所示。
图3-14-6
/* 把p->next赋值给p->prior的后继,如图中① */
p->prior->next = p->next;
/* 把p->prior赋值给p->next的前驱,如图中② */
p->next->prior = p->prior;
/* 释放结点 */
free(p);
好了,简单总结一下,双向链表相对于单链表来说,要更复杂一些,毕竟它多了prior指针,对于插入和删除时,需要格外小心。
另外它由于每个结点都需要记录两份指针,所以在空间上是要占用略多一些的。不过,由于它良好的对称性,使得对某个结点的前后结点的操作,带来了方便,可以有效提高算法的时间性能。说白了,就是用空间来换时间。