您现在的位置是：首页 >技术教程 >数据结构《链表》无头单向非循环-动图详解网站首页技术教程
数据结构《链表》无头单向非循环-动图详解
前言
前面学习了顺序表发现，顺序表虽然好，但也有很多不足的地方，比方说，顺序表是一块连续的物理空间，如果头插或者头删，那么整个数组的数据都要移动。但是链表不一样，链表是通过指针访问或者调整，链表是物理空间是不连续的，通过当前的next指针找到下一个。
插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可
链表的优点：
插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活
目录
链表的概念及结构
概念：
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
结构：
注意：
1.从图上看，链式结构在逻辑上是连续的，但在物理上不一定连续
2.现实中节点一般都是从堆上申请出来的
3.从堆上malloc的空间是按照一定策略来分配的，第二次申请空间可能是连续的，也可能不是
链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向或双向链表：
带头节点或者不带头节点：
循环或者非循环：
最常用的两种链表
无头单向非循环链表：
带头双向循环链表：
————————————————
链表的创建
链表是由数据和指针组成
那么我们在创建链表的时候，需要一个指针指向下一个节点
如下：
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SListNode;
创建新的节点
创建新的节点，把要插入的值放进新的节点的data，然后再把next指针赋成空，最后返回这个节点的指针
//创建新的节点
SListNode* BuySLTNode(SLTDataType x)
{
SListNode* ret = (SListNode*)malloc(sizeof(SListNode));
if (ret == NULL)
{
perror("BuySLTNode");
return NULL;
}
ret->data = x;
ret->next = NULL;
return ret;
}
尾插
既然是尾插，那就是在尾部插入元素
我们可以看到下面是用二级指针接收的，因为传过来的是一级指针的地址，所以我们要用二级指针接收，并且我们使用的时候要解引用，因为我们要改变的是一级指针本身
如果传过来的指针本身就是NULL，那就直接把新的节点赋给传过来的指针
如果不是空，那我们就找尾，找到尾之后，再把新的节点插入到尾部的next指针
注：
tail指针是指向元素当前位置，我们一般不直接使用原有的指针，因为我们要保留第一个元素指针的位置，以便后续使用。
//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode* tail = *pphead;
//找尾
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
头插
我们把新节点的next指向第一个元素的指针，然后再把第一个节点的指针更新为newnode
//头插
void SLTPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
SListNode* tail = *pphead;
newnode->next = *pphead;
*pphead = newnode;
}
尾删
分为三种情况：
1.链表没有元素，那我们直接断言解决
2.如果链表只有一个元素，那我们判断一下，然后free掉第一个指针指向的空间
3.链表多个元素，我们这里选择的是，判断tail->next->next是否为空，如果不为空，我们让tail指针向后走一步，再继续判断，直到tail->next->next为空，我们free掉tail->next即可
//尾删
void SLTPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);//如果*pphead为空，说明链表没有元素
if ((*pphead)->next == NULL)//如果（*pphead）->next为空，说明链表只有一个元素，我们只需要free掉第一个指针指向的空间即可
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
//判断tail->next->next是否为空，如果不为空，tail向后走一步，再判断
while (tail->next->next != NULL)
{
tail = tail->next;
}
//循环不满足，说明tail->next->next为空
//我们只需要free掉tail的next
free(tail->next);
tail->next = NULL;
}
}
头删
分为两种情况：
1.链表为空，直接用断言解决
2.链表多个元素，我们直接用tail指针保留第一个指针的位置，然后再更新第一个位置的指针，最后free掉刚刚保留的tail位置
//头删
void SLTPopFront(SListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
SListNode* tail = *pphead;
*pphead = tail->next;
free(tail);
tail = NULL;
}
查找
把phead指针赋给cur，如果cur->data和要查找的值相同，返回cur，如果不相同让cur继续向后走，直到相同位置，返回cur，如果走到NULL都没有相同的，说明没有。
//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
指定位置插入
进来直接判断pos是不是第一个元素的空间，如果是，直接头插
走到else里，我们定义一个prev指针，记录pos前一个的位置，直到prev的next等于pos，然后把要插入的值放进prev的next位置，再把pos给newnode的next
//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
指定位置删除
判断要删除的节点是否就是第一个节点，如果是，直接调用头删
反之，定义一个prev指针记录pos的前一个位置，直到prev的next指针等于pos的时候，把pos的next赋给prev的next进行拼接，然后free掉pos即可
//指定删除
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
//判断pos是否就是第一个节点
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
pos位置后插入
pos位置后插入相比指定插入，通俗易懂
直接把newnode的next指向pos的next，然后再把pos的next指向newnode
//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
pos位置后删除
把pos的next给del，del是等会要删除的位置
然后pos的next指向del的next，最后free掉del
//pos位置后删除
void SLTEease_After(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
打印
把phead给cur指针，让cur指针往后走，每次cur打印data数据，直到走到NULL。
//打印
void SLTPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL
");
}
销毁
定义一个cur指针，再记录一下cur的下一个位置，然后free掉cur，再把刚刚记录的cur的next位置赋给cur，直到cur走到NULL为止
//销毁
void SLTDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
完整代码
SList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SListNode;
//打印
void SLTPrint(SListNode* phead);
//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SListNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SListNode** pphead);
//头删
void SLTPopFront(SListNode** pphead);
//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x);
//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
//指定删除
void SLTErase(SListNode** pphead, SListNode* pos);
//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x);
//pos位置后删除
void SLTErase_After(SListNode* pos);
//销毁
void SLTDestroy(SListNode** pphead);
SList.c
#include "SList.h"
//打印
void SLTPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL
");
}
//创建新的节点
SListNode* BuySLTNode(SLTDataType x)
{
SListNode* ret = (SListNode*)malloc(sizeof(SListNode));
if (ret == NULL)
{
perror("BuySLTNode");
return NULL;
}
ret->data = x;
ret->next = NULL;
return ret;
}
//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode* tail = *pphead;
//找尾
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//头插
void SLTPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
SListNode* tail = *pphead;
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
//头删
void SLTPopFront(SListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
SListNode* tail = *pphead;
*pphead = tail->next;
free(tail);
tail = NULL;
}
//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
//指定删除
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//pos位置后删除
void SLTEease_After(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void SLTDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
Test.c(测试代码)
void SListTest2()
{
SListNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SListNode* ret = SLTFind(plist, 2);
//SLTPrint(plist);
SLTInsert(&plist, ret, 22);
SLTPrint(plist);
SLTErase(&plist, ret);
SLTPrint(plist);
}
int main()
{
SListTest3();
return 0;
}
下期讲解带头双向循环链表
站长推荐
- SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述