单链表的建立(头插法、尾插法)(数据结构与算法)

如果要把很多个数据元素存到一个单链表中，如何操作？
1.初始化一个单链表
2. 每次取一个数据元素，插入到表尾/表头

1. 尾插法建立单链表

尾插法建立的单链表元素顺序与输入数据集合的顺序相同，即按照输入数据的顺序排列。

使用尾插法建立单链表的一个常见应用是在计算机科学中进行数据输入。通过将用户输入的数据逐个添加到链表的尾部，可以方便地保存输入的数据，并在后续处理中使用。

1. 初始化单链表
2. 设置变量length纪录链表长度
3. while循环｛
4. 每取一个元素e；
5. ListInsert(L, length+1， e) 插入到尾部；
6. length++；｝
   

尾插法（尾部插入法）是一种建立单链表的常用方法，与头插法相反，它会将新节点插入到链表的尾部位置。以下是使用尾插法建立单链表的步骤：

1. 首先定义一个头节点，并将其初始化为空指针。
2. 遍历需要转化为链表的数据集合。
3. 对于数据集合中的每一个元素，创建一个新的节点，并设置其数据域为该元素的值。
4. 若链表为空，将新节点直接设置为头节点。
5. 若链表非空，则遍历到链表的最后一个节点，并将其指针域指向新节点。
6. 更新链表的最后一个节点为新节点。

typedef struct LNode      //定义单链表结点类型
{
	ElemType data;		  //每个结点存放一个数据元素
	struct LNode *next;   //指针指向下一个节点
}
//初始化一个单链表(带头结点)
bool InitList(LinkList &L)  
{
	L = (LNode *)  malloc(sizeof(LNode)); //分配一个头结点
	if (L == NULL) 		 //内存不足， 分配失败
		return false;
	L->next = NULL; 		//头结点之后暂时还没有节点
	return true;	
}
void test()
{
	LinkList L;   //声明一个指向单链表的指针
	//初始化一个空表
	InitList(L);
	//......后续代码......
}

//在第i个位置处插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e)
{
	if(i<1)
		return false;
	LNode *p;		//指针p指向当前扫描到的节点
	int j = 0; 		//指针p指向的是第几个结点
	p = L;		//L指向头结点 头结点是第0个结点，不存数据
	while( p != NULL && j < i-1) //循环找到第i-1个结点
	{
		p = p->next;
		j++;
	}
	if( p==NULL)	//i值不合法
		return false;
	LNode *s = (LNode *) malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;		//将结点s连到p之后
	return true;		//插入成功
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

当插入1个元素时，while需要循环一次，插入2个元素，while循环1此…插入n个元素，while循环n-1次。 每次都从开头开始之后遍历，循环次数为1+2+3+…+(n-1)。时间复杂度为0(n^2)

这种操作，时间复杂度太大，并不是最佳方案。

其实根本没必要每次都从头开始往后寻找， 我们可以设置一个指针r，指向表尾，当要在尾部插入一个新的数据元素时，就只需要对r结点做一个后插操作就行了。

//后插操作： 在p结点之后插入元素e
bool InsertNode(LNode *p, ElemType e)
{
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s==NULL)		//内存分配失败
		return false;
	s->data = e;		//用结点s保存数据元素
	s->next = p->next;   
	p->next = s; 		//将结点s连到p之后    后插操作
	return true;				
}
1
2
3
4
5
6
7
8
9
10
11
12
13

插入数据元素40

尾部插入一个元素，表尾指针后移一位，仍然指向最后一个元素,方便下一次插入

示例：尾插法建立单链表

设此次输入的整数是10，while循环检测，循环中前两句，会申请一个新的结点，然后让s这个指针指向新结点，并且把输入的x = 10放入新结点中，接下来把 r结点的next指针指向s结点。最后，再让r指针指向s结点，接下来就可以输入下一个元素x，继续插入。

时间复杂度：O(n)

LinkList List_TailInsert(LinkList &L)
{
	int x;		//设ElemType为整型
	L = (LinkList)malloc(sizeof(LNode));	//建立头结点
	LNode *s, *r = L;	//r为表尾指针
	scanf("%d", &x);	//输入结点的值
	while(x != 9999)    //该数是随便取的 ，输入9999表示结束
	{
		s = (LNode *) malloc(sizeof(LNode));  //简历一个结点s
		s->data = x; 	//将x存放到s数据域中
		r->next = s; //将表尾指针指向s结点
		r = s;	//r指向新的表尾结点
		scanf("%d",&x);
	}
	r->next = NULL; 	//尾结点指针置空
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LNode *s, *r = L; //r为表尾指针

申请一个新的结点，然后让s这个指针指向新结点，并且把输入的x = 10放入新结点中

接下来把 r 结点的next指针指向s结点

最后，再让r指针指向s结点, 接下来就可以输入下一个元素x，继续插入

假设继续输入 x = 16。那么会再申请一个新的结点s，让s指针指向新节点， 并把16放入新结点， 接下来把r结点的指针指向s结点， 最后…

将 r 指针指向s结点，再输入下一个元素27 。 以此类推完成插入操作。

如果x输入的是9999， 那么就可以跳过while循环，执行r->next = NULL; 让r结点的next指向NULL。

2. 头插法建立单链表

头插法建立单链表的特点是：新节点插入到链表的头部位置，因此建立完成的链表元素顺序是和输入数据集合的顺序相反的，即倒序排列。

对头结点的后插操作，如下图所示：

1. 首先定义一个头节点，并将其初始化为空指针。
2. 遍历需要转化为链表的数据集合。
3. 对于数据集合中的每一个元素，创建一个新的节点，并设置其数据域为该元素的值。
4. 将新节点的指针域指向当前头节点，即将新节点插入到链表的头部。
5. 更新头节点为新节点。

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e)
{
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)	//内存分配失败
		return false;	
	s->data = e;		//用结点s保存数据元素e
	s->next = p->next;
	p->next = s;		//将结点s连接到p之后
	return true；
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 如上图所示，此处，尾插法中是没有 L->next = NULL 这一句的，但在头插法中，这句非常必要。由于是动态分配，如果头结点指向没有被初始化为NULL，那头结点L->next 很有可能指向了内存中某一神秘区域，从而形成脏数据，影响后面的插入操作。

养成好习惯，只要是初始化单链表，都先把头指针指向NULL

• 按照头插法形成的规则，最终形成的单链表刚好是输入元素的逆序，这种性质非常重要！！！
  很多题目中都用得到单链表的逆置。
  

3. 知识点回顾