【数据结构】单链表解析+完整代码（插入、删除、尾插法、头插法、按值和按位查找、前插和后插）带头结点和不带两种实现_单链表的插入算法数据结构

3.1 单链表

3.1.1 单链表的定义

• 定义

  线性表的链式存储。

  • 结点结构：data+next（结点自身的数据＋指向后继的指针）

  • 特点：元素分散在内存中，非随机存取的存储结构。

  • 局限性：无法逆向检索，有时不方便。（双链表可双向检索）

    

//定义单链表节点类型
typedef struct LNode{
    ElemType data; //数据域
    Struct LNode *next; //指针域，指向下一个结点
}LNode,*LinkList;
//注：
//LNode —— 强调返回的是一个结点
//LinkList —— 强调的是一个单链表
1
2
3
4
5
6
7
8

• 初始化——带头结点

  //带头结点初始化
  bool InitList(LinkList &L){
      L=(LNode*)malloc(sizeof(LNode)); //为头结点分配内存
      if(L==NULL)return false; //内存不足，分配失败
      L->next=NULL; //头结点后还没有结点
      return true;
  }
  
  //带头结点判空
  bool Empty(LinkList L){
      if(L->next==NULL)
          return true;
      else
          return false;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

• 初始化——不带头结点

  //不带头结点初始化
  bool InitList(LinkList &L){
      L=NULL;
      return true;
  }
  
  //不带头结点判空
  bool Empty(LinkList L){
      if(L==NULL)
          return true;
      else
          return false;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

• 带头结点和不带头结点的区别

  • 头结点：不存储数据，只指向链表中第一个结点的位置

  • 不带头结点，写代码麻烦。原因：

    1.带头结点后，链表第一个位置上的结点与其他位置的操作可以一致，不用特殊处理。

    2.空表和非空表的处理得到统一。

    

3.1.2 单链表的插入

A.按位序插入（带头结点）

• 将值为e的新结点插入到位置i，步骤：

  1.找到要插入的位置，即第i-1个结点；

  2.在其后插入新结点，插入步骤如图：

  

bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1)return false;
    
    LNode *p; //指针p指向当前扫描到的结点
    int j=0; //记录当前p指向第几个结点
    p=L; //初始时，L指向头结点，头结点不存数据
    
    //循环找到第i-1个结点，即要插入的位置
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)return false;//i值不合法
    
    //插入结点
    LNode *s=(LNode*)malloc(sizeof(LNode)); //为要插入的结点开辟内存
    s->data=e; //将数值复值到新结点数据域
    s->next=p->next; //将新结点和后继结点连接
    p->next=s; //将新结点和前驱连接
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 时间复杂度：$O(n)$

B.按位序插入（不带头结点）

• 在非第一个插入时，与带头结点相同。但插入第一位时不同，当在第一位插入时要重新赋值头结点。

• 即在带头结点插入的基础上，插入以下一段即可：

  

bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1)return false;
    
    //插入第1个结点的操作与其它结点不同
    if(i==1){
        LNode *s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s; //头指针指向新结点
        return true;
    }
    
    LNode *p; //指针p指向当前扫描到的结点
    int j=0; //记录当前p指向第几个结点
    p=L; //初始时，L指向头结点，头结点不存数据
    
    //循环找到第i-1个结点，即要插入的位置
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)return false;//i值不合法
    
    //插入结点
    LNode *s=(LNode*)malloc(sizeof(LNode)); //为要插入的结点开辟内存
    s->data=e; //将数值复值到新结点数据域
    s->next=p->next; //将新结点和后继结点连接
    p->next=s; //将新结点和前驱连接
    
    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

• 时间复杂度：$O(n)$
• 后续不做特殊说明，则默认为带头结点。

C.指定结点的后插操作

• 即在指定结点p后，插入元素e。

  相当于在按位序插入的基础上，省去循环查找第i-1个结点的步骤。

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->next=p->next;
    p->next=s;
    return true;
}
1
2
3
4
5
6
7
8
9
10

• 时间复杂度：$O(1)$

D.指定结点的前插操作

