单链表（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）》
- 《数据结构与算法分析》
- 《计算机程序设计艺术》
热门推荐
遇龙河风景区游玩指南：探秘国内遇龙河旅游最佳攻略
男子吃饭突然"石化"手握筷子待急救！医生揭血糖低出事 拆解10症状教自救方法
当糖尿病遇上低血糖，该如何应对？要怎么预防？
“十一”假期，安全第一！这些安全提示请收藏！
第一届“儿童友好公益节”——发现每个孩子都是一座宝藏
小米用户必看：如何轻松设置一键锁屏？
低GI土豆粉条，健康吃法大揭秘！
土豆粉条：糖尿病患者的低GI食材新选择
谷医堂教你科学吃土豆粉条控血糖
糖尿病患者的福音：土豆粉条真的不升糖？
长白山秋冬打卡：天池+长白瀑布全攻略
《荒野起源》带你探秘长白山
无为市房价新动向：政策调控下的跌势分析
江苏淮安十大必吃美食：从软兜长鱼到十三香龙虾，每一道都值得一试！
《三角洲行动》烽火地带战备攻略：武器装备与药品配置详解
《三角洲行动》机密图生存攻略：武器选择与战术配合详解
旅途必备：这些便携美食让你飞得更健康
福建长乐显应宫：千年古建里的神秘传奇
长乐显应宫：融合郑和与妈祖文化的神秘古迹
TSA最新安检规则：轻松掌握飞机食物携带技巧
飞机旅行带吃的？这些小技巧你必须知道！
漳州美食与茶文化：闽南年味的独特魅力
锂电池维修保养的重要性
沈阳中街到方特乐园最新交通攻略
深部脑刺激术：最新帕金森病手抖疗法解析
帕金森病患者的饮食管理指南
揭秘三角洲部队：如何打造超强心理素质？
跟着《去有风的地方》，打卡沙溪古镇古戏台
用认知负荷理论破解函数学习难题
秋冬打卡漳州必吃：卤面、豆花粉丝、猫仔粥