带头结点单链表与不带头结点单链表的区别

目录

• 不带头结点的操作
• 代码①
• 代码②
• 代码③
• 代码④
• 带头结点的操作
• 代码⑤

链表作为一种基本数据结构，常用的链表分为带结点和不带头结点。从线性表的定义可以知道，线性表允许在任意位置进行插入和删除。所有的链表都有一个头指针head，带头结点的链表中head的数据项为空，而不带头的链表直接在头结点存入数据，那么当从头插入数据时，head需要时刻变化。

接下来具体分析：

1.带头结点的链表的插入，使用一个临时变量p等于插入之前的结点（不管具体插入位置），之后不论要插入的结点x是插到链表头还是插入到链表其他位置都是如下语句：

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

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

x->next=head;
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的值。所以一般单链表一般带有头结点。

下面是其它的补充

下面的代码中，传递链表时，传的是头指针。如果是带头结点的链表，传递链表时，可以传头结点，具体可以看看 C语言实现-线性表的链式存储(单链表)

带头结点单链表 和 不带头结点单链表的区别：

• 带头结点单链表，在进行插入、删除操作时，不需要改变链表头指针。

• 不带头结点的单链表，在进行插入、删除操作时，可能会涉及到链表头指针的修改（所以链表作为参数传递时，传递的是头指针的引用，具体可看代码④中head_insert方法中的指针变量带了&取地址符，而代码⑤中的没有。因为带头结点单链表进行头插操作不需要修改头指针，而不带头结点的单链表进行头插操作时需要修改头指针）

• 具体的代码也有些许差异，可对比 代码④ 和 代码⑤

带头结点单链表 和 不带头结点的init()初始化都修改了头指针，所以指针变量带了&取地址符

不带头结点的操作

① ② ③ ④ 四组代码本质是一样的。只是我本人对地址、指针、引用、指针变量概念不是很理解，所以才写了这四组代码进行对比，方便自己以后复习理解。读者可以跳过① ② ③，直接看④的代码即可

代码①

#include <stdio.h>
#include <malloc.h>
typedef struct LNode {
	int data;
	struct LNode *next;
};
void init(LNode **L) {
	*L = NULL;
}
void head_insert(LNode **L, int x) {
	LNode *newP = (LNode *)malloc(sizeof(LNode));
	newP->data = x;
	newP->next = *L;
	*L = newP;
}
LNode *get(LNode *L, int k) {
	if (k < 1) {
		printf("查找位置非法！");
		return NULL;
	}
	int i = 1;
	if (L != NULL && i <= k) {
		L = L->next;
		i++;
	}
	if (i == k) {
		return L;
	}
	printf("查找位置非法！");
	return NULL;
}
void print(LNode *L) {
	printf("\n");
	while (L) {
		printf("%4d ", L->data);
		L = L->next;
	}
	printf("\n");
}
int main() {
	LNode *L;
	init(&L);
	head_insert(&L, 15);
	head_insert(&L, 25);
	head_insert(&L, 35);
	print(L);
	printf("\n%4d \n", get(L, 2)->data);
	return 0;
}

代码②

#include <stdio.h>
#include <malloc.h>
typedef struct LNode {
	int data;
	struct LNode *next;
};
void init(LNode *&L) {
	L = NULL;
}
void head_insert(LNode *&L, int x) {
	LNode *newP = (LNode *)malloc(sizeof(LNode));
	newP->data = x;
	newP->next = L;
	L = newP;
}
LNode *get(LNode *L, int k) {
	if (k < 1) {
		printf("查找位置非法！");
		return NULL;
	}
	int i = 1;
	if (L != NULL && i <= k) {
		L = L->next;
		i++;
	}
	if (i == k) {
		return L;
	}
	printf("查找位置非法！");
	return NULL;
}
void print(LNode *L) {
	printf("\n");
	while (L) {
		printf("%4d ", L->data);
		L = L->next;
	}
	printf("\n");
}
int main() {
	LNode *L;
	init(L);
	head_insert(L, 15);
	head_insert(L, 25);
	head_insert(L, 35);
	print(L);
	printf("\n%4d \n", get(L, 2)->data);
	return 0;
}