• 方法一：

  传入头结点，遍历链表找到指定节点的前驱结点，再按后插的方式插入。

  • 时间复杂度：$O(n)$

• 方法二： better!

  按后插的方式在指定结点后插入新结点，再交换指定节点和新结点的数值。

  • 时间复杂度：$O(1)$

  bool InsertPriorNode(LNode *p,ElemType e){
      if(p==NULL)return false;
      LNode *s=(LNode*)malloc(sizeof(LNode));
      if(s==NULL)return false;
      
      s->next=p->next;
      p->next=s; //连接s和p后
      s->data=p->data; //p数据复制到s
      p->data=e; //原s的数据给p
      return true;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

  或者传入的是新结点，而不是数据时，也同理：

  bool InsertPriorNode(LNode *p,LNode *s){
      if(p==NULL||s==NULL)return false;
      
      s->next=p->next;
      p->next=s; //连接s和p后
      //交换值
      ElemType t=p->data;
      p->data=s->data;
      s->data=t;
      return true;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

3.1.3 单链表的删除

A.按位序删除

• 删除第i个结点的步骤

  1.找到要插入位置的前驱结点，即第i-1个结点。（如图，q是要删结点）

  

  2.将要删除结点从链表中断开，即前驱结点的next指向要删结点的后驱结点。

  

  3.释放已删除的结点空间。

  

bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)return false;
    LNode *p;
    p=L; //p从头开始扫描
    int j=0; //当前p指向第几个结点
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)return false; //i值不合法
    if(p->next==NULL)return false; //i-1后无结点
    
    LNode *q=p->next; //存储要删结点
    e=q->data; //e存储要删结点的值
    p->next=q->next; //将要删结点断开
    free(q);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度：$O(n)$

B.删除指定结点

• 方法：

  与指定结点的前插操作类似。

  1.交换指定结点和其后继结点的数据域；

  

  2.删除指定结点的后继结点。

  

  • 时间复杂度：$O(1)$

bool DeleteNode(LNode*p){
    if(p=NULL)return false;
    
    LNode*q=p->next; //q指向指定结点p的后继
    p->data=p->next->data; //与后继结点交换数据
    p->next=q->next; //将q结点断开（q里存的是要删结点的数据）
    free(q);
    return true;
}
1
2
3
4
5
6
7
8
9

• 注：

  若要删结点是最后一个结点，这样做有空指针的错误，只能用 从表头依次寻找p前驱的方法来删除。

3.1.4 单链表的查找

A.按位查找

• 查找第i个元素

  从链表第一个开始往后循环查找。

  i是链表中元素下标。

LNode *GetElem(LinkList L,int i){
    if(i<0)return NULL;
    LNode *p=L;
    int j=0;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10

• 可以用于按位查找、删除中的封装：

  

B.按值查找

• 找到数据域==e的结点

  时间复杂度：$O(n)$

LNode* LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)
        p=p->next;
    return p;
}
1
2
3
4
5
6

3.1.5 单链表的建立

A.尾插法

• 步骤

  1.建立头结点（初始化）；

  2.定义两个结点：一个指向表头结点s，另一个指向表尾结点r；

  3.循环输入结点值，并为新结点开辟空间；

  4.在表尾结点后插入新结点；

  5.更新表尾结点r，保证r永远指向最后一个结点；

  6.退出循环后，尾结点置空。

LinkList List_TailInsert(LinkList &L){
    int x;
    L=(LNode*)malloc(sizeof(LNode)); //创建头结点
    LNode *s,*r=L; //s始终指向表头结点，r指向表尾结点
    
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode)); //创建新结点
        s->data=x;
        r->next=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

B.头插法

• 注：

  头插法的输入和链表的数据是逆置关系：

  

LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;
    L=(LNode*)malloc(sizeof(LNode)); //创建头结点
    L->next=NULL; //初始化空链表
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode)); //创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s; //更新第一个结点
        scanf("%d",&x);
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

*完整代码 单链表带头结点

#include<stdio.h>
#include<stdlib.h>

#define ElemType int

typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

//初始化
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	return true;
}

//求表长
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next != NULL) {
		len++;
		p = p->next;
	}
	return len;
}

//头插法建立单链表
LinkList List_HeadInsert(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	LNode* s;
	int x;
	scanf("%d", &x);
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}

//尾插法建立单链表
LinkList List_TailInsert(LinkList& L) {
	int x;
	L = (LNode*)malloc(sizeof(LNode)); //创建头结点
	LNode* s, * r = L; //s指向头结点，r指向尾结点
	scanf("%d", &x);
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

//按序查找
LNode* GetItem(LinkList& L, int i) {
	LNode* p = L->next; //头结点中没有元素，所以要从next开始算
	int j = 0;
	while (j < i && p != NULL) {
		p = p->next;
		j++;
	}
	return p;
}

//按值查找
int LocateElem(LinkList& L, ElemType e) {
	LNode* p = L;
	int j = 0;
	while (p != NULL && p->data != e) {
		p = p->next;
		j++;
	}
	return j;
}

//按位序插入
bool ListInsert(LinkList& L, int i, ElemType e) {
	if (i < 0)return false;

	LNode* p = L;
	int j = 0;
	while (j < i-1 && p!= NULL) {
		p = p->next;
		j++;
	}
	if (p == NULL)return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//指定结点后插操作
bool InsertNextNode(LNode* p, ElemType e) {
	if (p == NULL)return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//指定结点前插操作
bool InsertPriorNode(LNode* p, ElemType e) {
	if (p == NULL )return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}

//按位序删除
bool ListDelete(LinkList& L, int i, ElemType& e) {
	LNode* p = L;
	int j=0;
	while (j < i-1 && p != NULL) {
		p = p->next;
		j++;
	}
	if (p == NULL||p->next==NULL)return false;

	LNode* q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

//删除指定结点
bool DeleteNode(LNode* p) {
	if (p == NULL)return false;

	LNode* q = p->next;
	p->data = p->next->data;
	p->next = q->next;
	free(q);
	return true;
}

void PrintList(LinkList& L) {
	LNode* p = L->next;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n\n");
}

void DestroyList(LinkList& L) {
	LNode* p = L;
	while (L) {
		p = L;
		L = L->next;
		free(p);
	}
}

int main() {
	LinkList L;

	printf("头插法建立单链表，输入以9999结束：\n");
	L=List_HeadInsert(L);
	PrintList(L);

	DestroyList(L);
	printf("尾插法建立单链表，输入以9999结束：\n");
	L=List_TailInsert(L);
	PrintList(L);

	printf("求表长：%d\n",Length(L));
	printf("\n");

	printf("按位序插入：\n");
	int pos=1, e=998;
	ListInsert(L, pos, e);
	PrintList(L);

	printf("指定结点的后插操作：\n");
	LNode* p =L->next;
	e = 222;
	InsertNextNode(p, e);
	PrintList(L);

	printf("指定结点的前插操作：\n");
	p = L->next;
	e = 111;
	InsertPriorNode(p, e);
	PrintList(L);

	printf("按值查找：\n");
	printf("查找222的位序是：%d\n", LocateElem(L, 222));
	printf("\n");

	printf("按序查找：\n");
	LNode* q = GetItem(L, 2);
	printf("查找第3个元素值是：%d\n", q->data);
	printf("\n");

	printf("按位序删除：\n");
	int ee;
	ListDelete(L, pos, ee);
	printf("删除的结点值：%d\n", ee);
	PrintList(L);

	printf("按指定结点删除：\n");
	p = L->next;
	DeleteNode(p);
	PrintList(L);
}
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224

*完整代码 单链表不带头结点

#include<stdio.h>
#include<stdlib.h>

#define ElemType int

typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode, * LinkList;

//初始化
bool InitList(LinkList& L) {
	L=NULL;
	return true;
}

//求表长
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p!= NULL) {
		len++;
		p = p->next;
	}
	return len;
}

//头插法建立单链表
LinkList List_HeadInsert(LinkList& L) {
	L= NULL;
	LNode* s;
	int x;

	//第一个结点要特殊判断
	scanf("%d", &x);
	L = (LNode*)malloc(sizeof(LNode));
	L->data = x;
	L->next = NULL;

	scanf("%d", &x);
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L;
		L = s;
		scanf("%d", &x);
	}
	return L;
}

//尾插法建立单链表
LinkList List_TailInsert(LinkList& L) {
	int x;
	L = NULL;

	//第一个结点要特殊判断
	scanf("%d", &x);
	L = (LNode*)malloc(sizeof(LNode));
	L->data = x;
	L->next = NULL;

	LNode* s, * r = L; //s指向头结点，r指向尾结点
	scanf("%d", &x);
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

//按序查找
LNode* GetItem(LinkList& L, int i) {
	LNode* p = L;
	int j = 0;
	while (j < i && p != NULL) {
		p = p->next;
		j++;
	}
	return p;
}

//按值查找
int LocateElem(LinkList& L, ElemType e) {
	LNode* p = L;
	int i = 0;
	while (p != NULL && p->data != e) {
		p = p->next;
		i++;
	}
	return i+1;
}

//按位序插入
bool ListInsert(LinkList& L, int i, ElemType e) {
	if (i < 0)return false;

	//插入第1个结点的操作与其它结点不同
	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s; //头指针指向新结点
		return true;
	}

	LNode* p = L;
	int j = 0;
	while (j < i - 1 && p != NULL) {
		p = p->next;
		j++;
	}
	if (p == NULL)return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//指定结点后插操作
bool InsertNextNode(LNode* p, ElemType e) {
	if (p == NULL)return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//指定结点前插操作
bool InsertPriorNode(LNode* p, ElemType e) {
	if (p == NULL)return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}

//按位序删除
bool ListDelete(LinkList& L, int i, ElemType& e) {
	if (i < 1)return false;

	//删除第1个结点的操作与其它结点不同
	if (i == 1) {
		e = L->data;
		LNode* s = L;
		L = L->next;
		free(s);
		return true;
	}

	LNode* p = L;
	int j = 0;
	while (j < i - 1 && p != NULL) {
		p = p->next;
		j++;
	}
	if (p == NULL || p->next == NULL)return false;

	LNode* q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

//删除指定结点
bool DeleteNode(LNode* p) {
	if (p == NULL)return false;

	LNode* q = p->next;
	p->data = p->next->data;
	p->next = q->next;
	free(q);
	return true;
}

void PrintList(LinkList& L) {
	LNode* p = L;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n\n");
}

void DestroyList(LinkList& L) {
	LNode* p = L;
	while (L) {
		p = L;
		L = L->next;
		free(p);
	}
}

int main() {
	LinkList L;

	printf("头插法建立单链表，输入以9999结束：\n");
	L = List_HeadInsert(L);
	PrintList(L);

	DestroyList(L);
	printf("尾插法建立单链表，输入以9999结束：\n");
	L = List_TailInsert(L);
	PrintList(L);

	printf("求表长：%d\n", Length(L));
	printf("\n");

	printf("按位序插入：\n");
	int pos = 1, e = 998;
	ListInsert(L, pos, e);
	PrintList(L);

	printf("指定结点的后插操作：\n");
	LNode* p = L;
	e = 222;
	InsertNextNode(p, e);
	PrintList(L);

	printf("指定结点的前插操作：\n");
	p = L;
	e = 111;
	InsertPriorNode(p, e);
	PrintList(L);

	printf("按值查找：\n");
	printf("查找222的位序是：%d\n", LocateElem(L, 222));
	printf("\n");

	printf("按序查找：\n");
	LNode* q = GetItem(L, 2);
	printf("查找第3个元素值是：%d\n", q->data);
	printf("\n");


	printf("按位序删除：\n");
	int ee;
	ListDelete(L, pos, ee);
	printf("删除的结点值：%d\n", ee);
	PrintList(L);

	printf("按指定结点删除：\n");
	p = L;
	DeleteNode(p);
	PrintList(L);
}
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257