链表
一、链表
💦 链表的概念和结构
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
🎗 这里就来实现一个简单的链表(这里有三个文件:SList.h、SList.c、Test.c)
SList.h文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SListPrint(SLTNode* phead);
SList.c文件
#include"SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
Test.c文件
#include"SList.h"
void TestSList1()
{
SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
n1->data = 1;
SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
n2->data = 2;
SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
n3->data = 3;
SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
n4->data = 4;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
SLTNode* plist = n1;
SListPrint(plist);
}
int main()
{
TestSList1();
return 0;
}
💨 结果
⚠ 注意
1️⃣ 从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
2️⃣ 现实中的结点一般都是从堆上申请出来的
3️⃣ 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
假设在32位系统上,结点中值域为int类型,则一个节点的大小为8个字节,则也可能有下述链表:
💦 链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
注:本章只了解单链表
1️⃣ 单向或者双向
2️⃣ 带头或者不带头
3️⃣ 循环或者非循环
🎗虽然有这么多的链表结构,但是实际中最常用的只有两种结构
1️⃣ 无头单向非循环链表
2️⃣ 带头双向循环链表
⚠ 注意:
▶ 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
▶ 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。
💦 单链表各接口实现 (动图分析)
这里写了三个文件:
1️⃣ SList.h文件,用于函数声明
2️⃣ SList.c文件,用于函数的定义
3️⃣ Test.c文件,用于测试函数
⭕ 首先需要定义结构体SLTNode
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//存储整型数据
struct SListNode* next;//指向下一个节点的地址
}SLTNode;
并定义plist变量 -> Test.c
SLTNode* plist = NULL;
⭕ 接口1:开辟空间 (BuySListNode)
函数原型:
函数实现:
SLTNode* BuySListNode(SLTDataType x)
{
//每次调用开辟一个节点的空间
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
printf("malloc fail\n");
exit(-1);
}
node->data = x;
node->next = NULL;
//开辟成功,返回地址
return node;
}
⭕ 接口2:输出数据 (SListPrint)
函数原型:
函数实现:
void SListPrint(SLTNode* phead)
{
//据情况分析,此处不需要断言,因为我们想在空链表时输出NULL
//assert(phead);
SLTNode* cur = phead;
//遍历
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
⭕ 接口3:尾插数据 (SListPushBack),详解请看下图:
函数原型:
函数实现:
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
//据析,指针可能为空,但是指针的地址不可能为空,所以需要断言(pphead就是plist的地址),且这里不能断言*pphead,因为这里空链表是可以处理的
assert(pphead);
//特殊情况
//1、空链表
if (*pphead == NULL)
{
//调用BuySListNode去开辟新节点
SLTNode* newnode = BuySListNode(x);
*pphead = newnode;
}
//2、非空链表
else
{
SLTNode* tail = *pphead;
//找尾 - NULL
while(tail->next != NULL)
{
tail = tail->next;
}
//开辟节点
SLTNode* newnode = BuySListNode(x);
tail->next = newnode;
}
}
📐 测试
⭕ 接口4:头插数据 (SListPushFront),详解请看下图:
函数原型:
函数实现:
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//对于首插来说,没有特殊情况,以下代码适用于空链表和非穿链表
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
📐 测试
⭕ 接口5:尾删数据 (SListPopBack),详解请看下图(2种方式):
方式1:
方式2:
函数原型:
函数实现:
void SListPopBack(SLTNode** pphead)
{
//据析,这里需要断言plist的地址是否传成NULL了;以及没有节点的情况
assert(pphead);
assert(*pphead);
//特殊情况
//一个节点的情况
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//多个节点的情况 - 找尾
//1.先指向第一个节点的位置
SLTNode* tail = *pphead;
//2.删尾(错误示范) - 这样删尾会造成野指针(因为每个节点都是一个局部节点,如果这样释放掉后,则前一个节点的next就是一个野指针)
/*while (tail->next != NULL)
{
tail = tail->next;
}
free(tail);
tail = NULL; */
//2.删尾(正确示范1)
/*while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;*/
//2.删尾(正确示范2) - 双指针
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail->next);
prev->next = NULL;
}
}
📐 测试
⭕ 接口6:头删数据 (SListPopFront),详解请看下图
函数原型:
函数实现:
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
//以下代码能适用于一个节点和多个节点,如果只有一个节点的情况,先备份NULL,就将NULL赋值于*pphead
//备份第2个节点的地址
SLTNode* temp = (*pphead)->next;
//释放第一个节点
free(*pphead);
//再将拷贝的节点链接起来
(*pphead) = temp;
}
📐 测试
⭕ 接口7:查找数据 (SListFind)
函数原型:
函数实现:
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
//据析,如果是空链表时,这里就无法查找,所以需要断言
assert(phead);
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;//返回x所在节点的地址
}
else
{
cur = cur->next;
}
}
return NULL;//找不到返回空
}
⭕ 接口8:指定的数之前插入数据 (SlistInser),不支持尾插,详解请看下图
因此可以看出单链表不适合在指定的数的前面插入的,因为它需要前面一个节点的地址
函数原型:
函数实现:
void SlistInser(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//据析,这里需要调用SlistFind函数来配合使用,所以这里不需要判断是否为空链表,因为SlistFind函数内已经断言过了
assert(pphead);
assert(pos);
//特殊情况
//1、调用头插的接口
if (*pphead == pos)
{
SListPushFront(pphead, x);
}
//2、非头插入 - 不包含尾插
else
{
//找pos位置的前一个节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
//注意这里它们前后链接时可以颠倒
newnode->next = pos;
prev->next = newnode;
}
}
📐 测试
⭕ 接口9:指定的数之后插入数据 (SlistInser),不支持头插,详解请看下图
函数原型:
函数实现:
void SlistInserAfter(SLTNode* pos, SLTDataType x)
{
//据析,这里也不需要判断空链表的情况
assert(pos);
SLTNode* newnode = BuySListNode(x);
//注意,必须先把pos后面节点的地址交给newnode->next,再将newnode的地址交给pos->next;两者不能颠倒
newnode->next = pos->next;
pos->next = newnode;
}
📐 测试
⭕ 接口10:指定的数删除 (SlistErase),详解请看下图
因此可以看出单链表不适合在删除指定的数,因为它需要前面一个节点的地址
函数原型:
函数实现:
void SlistErase(SLTNode** pphead, SLTNode* pos)
{
//据析,这里也不需要判断空链表的情况
assert(pphead);
//1、调用头删
if (pos == *pphead)
{
SListPopFront(pphead);
}
//2、其余节点 - 包括尾删
else
{
//找pos位置的前一个节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
📐 测试
⭕ 接口11:指定的数之后删除 (SlistEraseAfter),详解请看下图
函数原型:
函数实现:
void SlistEraseAfter(SLTNode* pos)
{
//据析如果那个数后面为NULL,就删除不了,需要断言
assert(pos);
assert(pos->next);
//拷贝一份
SLTNode* temp = pos->next->next;
free(pos->next);
pos->next = NULL;
pos->next = temp;
}
📐 测试
⭕ 接口12:统计 (SListSize)
函数原型:
函数实现:
int SListSize(SLTNode* phead)
{
//这里不需要断言
int size = 0;
SLTNode* cur = phead;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
📐 测试
⭕ 接口13:判空 (SListSize)
函数原型:
函数实现:
bool SListEmpty(SLTNode* phead)
{
//判空,空是真,非空是假
//写法1
//return phead == NULL ? true : false;
//写法2
//if (phead == NULL)
//{
// return true;
//}
//else
//{
// return false;
//}
//写法3
return phead == NULL;
}
📐 测试
⭕ 接口14:销毁 (SListDestory)
函数原型:
函数实现:
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
📐 测试
📝 完整代码
SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//存储整型数据
struct SListNode* next;//指向下一个节点的地址
}SLTNode;
//只读的函数接口
void SListPrint(SLTNode* phead);
int SListSize(SLTNode* phead);
bool SListEmpty(SLTNode* phead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
SLTNode* BuySListNode(SLTDataType x);
void SListInserAfter(SLTNode* pos, SLTDataType x);
void SListEraseAfter(SLTNode* pos);
void SListDestory(SLTNode** pphead);
//读写的函数接口
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
void SListInser(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SListErase(SLTNode** pphead, SLTNode* pos);
SList.c
#include"SList.h"
void SListPrint(SLTNode* phead)
{
//据情况分析,此处不需要断言,因为我们想在空链表时输出NULL
//assert(phead);
SLTNode* cur = phead;
//遍历
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuySListNode(SLTDataType x)
{
//每次调用开辟一个节点的空间
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
printf("malloc fail\n");
exit(-1);
}
node->data = x;
node->next = NULL;
//开辟成功,返回地址
return node;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
//据析,指针可能为空,但是指针的地址不可能为空,所以需要断言(pphead就是plist的地址),且这里不能断言*pphead,因为这里空链表是可以处理的
assert(pphead);
//特殊情况
//1、空链表
if (*pphead == NULL)
{
//调用BuySListNode去开辟新节点
SLTNode* newnode = BuySListNode(x);
*pphead = newnode;
}
//2、非空链表
else
{
SLTNode* tail = *pphead;
//找尾 - NULL
while(tail->next != NULL)
{
tail = tail->next;
}
//开辟节点
SLTNode* newnode = BuySListNode(x);
tail->next = newnode;
}
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//对于首插来说,没有特殊情况,以下代码适用于空链表和非空链表
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopBack(SLTNode** pphead)
{
//据析,这里需要断言plist的地址是否传成NULL了;以及没有节点的情况
assert(pphead);
assert(*pphead);
//特殊情况
//一个节点的情况
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//多个节点的情况 - 找尾
//1.先指向第一个节点的位置
SLTNode* tail = *pphead;
//2.删尾(错误示范) - 这样删尾会造成野指针(因为每个节点都是一个局部节点,如果这样释放掉后,则前一个节点的next就是一个野指针)
/*while (tail->next != NULL)
{
tail = tail->next;
}
free(tail);
tail = NULL; */
//2.删尾(正确示范1)
/*while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;*/
//2.删尾(正确示范2) - 双指针
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail->next);
prev->next = NULL;
}
}
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
//以下代码能适用于一个节点和多个节点,如果只有一个节点的情况,先备份NULL,就将NULL赋值于*pphead
//备份第2个节点的地址
SLTNode* temp = (*pphead)->next;
//释放第一个节点
free(*pphead);
//再将拷贝的节点链接起来
(*pphead) = temp;
}
int SListSize(SLTNode* phead)
{
//这里不需要断言
int size = 0;
SLTNode* cur = phead;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
bool SListEmpty(SLTNode* phead)
{
//判空,空是真,非空是假
//写法1
//return phead == NULL ? true : false;
//写法2
//if (phead == NULL)
//{
// return true;
//}
//else
//{
// return false;
//}
//写法3
return phead == NULL;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
//据析,如果是空链表时,这里就无法查找,所以需要断言
assert(phead);
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;//返回x所在节点的地址
}
else
{
cur = cur->next;
}
}
return NULL;//找不到返回空
}
void SListInser(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//据析,这里需要调用SlistFind函数来配合使用,所以这里不需要判断是否为空链表,因为SlistFind函数内已经断言过了
assert(pphead);
assert(pos);
//特殊情况
//1、调用头插的接口
if (*pphead == pos)
{
SListPushFront(pphead, x);
}
//2、非头插入 - 不包含尾插
else
{
//找pos位置的前一个节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
//注意这里它们前后链接时可以颠倒
newnode->next = pos;
prev->next = newnode;
}
}
void SListInserAfter(SLTNode* pos, SLTDataType x)
{
//据析,这里也不需要判断空链表的情况
assert(pos);
SLTNode* newnode = BuySListNode(x);
//注意,必须先把pos后面节点的地址交给newnode->next,再将newnode的地址交给pos->next;两者不能颠倒
newnode->next = pos->next;
pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
//据析,这里也不需要判断空链表的情况
assert(pphead);
//1、调用头删
if (pos == *pphead)
{
SListPopFront(pphead);
}
//2、其余节点 - 包括尾删
else
{
//找pos位置的前一个节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
void SListEraseAfter(SLTNode* pos)
{
//据析如果那个数后面为NULL,就删除不了,需要断言
assert(pos);
assert(pos->next);
//拷贝一份
SLTNode* temp = pos->next->next;
free(pos->next);
pos->next = NULL;
pos->next = temp;
}
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
Test.c
#include"SList.h"
void TestSList1()
{
SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
n1->data = 1;
SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
n2->data = 2;
SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
n3->data = 3;
SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
n4->data = 4;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
SLTNode* plist = n1;
SListPrint(plist);
}
void TestSList2()
{
//定义plist变量
SLTNode* plist = NULL;
//尾插
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
//头插
SListPushFront(&plist, 0);
SListPushFront(&plist, -1);
SListPushFront(&plist, -2);
SListPrint(plist);
//尾删
SListPopBack(&plist);
SListPrint(plist);
//头删
SListPopFront(&plist);
SListPrint(plist);
//查找 - 查找空链表时,断言报错;查找失败返回NULL;查找成功返回x所在的节点的地址
SLTNode* pos = SListFind(plist, 0);
if (pos)
{
printf("找到了\n");
}
//指定的数之前插入数据 - 此函数实现不了尾插
pos = SListFind(plist, -1);
if (pos)//找到了才插入数据
{
SListInser(&plist, pos, -2);
}
SListPrint(plist);
//指定的数之后插入数据 - 此函数实现不了头插
pos = SListFind(plist, 3);
if (pos)
{
SListInserAfter(pos, 4);
}
SListPrint(plist);
//指定的数删除
pos = SListFind(plist, 4);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
//删除指定的数之后的数
pos = SListFind(plist, 2);
if (pos)
{
SListEraseAfter(pos);
}
SListPrint(plist);
//统计
printf("%d\n", SListSize(plist));
//判空,空是真,非空是假
printf("%d\n", SListEmpty(plist));
//销毁
SListDestory(&plist);
}
int main()
{
TestSList2();
return 0;
}
💨 结果
四、顺序表和链表的区别和联系
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持 O(1) | 不支持 O(N) |
任意位置插入或删除元素 | 可能需要搬移元素,效率低 | 只需要修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率、缓存命中率 | 高 | 低 |
💨 总结:
链表和顺序表没有谁更优,它们各有优缺点,相辅相成
备注:缓存利用率参考存储体系结构以及局部原理性
假设写了一个程序,实现分别对顺序表和链表上的每个数据+1,那么这个程序会编译成指令,然后CPU再执行
CPU运算的速度很快,那内存的速度跟不上,CPU一般就不会直接访问内存,而是把要访问的数据先加载到缓存体系,如果是 ≤ 8byte的数据 (寄存器一般是8byte),会直接到寄存器;而大的数据,会到三级缓存,CPU直接跟缓存交互。
CPU执行指令运算要访问内存,先要取0x10 (假设) 的数据,拿0x10去缓存中找,发现没有 (不命中) ,这时会把主存中这个地址开始的一段空间都读进来 (缓存)。
如果是整型数组,下一次访问0x14、0x18… 就会命中
如果是链表,先取第1个节点0x60,不命中;再取第2个0x90,不命中…。这样会造成一定的缓存污染
- 点赞
- 收藏
- 关注作者
评论(0)