双向链表
●/*线性表的双向链表存储结构*/
typedef struct DulNode
{
ElemType data;
struct DulNode *prior;
struct DulNode *next;
} DulNode, *DulLinkList;
●带头结点的循环双向链表的空链表如下图:
●带头结点的循环双向链表的非空链表如下图:
●对于双向链表中的某一个节点p,它的后继的前驱是自己,前驱的后继也是自己,即:
p->next->prior = p->prior->next
●双向链表的插入操作
假设存储元素e的结点为s,要将结点s插到结点p和p->next之间,可以这么做:
①s->prior = p; /*把p赋给s的前驱*/
②s->next = p->next; /*把p->next赋给s的后继*/
③p->next->prior = s; /*把s赋给p->next的前驱*/
④p->next = s; /*把s赋给p的后继*/
注:④必须在②③之后,因为②③使用了p->next。
●双向链表的删除操作
删除结点p可以如下做:
p->prior->next = p->next; /*把p->next赋给p->prior的后继*/
p->next->prior = p->prior; /*把p->prior赋给p->next的前驱*/
free (p); /*释放结点*/