【数据结构-单链表】_数据结构单链

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

为什么需要单链表？
因为顺序表在插入和删除元素时，需要移动大量的元素，影响了运行效率，因此引入了单链表（链式存储方式）。

---

一、什么是单链表？

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

二、单链表有哪些特性？

1. 不需要连续的存储空间；
2. 单链表是非随机的存储结构， 即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找；
3. 一般单链表分为带头结点单链表和不带头结点的单链表；
4. 单链表中每个结点包括：数据域+指针域。

二、头结点

1.什么是头结点？

在通常情况下，为了方便操作单链表，会在单链表的第一个带元素的结点之前附加一个结点，这个结点称为头结点。

1.头结点有哪些特性？

1. 如果带头结点，那么单链表中的第一个结点就是头结点；
2. 头结点和其他结点没什么特殊的区别，只是头结点的数据域不存任何数据信息，若有需要，有时可以用来记录表长等信息；头结点的指针域指向的是单链表中第一个带有元素的结点。

三、头指针

1.什么是头指针？

不管单链表带不带头结点，头指针始终指向单链表的第一个结点，即头指针里保存的是第一个结点的地址。换言之，如果单链表不带头结点，此时头指针指向的是单链表中第一个带有数据元素的结点（称为首元结点）；反之如果单链表带头结点，此时头指针指向的是单链表中的头结点（因为：在此情况下，头结点为单链表中的第一个结点）

注意：单链表中可以没有头结点，但是不能没有头指针！

四、单链表的操作

结构化

1.定义结点结构

//定义结点结构
typedef struct LNode
{
   
	int data;
	struct LNode* next;
}LNode;
1
2
3
4
5
6
7

2.创建链表

//创建链表，用头结点代表一个链表（此处也相当于初始化了一个链表）
LNode* creatList() {
   
	LNode* headNode = (LNode*)malloc(sizeof(LNode));
	headNode->data = -1; //头结点的数据域可以不存任何值，也可以存链表的长度
	headNode->next = NULL;
	return headNode;
}
1
2
3
4
5
6
7
8

3.创建结点

LNode* createList(int data) {
   
	LNode* newNode = (LNode*)malloc(sizeof(LNode));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}
1
2
3
4
5
6
7

4.头插法(将新的结点插入到链表中)

void InsertListByHead(LNode* List,int data) {
   
	LNode* newNode = createList(data); //创建一个新的结点
	newNode->next = List->next;
	List->next = newNode;
}
1
2
3
4
5
6

5.尾插法(将新的结点插入到链表中)

void InsertListByTail(LNode* List,int data) {
   
	while (List->next)
	{
   
		List = List->next;
	}
	LNode* newNode = createList(data); //创建一个新的结点
	List->next = newNode;
	newNode->next = NU
1
2
3
4
5
6
7
8
9