学习记录：第二章 线性表的链式存储

文章目录

• 前言
• 一、插入
• • 1. 按位序插入（带头结点的单链表）
  • 2. 按位序插入（不带头结点的单链表）
  • 3. 在指定结点之后，插入一个结点
  • 4. 在指定结点之前，插入一个结点
  • 5. 在结点之后和在结点之前插入的区别
• 二、删除
• • 1. 按位序删除（带头结点的单链表）
  • 2. 按位序删除（不带头结点的单链表）
  • 3. 删除指定结点
• 三、查找（带头结点）
• • 1. 按位查找（带头结点）
  • 2. 按值查找（带头结点）
• 四、求表长（带头结点）
• 三、总代码
• • 1. 带头结点，按位序插入、删除（已封装，可运行）
  • 2. 不带头结点，按位序插入、删除（已封装，能运行）
• 总结（需要注意）
• 线性表系列文章

---

前言

本文给出了单链表_插入删除查找三种基本操作以及求表长_代码及相应图示助于理解，代码实现使用的是C语言在线工具。无概念解释，初学者建议配合书本食用。
【如果图片看不清楚，网页版是很清晰的。】

---

一、插入 1. 按位序插入（带头结点的单链表）

在单链表第 i 个位置插入元素 e 。只需要找到第 i -1 个结点，将新结点插入其后。

图示：

i 的 3 种位置：第一个、中间、最后一个。

由上图可以看出，
当 i<1，i 不合法【就是代码的第一个 if 条件判断】。
当 i=1，最好情况下的时间复杂度是O(1)。
当 i=length+1，最坏情况下时间复杂度是O(n)，因为需要循环找到第 i-1个结点。
当 1< i 当 i>length+1，i 不合法【就是代码的第二个 if 条件判断】。

代码如下：

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e){
	if(i<1)  		//判断i是否合法，位序从1开始，如果i<1，不合法
		return false;
	LNode *p;  		//指针p指向当前扫描到的结点
	int j = 0;		//p指向当前第j个结点，j=0是头结点，所谓的第0个结点（不存数据）
	p = L;			//L指向头结点，p从头结点开始
	while(p!=NULL && j	//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if(p==NULL)		//判断i是否合法，比如总共4个结点存储数据，那么最多插入到第5个位置，如果i=6，经过上述while循环后此时p==NULL，不合法
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;				//返回true代表插入成功
}

2. 按位序插入（不带头结点的单链表）

在单链表第 i 个位置插入元素 e 。只需要找到第 i -1 个结点，将新结点插入其后。

i 的 3 种位置：第一个、中间、最后一个。

但是如果 i 是第一个位置，因为不带头结点，也就是不存在所谓的 “第0个” 结点，因此插入第1个元素时，需要更改头指针L，需要单独加一段代码，如图：
（其余两种位置和带头结点的一样）

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;				

//在第i个位置插入元素e（不带头结点）
bool ListInsert(LinkList &L, int i, int e){
	if(i < 1)  		//判断i是否合法，位序从1开始，如果i<1，不合法
		return false;
	if(i == 1){		//插入第1个结点的操作与其他结点不同
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;		//头指针指向新结点
		return true;
	}
	LNode *p;  		//指针p指向当前扫描到的结点
	int j = 1;		//p指向当前第j个结点
	p = L;			//p从第一个结点开始（不是头结点）
	while(p!=NULL && j	//循环找到第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;			//将结点s与p的下一个结点相连
	p->next = s;				//将结点s连到p之后
	return true;				//返回true代表插入成功
}

3. 在指定结点之后，插入一个结点

指定 p 结点，在这个结点之后插入一个结点元素 e。

代码如下，由于没有循环，所以时间复杂度是O(1)。

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//在p结点之后插入新结点元素e
bool InsertNextNode(LNode *p, int e){
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)		//内存不足，分配失败，这个if也可以不加
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;		//将结点s连到p后
	return true;
}

这段代码很眼熟吧，其实就是ListInsert插入函数的这一部分：

于是可以封装为如下图：

4. 在指定结点之前，插入一个结点

指定 p 结点，在这个结点之前插入一个结点元素 e。相当于在 p 的前驱结点后面插入一个结点。

由于单链表只能向后找，不能向前找，那如何找到 p 结点的前驱节点？

• 办法一，传入头指针 L，从头开始遍历找到 p 的前驱结点 m，然后在 m 结点之后插入 e。这样也可以，但是需要循环，意味着时间复杂度为O(n)。

bool InsertPriorNode(LinkList L, LNode *p, ElemType e) //传入头指针L

• 办法二，与其找 p 的上一个结点，不如创建一个新结点 s，把 s 插到 p 之后，然后对调 p 和 s（偷天换日了啊兄弟们），这不就相当于在 p 之前插入一个 s 吗，这样不用循环，所以时间复杂度是O(1)。代码如下：

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//在p结点之前插入新结点元素e
bool InsertPriorNode(LNode *p, ElemType e){
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)		//内存不足，分配失败，这个if也可以不加
		return false;
	s->next = p->next;
	p->next = s;		//新结点s连到p之后
	s->data = p->data;	//p中的data复制到s中
	p->data = e;		//p中的data换成e
	return true;
}

