【数据结构与算法】单链表的插入和删除

末蓝、 2024-04-26 02:17 104阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年9月21日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  单链表的定义
 *   *  什么是单链表？
     *  定义单链表
     *  不带头结点的单链表
     *  带头结点的单链表
     *  无头结点 VS 有头结点
 *  单链表的插入操作
 *   *  按位序插入（带头结点）
     *  按位序插入（不带头结点）
     *  指定结点的后插操作
     *  指定结点的前插操作
 *  单链表的删除操作
 *   *  按位序删除（带头结点）
     *  删除指定结点

## 单链表的定义 ##

### 什么是单链表？ ###

众所周知，顺序表中的每个结点中只存放数据元素，其优缺点为：

*  优点：可随机存取，存储密度高
 *  缺点：要求大片连续空间，改变容量不方便

而单链表中的每个结点除了存放数据元素外，还要存储指向下一个节点的指针，其优缺点为：

*  优点：不要求大片连续空间，改变容量方便
 *  缺点：不可随机存取，要耗费一定空间存放指针

### 定义单链表 ###

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

当你想要增加一个新的节点时，你需要在内存中申请一个结点所需的空间，并用指针 **p** 指向这个结点

LNode * p = (LNode *)malloc(sizeof(LNode));

上面这样写是不是很麻烦呢？

所以我们下面用一种更简洁的方式来实现

typedef int ElemType;
    
    typedef struct LNode{
        
    	ElemType data;			//每个节点存放一个数据元素
    	struct LNode *next;		//指针指向下一个节点
    }LNode, *LinkList;

它等同于下面的代码

typedef int ElemType;
    
    struct LNode{
        
    	ElemType data;			//每个节点存放一个数据元素
    	struct LNode *next;		//指针指向下一个节点
    };
    typedef struct LNode LNode;
    typedef struct LNode *LinkList;

这样的话，当我们要表示一个单链表时，只需要声明一个头指针 L，让它指向单链表的第一个结点，具体有下面两种方式：

第一种：

LNode * L;		//声明一个指向单链表第一个结点的指针

第二种：

LinkList L;		//声明一个指向单链表第一个结点的指针

相比起来，第二种方式的可读性更强

具体在写代码时，我们需要记住：

*  强调这是一个单链表 —— 使用 **LinkList**
 *  强调这是一个结点 —— 使用 **LNode \***

### 不带头结点的单链表 ###

#include <stdio.h>
    
    typedef int ElemType;
    
    typedef struct LNode{
        
    	ElemType data;			//每个节点存放一个数据元素
    	struct LNode *next;		//指针指向下一个节点
    }LNode, *LinkList;
    
    //初始化一个空的单链表
    bool InitList(LinkList &L) {
        
    	L = NULL;	//空表，暂时没有任何结点
    	return true;
    }
    
    //判断单链表是否为空
    bool Empty(LinkList L) {
        
    	return L == NULL;
    }
    
    //主函数
    int main() {
        
    	LinkList L;		//声明一个指向单链表的指针
    
    	//初始化一个空表
    	InitList(L);
    
    	return 0;
    }

### 带头结点的单链表 ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElemType;
    
    typedef struct LNode{
        
    	ElemType 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) {
        
    	return L->next == NULL;
    }
    
    //主函数
    int main() {
        
    	LinkList L;		//声明一个指向单链表的指针
    
    	//初始化一个空表
    	InitList(L);
    	
    	return 0;
    }

### 无头结点 VS 有头结点 ###

不带头结点，写代码会更加麻烦，对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑；对空表和非空表的处理也需要不同的代码逻辑

头结点不存储数据，只是为了操作方便

## 单链表的插入操作 ##

### 按位序插入（带头结点） ###

`ListInsert(&L, i, e)`：插入操作。在表 **L** 中的第 **i** 个位置上插入指定元素 **e**

**代码实现**

//在第 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 个结点
    
    	//循环找到第 i-1 个结点
    	while (p != NULL && j < i - 1) {
        
    		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;		//将结点s连到p之后
    	return true;		//插入成功
    }

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

`ListInsert(&L, i, e)`：插入操作。在表 **L** 中的第 **i** 个位置上插入指定元素 **e**

由于不带头结点，所以在处理 **i=1** 时需要特殊处理

**代码实现**

//在第 i 个位置插入元素 e（带头结点）
    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 = 1;		//当前p指向的是第几个结点
    	p = L;			//L指向头结点，头结点是第 0 个结点
    
    	//循环找到第 i-1 个结点
    	while (p != NULL && j < i - 1) {
        
    		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;		//将结点s连到p之后
    	return true;		//插入成功
    }

到这里，你能体会到不带头结点的麻烦之处了吧

### 指定结点的后插操作 ###

//后插操作：在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;
    }

有了这个后插操作，我们前面的插入操作就可以改为

### 指定结点的前插操作 ###

这我就有点懵了，给你一个结点，你又找不到前面的结点，怎么插入啊

//前插操作：在p结点之前插入元素e
    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->data = e;
    	return true;
    }

想不到吧，我的指针跑不了路，数据可以啊

//前插操作：在p结点之前插入结点s
    bool InsertPriorNode(LNode *p, LNode *s) {
        
    	if (p == NULL || s == NULL) return false;
    	
    	s->next = p->next;
    	p->next = s;			//将结点s连到p之后
    	ElemType temp = p->data;
    	p->data = s->data;
    	s->data = temp;
    	return true;
    }

## 单链表的删除操作 ##

### 按位序删除（带头结点） ###

`ListDelete(&L, i, &e)`：删除操作。删除表 **L** 中第 **i** 个位置的元素，并用 **e** 返回删除元素的值

//按位序删除（带头结点）
    bool ListDelete(LinkList &L, int i, ElemType &e) {
        
    	if (i < 1) return false;
    
    	LNode *p;		//指针p指向当前扫描到的结点
    	int j = 0;		//当前p指向的是第几个结点
    	p = L;			//L指向头结点，头结点是第 0 个结点
    
    	//循环找到第 i-1 个结点
    	while (p != NULL && j < i - 1) {
        
    		p = p->next;
    		j++;
    	}
    
    	if (p == NULL) return false;
    	if (p->next == NULL) return false;
    
    	LNode *q = p->next;		//让q指向要被删除的结点
    	e = q->data;			
    	p->next = q->next;		//将*q结点断开
    	free(q);
    	return true;
    }

### 删除指定结点 ###

思路：将指定结点的下一个结点的值传给指定结点，指定结点指向下一个结点的下一个，再删除下一个结点，这样就变相地删除了指定结点

//删除指定结点
    bool DeleteNode(LNode *p) {
        
    	if (p == NULL) return false;
    
    	LNode *q = p->next;
    	p->data = q->data;
    	p->next = q->next;
    	free(q);
    }

不过这个方法有个 **bug**，就是当 **p** 是最后一个结点时，就行不通了，只能从表头开始依次寻找 **p** 的前驱

至于直接 `free(p)` 的操作是不行的，因为最后一个结点总得指向 **NULL**，你直接释放掉 **p** 怎么行

从这里我们就可以看出单链表的局限性：无法逆向检索，有时候不太方便

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482