数据结构之单链表基本运算的实现[12]

双向链表结点的定义如下

typedef struct node{

DataType data;

struct node *prior *next;

}DuNode*DLinkList;

和单链表类似双向链表也有几种变形形式图给出了带头结点的双向链表示意图链表中存在从头到尾和从尾到头的两条链;图给出了带头结点的双向循环链表示意图链表中存在两个环

显然通过某结点的指针p可以直接得到它的后继结点的指针p>next也可以直接得到它的前驱结点的指针p>prior这样在有些需要查找前驱的操作中时间效率大大提高

设p指向双向循环链表中的某一结点即p是该结点的指针则p>prior>next表示的是*p结点之前驱结点的后继结点的指针即与p相等;类似p>next>prior表示的是*p结点之后继结点的前驱结点的指针也与p相等所以有以下等式

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

双向链表中结点的插入设p指向双向链表中某结点s指向待插入的值为x的新结点将*s插入到*p的前面插入示意图如图所示

图 双向链表中的结点插入

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []