【数据结构】链表的基本操作

1.单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数元素。
单链表结点结构如下图1.1所示，其中data为数据域，用来存放数据元素；next为指针域，存放其后继结点的地址。

单链表中结点类型描述如下：

typedef struct LNode{ //定义单链表结点类型
	ElemType data; //数据域
	LNode *next; //指针域 
} *LinkList;
1
2
3
4

通常利用头指针来标识一个单链表，如单链表L，头指针为NULL是表示一个空表。此外，为了操作上的方便，在单链表第一个节点之前附加一个结点，称为头结点。头结点的数据域可以不存放任何信息。如图1.2所示。

2.单链表上的基本操作

2.1采用头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后新结点插入到当前链表的表头，即头结点之后。如图1.3所示。

头插法建立单链表的算法如下：

LinkList HairInsert(LinkList &L,int n){  //n为所要创建链表的长度
	L = new LNode;  //创建头结点 
	L->next = NULL;  //初始化为空链表
	LinkList p;
	int x;
	for(int i = 0;i<n;i++){
		p = new LNode; // 创建新节点
		cin >> x; //输入结点的值
		p->data = x;
		p->next = L->next;  //将新结点插入表中
		L->next = p;
	}
	return L; 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意：采用头插法建立单链表时，读入数据的顺序与生成链表中的元素的顺序生成是相反的。该算法的时时间复杂度为O(n)。

2.2采用尾插法建立单链表

头插法建立单链表的算法虽然简单，但生成链表中的结点的次序和输入数据的顺序不一致。而尾插法解决了这种问题，该方法将新结点插入到当前链表的表尾，所以必须增加一个尾指针r，使其始终指向当前链表的表尾,如图1.4所示。

尾插法建单链表的算法如下：

LinkList TailInsert(LinkList &L,int n){//n为所要创建链表的长度
	L = new LNode; // 创建头结点
	LNode *p,*r; // 其中r为尾指针
	r = L;
	ElemType x;
	for(int i = 0;i<n;i++){
		p = new LNode;  //创建新节点
		cin >> x;
		p->data = x;
		r->next = p;
		r = p; 
	} 
	r->next = NULL;
	return L;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意：尾插法的时间复杂度与头插法相同

2.3按序号查找结点数据

在单链表中从第一个结点出发，顺指针next域逐个网下搜索，直到找到第i个结点为止，否则返回最后一个指针域NULL.

按序查找的算法如下：

LNode *GetElem(LinkList &L,int i){  /*这里需要注意的是，因为用LNode 创建的头结点，
所以返回类型应为LNode(为指针类型)，而不是LinkList  */
	LinkList p;
	p = L->next; //让指针p指向第一个节点
	int j = 1; //从第一个节点开始计数 
	//判断i的合法性 
	if(i<0) return NULL;
	if(i == 0) return L;
	while(p&&j<i){
		p = p->next;
		j++;
	}
	return p;  //返回指向第i个结点的指针，若i大于表长，则返回NULL
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意：按序查找的时间复杂度为O(n)。

2.4按值查找表结点

从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该节点的指针；若整个单链表中没有这样的结点，则返回NULL.

按值查找的算法如下：

int LocateList(LinkList &L,ElemType e){
	LinkList p;
	p = L->next; //还是从第一个节点开始查找
	int j=1;
	while(p&&p->data!=e){  //从第i个结点开始查找data域为e的结点
		p = p->next;
		j++;
	} 
	return j;
} 
1
2
3
4
5
6
7
8
9
10

注意：按值查找操作的时间复杂度为O(n)。

2.5插入节点操作

插入结点操作将值为x的新结点插入到单链表的第i
个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱节点，即第i-1个结点，再往后插入新节点。算法首先调用按序号查找算法GetElem(L，i-1)，查找第i-1个结点。设返回第i-1个结点为*p ,然后令新节点 *s的指针域指向 *p的后继节点，然后在令结点 *p的指针域指向新插入的结点 *s。如图1.5所示。

插入节点操作的算法如下：

LinkList InsertList(LinkList &L,int i,ElemType e){ //在第i个位置上插入元素e 
	LNode *p;
	LinkList s;
	p = GetElem(L,i-1);//获取第i个位置的前驱节点，并被p所指
	s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return L;
}
1
2
3
4
5
6
7
8
9
10

注意：由于要调用查找算法GetElem(L，i-1)查找第查找第i-1个元素，所以该算法的时间复杂度为O(n)。

2.6删除节点操作

删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性，后查找表中第i-1个结点，即被删除结点的前驱结点，再将其删除。假设结点*p 为找到的被删除结点的前驱结点，要实现删除操作，仅需修改 *p的指针域，即将 *p的指针域next指向 *q的下一结点（或者 *p的指针域next直接指向 *q的下一结点)。如图1.6所示。

删除操作的算法如下：

LinkList DeleteList(LinkList &L,int i){
	LNode *p; //标记指针
	p = GetElem(L,i-1);
	p->next = p->next->next;
	return L;
}
1
2
3
4
5
6

注意：和插入算法一样，该算法的主要时间也在耗费在查找操作上，故时间复杂度为O(n)。

3.代码演示

#include<iostream>
#include<algorithm>
#define ElemType int
using namespace std;
typedef struct LNode{
	ElemType data; //数据域
	LNode *next; //指针域 
} *LinkList;
//链表的初始化
void IniteList(LinkList &L){
	L = new LNode; //创建头结点 
	L->next = NULL;  //将头结点的指针域置空 
} 
//头插法创建单链表
LinkList HairInsert(LinkList &L,int n){
	L = new LNode;  //创建头结点 
	L->next = NULL;
	LinkList p;
	int x;
	for(int i = 0;i<n;i++){
		p = new LNode; // 创建新节点
		cin >> x;
		p->data = x;
		p->next = L->next;
		L->next = p;
	}
	return L; 
} 
//尾插法创建单链表
LinkList TailInsert(LinkList &L,int n){
	L = new LNode; // 创建头结点
	LNode *p,*r; // 其中r为尾指针
	r = L;
	ElemType x;
	for(int i = 0;i<n;i++){
		p = new LNode;  //创建新节点
		cin >> x;
		p->data = x;
		r->next = p;
		r = p; 
	} 
	r->next = NULL;
	return L;
} 
//按序查找操作
LNode *GetElem(LinkList &L,int i){  /*这里需要注意的是，因为用LNode 创建的头结点，
所以返回类型应为LNode(为指针类型)，而不是LinkList  */
	LinkList p;
	p = L->next; //让指针p指向第一个节点
	int j = 1; //从第一个节点开始计数 
	//判断i的合法性 
	if(i<0) return NULL;
	if(i == 0) return L;
	while(p&&j<i){
		p = p->next;
		j++;
	}
	return p;
} 
//按值查找操作
int LocateList(LinkList &L,ElemType e){
	LinkList p;
	p = L->next; //还是从第一个节点开始查找
	int j=1;
	while(p&&p->data!=e){
		p = p->next;
		j++;
	} 
	return j;
} 
//链表的插入操作
LinkList InsertList(LinkList &L,int i,ElemType e){ //在第i个位置上插入元素e 
	LNode *p;
	LinkList s;
	p = GetElem(L,i-1);//获取第i个位置的前驱节点，并被p所指
	s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return L;
}
//链表的删除操作
LinkList DeleteList(LinkList &L,int i){
	LNode *p; //标记指针
	p = GetElem(L,i-1);
	p->next = p->next->next;
	return L;
}
//打印输出链表中的值
void PrinteList(LinkList &L){
	LNode *p;
	p = L->next; //让p指向第一个节点
	cout << "当前链表中的元素为：";
	while(p){
		cout << p->data << " ";
		p = p->next; // 让p指向下一节点 
	} 
	cout << endl;
} 
//头插法 
void Hair(LinkList &L){
	int n;
	cout << "请输入创建链表的长度：";
	cin >> n;
	HairInsert(L,n);
	cout << "头插法建立"; 
	PrinteList(L);
}  
//尾插法
 void Tail(LinkList &L){
	int n;
	cout << "请输入创建链表的长度：";
	cin >> n;
	TailInsert(L,n);
	cout << "尾插法建立";
	PrinteList(L);
}  
//按序查找
void Get(LinkList &L){
	int i;
	cout << "请输入要查找的位置：";
	cin >> i;
	LNode *p; //标记指针 
	p = GetElem(L,i);
	cout << "链表中第" << i << "个位置的元素为" << p->data << endl;  
} 
//按值查找
void  Locate(LinkList &L){
	ElemType e;
	cout << "请输入要查找的值：";
	cin >> e;
	cout << e << "在链表中的位置为:" << LocateList(L,e) << endl;
}
//插入
void Insert(LinkList &L){
	int i;
	ElemType e;
	cout << "请输入插入的位置和所插元素：";
	cin >> i >> e;
	InsertList(L,i,e); 
	cout << "插入后";
	PrinteList(L);
} 
//删除
void Delete(LinkList &L){
	int i;
	cout << "请输入要删除的位置：";
	cin >> i;
	DeleteList(L,i);
	cout << "删除后";
	PrinteList(L); 
} 
int main(){
	LinkList L;
	cout << "----------------1.链表的初始化        "<<  "2.头插法建立单链表------------------\n";
	cout << "----------------3.尾插法建立单链表    " << "4.按序查找--------------------------\n";
	cout << "----------------5.按值查找            " << "6.链表的插入操作--------------------\n";
	cout << "----------------7.链表的删除操作      " << "8.打印链表--------------------------\n" ;
	int i;
	cout << "请输入您所选择的操作：";
	for(int j=0;j<8;j++){
		cin >> i;
		switch(i){
		case 1: IniteList(L); break;
		case 2: Hair(L); break;
		case 3: Tail(L); break;
		case 4: Get(L); break;
		case 5: Locate(L); break;
		case 6: Insert(L); break;
		case 7: Delete(L); break;
		case 8: PrinteList(L); break; 
	}
	}
	return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175

4.编译结果

总结：单链表的基本操作就写到这了，如果觉得有帮助，还请麻烦您的小手支持一下博主哦，谢谢！！由于水平有限，如有问题，欢迎评论区留言。