欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

链表带头结点和不带头结点带区别

程序员文章站 2024-03-21 12:57:28
...

链表作为一种基本数据结构,常用的链表分为带结点和不带头结点。从线性表的定义可以知道,线性表允许在任意位置进行插入和删除。所有的链表都有一个头指针head,带头结点的链表中head的数据项为空,而不带头的链表直接在头结点存入数据,那么当从头插入数据时,head需要时刻变化。
接下来具体分析:
1.带头结点的链表的插入,使用一个临时变量p等于插入之前的结点(不管具体插入位置),之后不论要插入的结点x是插到链表头还是插入到链表其他位置都是如下语句:

x->next=p->next;
p->next=x;

2.不带头结点的链表的插入,若要插入到链表的开头:

x->next=head->next;
head=x;  //这里不再是head->next=x;

若插到链表的其他位置:

p=插入之前的结点
x->next=p->next;
p->next=x;

3.带头结点的删除:
p是删除结点之前结点
x是要删除结点
p->next=x->next;
free(x);
同样不存在删除位置的差异。

4.不带头结点的删除:
删除第一个结点:head=head->next;这时需要改变链表的头结点。
删除其他结点时,head的值不会变。

综上所述,带头结点的单链表,不论删除和插入的位置如何,不需要修改head的值,不带头结点的单链表当头插和头删需要修改head的值。所以一般单链表一般带有头结点。

相关标签: 链表

上一篇: Prometheus

下一篇: 百度地图使用