以上代码图示：

5. 在结点之后和在结点之前插入的区别

二、删除 1. 按位序删除（带头结点的单链表）

删除第 i 个位置的结点，并用 e 返回删除元素的值。只需要找到第 i-1个位置的结点，将其 next 指针指向第 i+1个结点，然后释放第 i 个结点。

和插入一样，i 的 3 种位置：第一个、中间、最后一个。，
所以最好时间复杂度是O(1)，最坏和平均时间复杂度是O(n)。

代码如下：

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//删除第i个位置的结点，并用e返回删除元素的值
bool ListDelete(LinkList &L, int i, int &e){	//注意e是引用类型参数
	if(i < 1)
		return false;
	LNode *p;  		//指针p指向当前扫描到的结点
	int j = 0;		//p指向当前第j个结点，j=0是头结点，所谓的第0个结点（不存数据）
	p = L;			//L指向头结点，p从头结点开始
	while(p!=NULL && j	//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if(p == NULL)			//i值不合法
		return false;
	if(p->next == NULL)		//第i-1个结点之后已无其他结点，p是找到的第i-1个结点
		return false;
	LNode *m = p->next;		//令指针m指向被删除结点，也就是第i个结点
	e = m->data;			//用e返回第i个元素的值，也就是m的值
	p->next = m->next;		//将结点*m从链中断开：让第i-1个直接指向第i+1个
	free(m);				//释放第i个
	return true;			//删除成功
}

2. 按位序删除（不带头结点的单链表）

删除第 i 个位置的结点，并用 e 返回删除元素的值。只需要找到第 i-1个位置的结点，将其 next 指针指向第 i+1个结点，然后释放第 i 个结点。

i 的 3 种位置：第一个、中间、最后一个。

但在删除一个位置时，因为不带头结点，也就是不存在所谓的 “第0个” 结点，因此删除第1个元素时，需要更改头指针L，需要单独加一段代码，和带头结点的代码区别如下：
（其余两种位置和带头结点的一样）

代码如下：

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//删除第i个位置的结点，并用e返回删除元素的值
bool ListDelete(LinkList &L, int i, int &e){	//注意e是引用类型参数
	if(i < 1)
		return false;
	if(i == 1){		//删除第1个结点的操作与其他结点不同
		LNode *m = L;		//令指针m指向被删除结点，也就是第i个结点
		e = m->data;		//用e返回第i个元素的值，也就是m的值
		L = m->next;		//将结点*m从链中断开：让第i-1个直接指向第i+1个
		free(m);			//释放第i个
		return true;
	}
	LNode *p;  		//指针p指向当前扫描到的结点
	int j = 1;		//p指向当前第j个结点
	p = L;			//p指向第一个结点（不是头结点）
	while(p!=NULL && j	//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if(p == NULL)			//i值不合法
		return false;
	if(p->next == NULL)		//第i-1个结点之后已无其他结点，p是找到的第i-1个结点
		return false;
	LNode *m = p->next;		//令指针m指向被删除结点，也就是第i个结点
	e = m->data;			//用e返回第i个元素的值，也就是m的值
	p->next = m->next;		//将结点*m从链中断开：让第i-1个直接指向第i+1个
	free(m);				//释放第i个
	return true;			//删除成功
}

3. 删除指定结点

删除结点 p，只需要修改其前驱结点的 next 指针。也就是让 p 的前驱结点 m 指向 p 的后继结点 n ，相当于删除了 p 。

• 方法一：从链表头依次寻找，直至找到前驱结点 m 并修改其 next 指针。
• 方法二：与其循环找结点 p 的前驱结点，不如把后继结点 n 提前一个位置，覆盖结点 p，也相当于删除了 p 结点，这样时间复杂度是O(1)，代码如下：

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//删除指定结点p
bool DeleteNode(LNode *p){
	if(p == NULL)
		return false;
	LNode *n = p->next;		//令指针n指向*p的后继结点
	p->data = p->next->data;//和后继结点交换数据域
	p->next = n->next;		//将结点*n从链中断开
	free(n);				//释放后继结点
	return true;
}

三、查找（带头结点） 1. 按位查找（带头结点）

按位查找，返回第 i 个元素。代码如下：

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//按位查找，返回第i个元素
LNode * GetElem(LinkList L, int i){
	if(i < 0)
		return NULL;
	LNode *p;		//指针p指向当前扫描到的结点
	int j = 0;		//当前p指向的是第j个结点
	p = L;			//L指向头结点，头结点是第0个结点（不存数据）
	while(p!=NULL && j		//循环找到第i个结点
		p = p->next;
		j++;
	}
	return p;
}

当 i = 0，GetElem返回头结点。
当 i 无效(比如 i < 0)或者大于表长，返回NULL。
因此可以通过返回值是否为NULL，判断按位查找操作是否执行成功。

平均时间复杂度O(n)。

上面的插入和删除两个操作，都需要找到第 i-1 个结点，因此这部分的代码可以用GetElem函数替换。如图：
（封装避免了重复代码，使得代码简洁易维护）

如果对InsertNextNode(指定结点之后插入新结点)的 if (p == NULL)有疑惑：

为什么InsertNextNode(指定结点之后插入新结点)要判断p是否为NULL呢？
上面我们提到 i 有不合法的情况：

因此InsertNextNode函数的 if (p == NULL)是考虑到了 i 值的非法情况，加强了代码的健壮性。

2. 按值查找（带头结点）

按值查找，找到数据域等于 e 的结点并返回。代码如下：

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//按值查找，找到数据域等于e的结点（带头结点的单链表）
LNode * LocateElem(LinkList L, int e){
	LNode *p = L->next;		//从第一个结点开始找数据域为e的结点，L是头结点
	while(p!=NULL && p->data!=e)	//这里e是int类型，所以可以直接用!=直接比较，但如果e是struct结构类型，就不能用!=比较是否相等
		p = p->next;
	return p;				//找到后返回该结点指针，否则返回NULL
}

该函数找到后返回该结点指针，否则返回NULL：
是因为这个while 循环，就是找不到 e 就让指针 p 一直往后移，最终会移到NULL，所以找不到就返回NULL。函数的调用者接收到NULL，说明找不到数据域为 e 的结点。

时间复杂度O(n)。

四、求表长（带头结点）

typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

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

时间复杂度O(n)。

三、总代码 1. 带头结点，按位序插入、删除（已封装，可运行）

#include
#include 
typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//初始化一个单链表（带头结点）
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;
}

//按位查找，返回第i个元素
LNode * GetElem(LinkList L, int i){
	if(i < 0)
		return NULL;
	LNode *p;		//指针p指向当前扫描到的结点
	int j = 0;		//当前p指向的是第j个结点
	p = L;			//L指向头结点，头结点是第0个结点（不存数据）
	while(p!=NULL && j		//循环找到第i个结点
		p = p->next;
		j++;
	}
	return p;
}

//按值查找，找到数据域等于e的结点（带头结点的单链表）
LNode * LocateElem(LinkList L, int e){
	LNode *p = L->next;		//从第一个结点开始找数据域为e的结点，L是头结点
	while(p!=NULL && p->data!=e)
		p = p->next;
	return p;				//找到后返回该结点指针，否则返回NULL
}

//在p结点之后插入新结点元素e
bool InsertNextNode(LNode *p, int e){
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)		//内存不足，分配失败，这个if也可以不加
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;		//将结点s连到p后
	return true;
}

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e){
	if(i<1)  		//判断i是否合法，位序从1开始，如果i<1，不合法
		return false;
	LNode *p = GetElem(L, i-1);		//找到第i-1个结点
	return InsertNextNode(p, e);	//插入e
}

