双向链表

/*线性表的双向链表存储结构*/

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); /*释放结点*/