数据结构系列----循环链表和双向链表
对于单链表,每个结点只存储了后向指针
循环链表:首尾相接的单链表
循环链表的头指针(空链表):
非空循环链表:
循环链表和单链表的主要差异:
在循环的判断条件上,单链表判断:p->next是否为空;循环链表:p->next不等于头结点,则循环没有结束
双向链表:在单链表的每个结点中,在设置一个指向前驱结点的指针
双向链表的头指针:(空链表)
非空的循环的带头结点的双向链表:
双向链表插入操作:将结点s插入p和p->next之间需要四步操作:(顺序很重要)
- s->prior=p;
- s->next=p->next;
- p->next->prior=s;
- p->next=s;
顺序:先确定s的前驱和后继;然后确定后结点的前驱,最后确定前结点的后继
双向链表的删除操作:删除p结点
- p->prior->next=p->next;//将p->next赋值给p->prior的后继
- p->next->prior=p->prior;//将p->prior赋值给p->next的前驱