//删除第i个位置的结点，并用e返回删除元素的值
bool ListDelete(LinkList &L, int i, int &e){	//注意e是引用类型参数
	if(i < 1)
		return false;
	LNode *p = GetElem(L, i-1);		//找到第i-1个结点
	if(p == NULL)			//i值不合法
		return false;
	if(p->next == NULL)		//第i-1个结点之后已无其他结点，p是找到的第i-1个结点
		return false;
	LNode *m = p->next;		//令指针m指向被删除结点，也就是第i个结点
	e = m->data;			//用e返回第i个元素的值，也就是m的值
	p->next = m->next;		//将结点*m从链中断开：让第i-1个直接指向第i+1个
	free(m);				//释放第i个
	return true;			//删除成功
}

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

//打印单链表（带头结点）
void PrintList(LinkList &L){
	if(!Empty(L)){  			//判断链表是否为空，空则返回true
		LNode *p = L->next;  
		while (p != NULL) {
			printf("%dn", p->data);
			p = p->next;
		}
	}
}

int main(){
	LinkList L;			//声明一个指向单链表的指针,指针指向头结点
	InitList(L);		//初始化一个空表
	int e;
	int i;
	//插入10个结点
	for(i=1; i<=10; i++){  	
		e = i;				//插入的元素e的值为当前i值
		ListInsert(L, i, e); 	//在第i个位置插入元素e（带头结点）
	}
	//打印单链表
	printf("打印整个单链表n");
	PrintList(L);		
	//求表长
	printf("表长为%dn", Length(L));
	//删除第i=5个结点
	i = 5;
	ListDelete(L, i, e);
	printf("删除第%d个结点，值为%dn", i, e);
	//打印单链表
	printf("再次打印整个单链表n");
	PrintList(L);		
	//求表长
	printf("表长为%dn", Length(L));
	return true;
}

