🔥 本文由 程序喵正在路上 原创，CSDN首发！
💖 系列专栏：数据结构与算法
🌠 首发时间：2022年9月21日
🦋 欢迎关注🖱点赞👍收藏🌟留言🐾
🌟 一以贯之的努力 不得懈怠的人生
单链表的定义
什么是单链表？
众所周知，顺序表中的每个结点中只存放数据元素，其优缺点为：
- 优点：可随机存取，存储密度高
- 缺点：要求大片连续空间，改变容量不方便
而单链表中的每个结点除了存放数据元素外，还要存储指向下一个节点的指针，其优缺点为：
- 优点：不要求大片连续空间，改变容量方便
- 缺点：不可随机存取，要耗费一定空间存放指针
定义单链表
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;
}
有了这个后插操作，我们前面的插入操作就可以改为
//在第 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++;
}
return InsertNextNode(p, e);
}
指定结点的前插操作
这我就有点懵了，给你一个结点，你又找不到前面的结点，怎么插入啊
//前插操作：在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 怎么行文章来源：https://www.toymoban.com/news/detail-724090.html
从这里我们就可以看出单链表的局限性：无法逆向检索，有时候不太方便文章来源地址https://www.toymoban.com/news/detail-724090.html
到了这里，关于【数据结构与算法】单链表的插入和删除的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