代码③

#include <stdio.h>
#include <malloc.h>
typedef struct LNode {
	int data;
	struct LNode *next;
}*LinkList;
void init(LinkList *L) {
	*L = NULL;
}
void head_insert(LinkList *L, int x) {
	LinkList newP = (LinkList)malloc(sizeof(LNode));
	newP->data = x;
	newP->next = *L;
	*L = newP;
}
LinkList get(LinkList L, int k) {
	if (k < 1) {
		printf("查找位置非法！");
		return NULL;
	}
	int i = 1;
	if (L != NULL && i <= k) {
		L = L->next;
		i++;
	}
	if (i == k) {
		return L;
	}
	printf("查找位置非法！");
	return NULL;
}
void print(LinkList L) {
	printf("\n");
	while (L) {
		printf("%4d ", L->data);
		L = L->next;
	}
	printf("\n");
}
int main() {
	LinkList L;
	init(&L);
	head_insert(&L, 15);
	head_insert(&L, 25);
	head_insert(&L, 35);
	print(L);
	printf("\n%4d \n", get(L, 2)->data);
	return 0;
}

代码④

#include <stdio.h>
#include <malloc.h>
//结构体
typedef struct LNode {
	int data;
	struct LNode *next;
} *LinkList;
//初始化
void init(LinkList &L) {
	L = NULL;
}
//头插
void head_insert(LinkList &L, int x) {
	LinkList newP = (LinkList)malloc(sizeof(LNode));
	newP->data = x;
	newP->next = L;
	L = newP;
}
//按位序查找
LinkList get(LinkList L, int k) {
	if (k < 1) {
		printf("查找位置非法！");
		return NULL;
	}
	int i = 1;
	if (L != NULL && i <= k) {
		L = L->next;
		i++;
	}
	if (i == k) {
		return L;
	}
	printf("查找位置非法！");
	return NULL;
}
//遍历输出
void print(LinkList L) {
	printf("\n");
	while (L) {
		printf("%4d ", L->data);
		L = L->next;
	}
	printf("\n");
}
int main() {
	LinkList L;
	init(L);
	head_insert(L, 15);
	head_insert(L, 25);
	head_insert(L, 35);
	print(L);
	printf("\n%4d \n", get(L, 2)->data);
	return 0;
}

带头结点的操作

代码⑤

#include <stdio.h>
#include <malloc.h>
//结构体
typedef struct LNode {
	int data;
	struct LNode *next;
} *LinkList;
//初始化
void init(LinkList &L) {
	LinkList newp = (LinkList)malloc(sizeof(LNode));
	newp->next = NULL;
	L = newp;
}
//头插
void head_insert(LinkList L, int x) {
	LinkList newp = (LinkList)malloc(sizeof(LNode));
	newp->data = x;
	newp->next = L->next;
	L->next = newp;
}
//按位序查找
LinkList get(LinkList L, int k) {
	if (k < 1) {
		printf("查找位置非法！");
		return NULL;
	}
	int i = 1;
	LinkList p = L->next;
	if (p != NULL && i <= k) {
		p = p->next;
		i++;
	}
	if (i == k) {
		return p;
	}
	printf("查找位置非法！");
	return NULL;
}
//遍历输出
void print(LinkList L) {
	printf("\n");
	LinkList p = L->next;
	while (p) {
		printf("%4d ", p->data);
		p = p->next;
	}
	printf("\n");
}
int main() {
	LinkList L;
	init(L);
	head_insert(L, 15);
	head_insert(L, 25);
	head_insert(L, 35);
	print(L);
	printf("\n%4d \n", get(L, 2)->data);
	return 0;
}