这段代码是在上篇文章单链表_初始化创建中，创建一个空的带头结点的单链表的代码的基础上，插入10个结点，然后删除第 i 个结点，求表长，运行结果如下：

2. 不带头结点，按位序插入、删除（已封装，能运行）

#include
#include
typedef struct LNode{			//定义单链表结点类型
	int data;					//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;				

//初始化一个空的单链表（不带头结点）
bool InitList(LinkList &L){		//注意这里传入指针变量L的时候使用的是&L引用类型
	L = NULL;		//空表，暂时没有任何结点
	return true;
}

//判断单链表是否为空（不带头结点）：判断头指针L是否等于NULL
bool Empty(LinkList L){
	if(L == NULL)
		return true;
	else 
		return false;
}

//按位查找，返回第i个元素
LNode * GetElem(LinkList L, int i){
	if(i < 0)
		return NULL;
	LNode *p;		//指针p指向当前扫描到的结点
	int j = 1;		//当前p指向的是第j个结点
	p = L;			//p从第一个结点开始（不是头结点）
	while(p!=NULL && j		//循环找到第i个结点
		p = p->next;
		j++;
	}
	return p;
}

//按值查找，找到数据域等于e的结点（不带头结点的单链表）
LNode * LocateElem(LinkList L, int e){
	LNode *p = L;		//从第一个结点开始找数据域为e的结点
	while(p!=NULL && p->data!=e)
		p = p->next;
	return p;				//找到后返回该结点指针，否则返回NULL
}

//在p结点之后插入新结点元素e
bool InsertNextNode(LNode *p, int e){
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)		//内存不足，分配失败，这个if也可以不加
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;		//将结点s连到p后
	return true;
}

