用C语言实现单链表的基本操作（附有完整代码）

导语：

无论是顺序存储结构还是链式存储结构，在内存中进行存放元素的时候，不仅需要存放该元素的相关信息，还需要存放该元素和其他元素之间的关系，而我们之前所学的顺序表“与生俱来”的物理结构自然地能够表达出元素和元素之间的关系，不需要额外的信息去表达元素和元素之间的关系，而对于链式存储这种非顺序存储的结构，需要额外附加指针去表示这种关系。

单链表：

每个结点除了存放数据元素外，还要存储指向下一个节点的指针。

单链表的特点：

优点：不要求大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

定义：

typedef struct LNode {
   
	int data;
	struct LNode* next;//指针指向下一个节点，指针的类型为节点类型；
}*LinkNode;//声明*LinkNode为结构体指针类型
1
2
3
4
5

除了上述这种方法外，我们还可以先先声明LinkNode为结构体类型，在使用该类型的时候，将对应的变量定义为指针即可。

单链表分为带头结点和不带头结点，我们一般主要学习带头结点的。

初始化操作：

在所有的操作之前，我们首先需要建立一个空的单链表，那么首先需要做的就是分配头结点。

void InistLinkNode(LinkNode& L) {
   
	L = (LNode*)malloc(sizeof(LNode));//分配头结点
	L->next = NULL;
}
1
2
3
4
5

头插法：

“头插法”顾名思义就是将元素插入到头结点之后，插入一次好像和我们通常所讲的插入没什么区别，但多次这样插到头结点之后，也就是“第一个真正的节点”，那么是不是会产生一种现象，它最终的存储数据和我们所插入时的顺序是相反的。

void InsertLinkNode(LinkNode& L) {
   
	LNode* s;
	int x,Length;
	printf("请输入你要插入的元素个数：");
	scanf("%d", &Length);
	printf("请输入你要插入的元素：\n");
	for (int j = 0; j < Length; j++) {
   
		s = (LNode*)malloc(sizeof(LNode));//每插入一个元素之前，都需要给它分配节点空间
		scanf("%d", &x);
		s->data = x;
		s->next = L->next;
		L->next = s;
	}

} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

通过程序验证以下：

尾插法：

“尾插法”顾名思义就是将元素插入到表尾，也就是我们普通的插入，那么怎么要找到表尾的位置呢？在顺序表中，我们完全可以利用它顺序存储结构的天然特性，通过下标即可以找到，但是单链表是没有办法的，我们只有两种方式，要么循环遍历，要么尝试在表尾的地方做个标记。

那么那种方法是好的呢？

答案是第二种！循环遍历的方式，如果只插入一个元素看似没什么问题，但如果多次的重复遍历循环无疑增加了时间复杂度，这显然不是好的方法。

第二个方法就不存在时间复杂度的问题，只需要在表尾位置做个标记，使它永远指向表尾即可。

void TailInsertLinkNode(LinkNode& L) {
   
	LNode* s,*r;
	int x,Length;
	r = L;//r为表尾指针
	printf("请输入你要插入的元素个数：");
	scanf("%d", &Length);
	printf("请输入你要插入的元素：\n");
	for (int j = 0; j < Length; j++) {
   
		s = (LNode*)malloc(sizeof(LNode))
1
2
3
4
5
6
7
8
9
10