单链表（LinkList）基本算法（理论+代码实现(C/C++)）
创作时间:
作者:
@小白创作中心
单链表（LinkList）基本算法（理论+代码实现(C/C++)）
引用
CSDN
1.
https://blog.csdn.net/weixin_68098409/article/details/142969850
链表是一种常见的数据结构，它通过一组任意的存储单元来存储一组具有相同类型的数据。链表中的每个数据元素占用若干存储单元的组合称为一个「链节点」，每个链节点不仅要存放一个数据元素的值，还要存放一个指出这个数据元素在逻辑关系上的直接后继元素所在链节点的地址，该地址被称为「后继指针」。链表具有存储空间灵活、插入删除操作效率高等优点，但同时也存在空间开销大等缺点。
链表的定义
链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。
简单来说，链表就是实现线性表链式存储结构的基础。
链表是由链节点通过 next 指针链接而构成的，我们可以先定义一个简单的「链节点类」，再来定义完整的「链表类」。
链节点类（即 Node 类）：使用成员变量 data 表示数据元素的值，使用指针变量 next表示后继指针。
链表类（即 LinkedList 类）：使用一个链节点变量 head 来表示链表的头节点。
我们在创建空链表时，只需要把相应的链表头节点变量设置为空链接即可。
图解：
链表通过将一组任意的存储单元串联在一起。其中，每个数据元素占用若干存储单元的组合称为一个「链节点」。为了将所有的节点串起来，每个链节点不仅要存放一个数据元素的值，还要存放一个指出这个数据元素在逻辑关系上的直接后继元素所在链节点的地址，该地址被称为「后继指针 nextnext」。
链表的优缺点
- 优点：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。
- 缺点：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。
单链表的基本操作（代码实现）
定义链节点类
#include <cstdlib>
struct NODE {
int data; // 数据
NODE *next; // 后继
};
定义单链表的抽象数据结构
struct LinkList {
NODE *head; //头[链表的第0个元素]
bool IsEmpty(); //判断链表是否为空
void Init(); // 初始化链表
void HeadCreate(int c); // 插入：头插法
void TailCreate(int c); // 插入：尾插法
void Traverse(); // 链表迭代器
void Insert(int i, int data); // 在i的位置插入一个node节点,数据为data
bool Delete(int i, int &e); // 删除链表中第i个位置的节点，并将数据赋值给e
void Modify(int x, int y); // 将单链表中值为x的数据改为 y
void Replace(int i, int x); // 将i位置上的数据替换为 x
int Seek(int x); // 查找单链表是否有值为x的节点，若有则返回值为x的位置，若没有则返回 -1
int Count(int x);// 统计单链表节点值为x的数据的个数
int Length(); // 求单链表的长度
void Sort(); //链表排序
NODE *Unsortfind(int x); // 无序查找
bool GetElem(int i, int &e); // 取第i位置上的数据并保存在e中
void Destroy(); // 销毁单链表
};
头插法图解
链表头部插入元素：在链表第 1个链节点之前插入值为 valval 的链节点。
- 先创建一个值为 value 的链节点 newNode。
- 然后将 newNode的 next 指针指向链表的头节点 head -> next。
- 再将链表的头节点head -> next指向 newNode。
中间位置插入节点图解
链表中间插入元素：在链表第 i个链节点之前插入值为 data的链节点。
- 使用指针变量 cur (代码实现中使用p) 和一个节点变量node来申请新节点的空间，并存放数据。令 cur 指向链表的头节点。
- 沿着链节点的 next 指针遍历链表，指针变量 cur每指向一个链节点，计数器就做一次计数。
- 当遍历到第（i-1）个链节点时停止遍历。
- 创建一个值为 data 的链节点 node。
- 将 node ->next 指向 cur ->next。
- 然后令cur ->next 指向 node。
具体算法实现
/**
* @brief 统计单链表节点值为x的数据的个数
*
* @param x 需要对比的数据
*
* @return 值为X的数量
*/
int LinkList::Count(int x) {
NODE *p;
int count = 0;
p = head ->next;
for (int i = 0; i < Length(); i++) {
if (x == p ->data) {
count++;
}
p = p ->next;
}
return count;
}
/**
* @brief 将i位置上的数据替换为 x
*
* @param i 链表的节点位置
* @param y 给该节点替换的数据
*/
void LinkList::Replace(int i, int y) {
if (i < 0 || IsEmpty() || i > Length()) return;
NODE *p;
p = head ->next;
for (int j = 0; j < i - 1; j++) {
p = p ->next;
}
p ->data = y;
}
/**
* @brief 查找单链表是否有值为x的节点，
*
* @param x 需要对比的数据
*
* @return 若有则返回值为x的位置，若没有则返回 -1
*/
int LinkList::Seek(int x) {
NODE *p;
p = head ->next;
for (int i = 0; i <= Length() - 1; i++) {
if (x == p ->data) {
return i;
}
p = p ->next;
}
return -1;
}
/**
* @brief 将单链表中值为x的数据改为 y
*
* @param x 需要查找的数据
* @param y 用于替换的数据
*/
void LinkList::Modify(int x, int y) {
NODE *p;
p = head ->next;
int j = Seek(x);
if (j == -1) return;
for (int i = 0; i < j; i++) {
p = p ->next;
}
p ->data = y;
Modify(x, y);
}
/**
* @brief 求单链表的长度
*
* @return 链表的长度
*/
int LinkList::Length() {
NODE *p;
int length = 0;
p = head ->next;
while (p) {
p = p ->next;
length++;
}
return length;
}
/**
* @brief 删除链表中第i个位置的节点，并将数据赋值给
*
* @param e 被删除节点的数据
* @param i 被删除节点的位置
*
* @return 删除成功返回true，否则返回false
*/
bool LinkList::Delete(int i, int &e) {
if (i < 0 || IsEmpty()) return false;
NODE *p,*q;
p = head ->next;
for (int j = 0; (j < i - 1 ) && (p ->next != NULL); j++) {
p = p ->next;
}
e = p ->next ->data;
q = p ->next ->next;
p ->next = q;
if (p ->next == NULL) {
return false;
}
return true;
}
/**
* @brief 在i的位置插入一个node节点,数据为data
*
* @param data 插入节点的数据
* @param i 插入节点的位置
*/
void LinkList::Insert(int i, int data) {
NODE *p,*node;
p = head ->next;
node = (NODE *) malloc(sizeof(NODE));
node ->data = data;
node ->next = NULL;
if (i <= 0) {
node ->next = head -> next;
head ->next = node;
return;
}
for (int j = 0; j < i - 1 && p ->next != NULL; j++) {
p = p ->next;
}
node ->next = p ->next;
p ->next = node;
if (p ->next == NULL) {
p ->next = node;
return;
}
}
/**
* @brief 链表的迭代器，返回每个链表中每个NODE的值
*/
void LinkList::Traverse() {
NODE *p;
p = head ->next;
// int countSize = sizeof(NODE);
// printf("每个NODE的大小：%d", countSize);
while (p) {
printf("%5d", p->data);
p = p ->next;
}
printf("\n");
}
/**
* 尾插法
* @param c(count) 插入数据的数量
*/
void LinkList::TailCreate(int c) {
if (c <= 0) return;
NODE *q,*node;
q = head;
int x = 1;
for (int i = 0; i < c; i++) {
node = (NODE *)malloc(sizeof(NODE));
// x = rand() % 300;
node ->data = x++;
node ->next = NULL;
// 连接
q ->next = node;
q = node;
}
}
/**
* 头插法
* @param c(count) 插入数据的数量
*/
void LinkList::HeadCreate(int c) {
if (c <= 0) return;
NODE *p;
int x = 1;
for (int i = 0; i < c; i++) {
p = (NODE *)malloc(sizeof(NODE));
p ->data = x++;
p ->next = NULL;
// 连接
p ->next = head ->next;
head ->next = p;
}
}
/**
* 初始化链表
*/
void LinkList::Init() {
head = (NODE *)malloc(sizeof(NODE));
head ->next = NULL;
}
/**
* 判断链表是否为空
*/
bool LinkList::IsEmpty() {
if (head ->next == NULL) {
return true;
}
return false;
}
最后三个实现（无序查找、查找某一个并保存在变量e中、销毁线程表）
/**
* @brief 销毁单链表（将每个节点动态分配的空间释放）
*/
void LinkList::Destroy() {
if (IsEmpty()) return;
NODE *p,*p_next;
p = head ->next;
p_next = p;
int i = 1;
while (p_next) {
p_next = p_next ->next;
printf("\n销毁前的值：%d", p ->data);
if (p != NULL) {
free(p);
printf("\n销毁%d个节点！", i++);
}
printf("\n销毁后的值：%d", p ->data);
p = p_next;
}
head ->next = NULL;
printf("\n销毁成功！");
}
/**
* @brief 取第i位置上的数据并保存在e中
*
* @param e 获取到的数据
* @param i 获取的链表位置
*
* @return true / false
*/
bool LinkList::GetElem(int i, int &e) {
if (i < 0 || IsEmpty() || i >= Length()) return false;
NODE *p;
p = head ->next;
for (int j = 0; j < i - 1; j++) {
p = p ->next;
}
e = p ->data;
return true;
}
/**
* @brief 返回节点的值为x的第一个节点的地址，无值为X节点时，返回NULL
*
* @param x
*
* @return *x / NULL
*/
NODE *LinkList::Unsortfind(int x) {
NODE *p;
p = head ->next;
for (int i = 0; i < Length(); i++) {
if (p ->data == x) {
return p;
}
p = p->next;
}
return NULL;
}
理论知识参考文献
- 《算法通关手册（LeetCode）》
- 《数据结构与算法分析》
- 《计算机程序设计艺术》
热门推荐
被摩托车撞了对方全责怎么赔偿
专家支招：8个实用方法帮助孩子辨别网络虚假信息
中医“救急”良方多：专访36年中医急诊专家姚卫海
重庆江津：居民发现受伤老鹰，多方联动及时救助
七猫稿件已提终审：法律流程、注意事项与实务分析
房子要有什么证件才属于自己？详解购房全流程
杭州购房政策最新整理（10月版）！贷款、税费、落户、购房补贴...
萍乡去海南坐哪辆列车最近最方便
最新教师绩效工资考核方案
保持耐心和一致性，培养宝宝自主入睡
唐山：数智化转型让高端装备制造“加速跑”
中国航空科幻启航！中国航天工业集团推出硬核科幻IP“南天门计划”
包产到户后，小岗村的发展蒸蒸日上！如今也面临诸多困境
公证委托书的写作要点及注意事项
珍爱健康，从预防职业病开始
三道鳞孩子补钙的一道菜
U-2侦察机被击落背后的苏联克格勃秘密行动揭秘
美空军最神秘的战机：保密程度仅次于B2轰炸机，曾被误认为UFO
增程车VS插混车：深度解析及选购指南
留置送达的程序有哪几个步骤
如何清除白头粉刺？解析粉刺种类、原因，以及对付粉刺的4个对策
白头粉刺痘痘用什么药膏好的快呢
Nano Lett：负载益生菌的胞内凝胶化巨噬细胞用于治疗结肠炎
本科论文初稿写作指南：从选题到定稿的完整流程
藕粉的做法大全
和妹妹吵架了怎么办？姐妹情深，如何化解矛盾和重建关系？！
投资还是借贷，法院如何认定？
《光明王》新版深度解析
英雄联盟竞技赛中的团队协作精髓探讨
对我国法定存款准备金政策的评价及创新性政策建议