//在第i个位置插入元素e（不带头结点）
bool ListInsert(LinkList &L, int i, int e){
	if(i < 1)  		//判断i是否合法，位序从1开始，如果i<1，不合法
		return false;
	if(i == 1){		//插入第1个结点的操作与其他结点不同
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;		//头指针指向新结点
		return true;
	}
	LNode *p = GetElem(L, i-1);		//找到第i-1个结点
	return InsertNextNode(p, e);
}

//删除第i个位置的结点，并用e返回删除元素的值
bool ListDelete(LinkList &L, int i, int &e){	//注意e是引用类型参数
	if(i < 1)
		return false;
	if(i == 1){		//删除第1个结点的操作与其他结点不同
		LNode *m = L;		//令指针m指向被删除结点，也就是第i个结点
		e = m->data;		//用e返回第i个元素的值，也就是m的值
		L = m->next;		//将结点*m从链中断开：让第i-1个直接指向第i+1个
		free(m);			//释放第i个
		return true;
	}
	LNode *p = GetElem(L, i-1);		//找到第i-1个结点
	if(p == NULL)			//i值不合法
		return false;
	if(p->next == NULL)		//第i-1个结点之后已无其他结点，p是找到的第i-1个结点
		return false;
	LNode *m = p->next;		//令指针m指向被删除结点，也就是第i个结点
	e = m->data;			//用e返回第i个元素的值，也就是m的值
	p->next = m->next;		//将结点*m从链中断开：让第i-1个直接指向第i+1个
	free(m);				//释放第i个
	return true;			//删除成功
}

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

//打印单链表（不带头结点）
void PrintList(LinkList &L){
	if(!Empty(L)){  			//判断链表是否为空，空则返回true
		LNode *p = L;  
		while (p != NULL) {
			printf("%dn", p->data);
			p = p->next;
		}
	}
}

int main(){
	LinkList L;			//声明一个指向单链表的指针
	InitList(L);		//初始化一个空表
	int e;
	int i;
	//插入10个结点
	for(i=1; i<=10; i++){  	
		e = i;				//插入的元素e的值为当前i值
		ListInsert(L, i, e); 	//在第i个位置插入元素e（不带头结点）
	}
	//打印单链表
	printf("打印整个单链表n");
	PrintList(L);
	//求表长
	printf("表长为%dn", Length(L));
	//删除第i=1个结点
	i = 1;
	ListDelete(L, i, e);
	printf("删除第%d个结点，值为%dn", i, e);
	//打印单链表
	printf("再次打印整个单链表n");
	PrintList(L);
	//求表长
	printf("表长为%dn", Length(L));
	return true;
}

这段代码是在上篇文章单链表_初始化创建中，创建一个空的不带头结点的单链表的代码的基础上，插入10个结点，然后删除第 i 个结点，求表长，运行结果如下：

---

总结（需要注意）

• 不带头结点：
  插入、删除第1个元素时，需要更改头指针 L，额外加一段代码，因此不带头结点的单链表的操作更麻烦。
• 插入和删除操作：
  都需要传入参数 e ，但是删除操作需要用 e 返回被删除结点的值，因此bool ListDelete(LinkList &L, int i, int &e) //注意e是引用类型参数。而插入操作不需要返回 e 值，因此不需要引用类型。
• 插入操作：
  s->next = p->next;
  p->next = s;
  这两行代码不能颠倒顺序。
• 可以看出，查找、插入、删除三种基本操作的时间复杂度都是O(n)，但这里指的是最坏和平均情况下的时间复杂度。

线性表系列文章

• 线性表的顺序存储_顺序表_初始化（静态分配以及动态分配）（代码、图示、C++）
• 线性表的顺序存储_顺序表_插入删除查找三种基本操作（代码、图示、C++）
• 线性表的链式存储_单链表_初始化创建（代码、图示、C++）
• 本文的位置

【请多多支持，多多建议，一键三连(bushi)，3Q~ 】