数据结构之单链表基本运算的实现[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的前面 插入示意图如图 所示
图 双向链表中的结点插入
lishixinzhi/Article/program/sjjg/201311/23077