数据结构——链表（超详细解读）
创作时间:
作者:
@小白创作中心
数据结构——链表（超详细解读）
引用
CSDN
1.
https://blog.csdn.net/2303_81146519/article/details/142530281
链表是一种常见的数据结构，它通过指针将数据元素链接在一起，形成一个线性序列。与顺序表不同，链表的元素在内存中可以是不连续的，这使得链表在插入和删除操作上具有更高的效率。本文将详细介绍链表的基本概念、分类以及单链表的各种操作实现。
一、链表的概念和结构
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表的基本组成单元）组成，结点可以在运行时动态生成。
图中的phead指针中存放的是第一个结点的地址，根据这个地址可以找到这个结构体，又因为这个结构体中存放了下一个结构体的地址，所以又可以找到第二个结构体，循环往复就可以找到所有的结点，直到存放空地址的结构体。
注：图中的箭头实际上是不存在的，这里只是为了方便理解。
注意：
- 从图中可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。
- 现实中的结点一般都是从堆上申请出来的。
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
二、链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
虽然链表结构如此之多，但是我们常用的就只有两种：
- 单链表：无头+单向+非循环
- 双链表：无头+双向+非循环
三、单链表的实现
所谓单链表就是无头+单向+非循环 链表。
动态申请节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
return newnode;
}
单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
if (*(pplist) == NULL)
{
*pplist = newnode;
}
else
{
SListNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
newnode->next = *pplist;
*pplist = newnode;
}
}
单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* tail = *pplist;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
单链表的头删
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
}
单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
SListNode* next = pos->next;
pos->next = newnode;
newnode->next = next;
}
单链表在pos位置之前插入
void SListInsertFront(SListNode** pplist, SListNode* pos, SLTDateType x)
{
assert(pos);
assert(*pplist);
if (pos == *pplist)
{
SListPushFront(pplist, x);
}
else
{
SListNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
newnode->next = pos;
prev->next = newnode;
}
}
删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos)
{
assert(pos);
assert(*pplist);
if (pos == *pplist)
{
SListPopFront(pplist);
}
else
{
SListNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* next = pos->next;
free(pos);
prev->next = next;
}
}
单链表的销毁
void SListDestroy(SListNode** pplist)
{
assert(*pplist);
while (*pplist)
{
SListNode* prev = *pplist;
*pplist = (*pplist)->next;
free(prev);
}
}
四、完整代码
SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
} SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsertFront(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 删除pos位置
void SListErase(SListNode** pplist, SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** pplist);
SList.c
#include "SList.h"
void SListPrint(SListNode* plist)
{
assert(plist);
while (plist)
{
printf("%d ", plist->data);
plist = plist->next;
}
printf("NULL\n");
}
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
assert(newNode);
newNode->data = x;
newNode->next = NULL;
return newNode;
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* newNode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newNode;
}
else
{
SListNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newNode;
}
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newNode = BuySListNode(x);
newNode->next = *pplist;
*pplist = newNode;
}
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* tail = *pplist;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
while (plist)
{
if (plist->data == x)
{
return plist;
}
plist = plist->next;
}
return NULL;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
SListNode* next = pos->next;
pos->next = newnode;
newnode->next = next;
}
void SListInsertFront(SListNode** pplist, SListNode* pos, SLTDateType x)
{
assert(pos);
assert(*pplist);
if (pos == *pplist)
{
SListPushFront(pplist, x);
}
else
{
SListNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
newnode->next = pos;
prev->next = newnode;
}
}
void SListErase(SListNode** pplist, SListNode* pos)
{
assert(pos);
assert(*pplist);
if (pos == *pplist)
{
SListPopFront(pplist);
}
else
{
SListNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* next = pos->next;
free(pos);
prev->next = next;
}
}
void SListDestroy(SListNode** pplist)
{
assert(*pplist);
while (*pplist)
{
SListNode* prev = *pplist;
*pplist = (*pplist)->next;
free(prev);
}
}
链表和顺序表是两种常见的线性数据结构，它们各有优劣。链表在插入和删除操作上具有更高的效率，而顺序表在随机访问上具有优势。理解这两种数据结构的原理和使用场景，对于编写高效的数据处理程序至关重要。
热门推荐
心电图不合格会当场复检吗？
监事有哪些权利？监事如何行使这些权利？
高血压如何影响心脏健康？
痛风可以吃肉吗？这份详细的饮食指南请收好
Ubuntu忘记登录密码重置步骤
痛风患者想吃海鲜怎么办？这篇一定要看！
智利杯前瞻：科金博与伊基克体育的对决
全国人均储蓄超10万，你的存款达标了吗？ 各地存款差距大解析
山东聊城十大名吃
征收维权中咨询律师的正确姿势，你应该知道点儿
必看，什么样的痣容易恶变！
家里室内养什么花好，让家居增添活力与舒适
快速降血脂肪3大方法！營養師：多吃7大食物、5大飲食禁忌
2024年植物害虫防治新策略
伯里克利改革：雅典民主的巅峰与隐忧
如何更改WiFi的DNS设置以优化网络连接？
伯里克利公民权：只要加入雅典就可以成为公民吗？
苯磺酸氨氯地平有什么副作用？苯磺酸氨氯地平是如何降血压的？
欧盟“排放池”开张 谁是大赢家
一集爆红！这部古装剧让我彻夜追剧，收视率一夜破千万
欧洲车企百亿罚款危机，为中国车企带来数十亿碳机遇
芭蕾舞剧《爱丽丝梦游仙境》：奇妙手段再现童话瑰丽想象
有氧、无氧与间歇训练如何影响脂肪代谢？
高效加湿器选购指南：从加湿能力到智能化功能，全方位解析选购要点
眼压高的缓解方法
脸型以及如何充分利用它们
六个关键词！打开聊城高质量发展“密码”
恩瓦内里：天赋异禀，阿森纳未来的中场大师
腰痛关节痛吃什么药有效果呢
最抽象的数学思想——无穷，一种复杂的结构，一种令人敬畏的奥秘