当前位置: 首页 > news >正文

详细介绍关于链表【数据结构】

文章目录

    • 链表
      • 单链表
        • 尾插
        • 头插
        • 尾删
          • 第一种方式删除
          • 第二种
        • 头删
        • 查找
        • pos之前插入
        • pos位置删除
        • pos后面插入
        • pos位置后面删除

链表

顺序表缺点:

  • 空间不够了 需要扩容,但是扩容是有消耗的
  • 头部或中间位置需要插入或删除,需要挪动 ,但是挪动是有消耗的
  • 避免频繁扩容 ,一次一般都是去按倍数去扩2倍,可能存在一定的空间浪费
    我们采用链表解决问题

顺序表优点:

  • 支持随机访问

链表优点:

  • 按照需求申请空间,不用了就释放空间,更加合理的运用空间
  • 头部中间插入或删除数据 ,不需要挪动数据,不存在空间浪费

缺点:

  • 每插入一个数据,都需要存一个指针去链接后面的数据节点 ,
  • 不支持随机访问,用下标直接访问第i个( arr[ i ] )

单链表

typedef struct  SListNode  // 单链表
{SLDataType data;struct  SListNode* next;
}SLTNode; //单链表类型
void SListPrint(SLTNode* phead)
{SLTNode* cur= phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}
}

在这里插入图片描述

尾插

尾插的本质是原来的尾节点需要存储新的尾节点地址

void SListPushBack(SLTNode** pphead  , SLDataType x) // 尾插
{                                                                                              //插入SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;if (*pphead == NULL) //链表中一个节点都没有,就不用去找尾{*pphead = newnode;}else{//找到尾节点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}

在这里插入图片描述

头插

 SLTNode *  BuySingListNode(SLDataType x)//创建节点
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode; 
}
void SListPushFront(SLTNode** pphead, SLDataType x) // 头插
{//创建节点SLTNode* newnode =BuySingListNode(x);newnode->next = *pphead;*pphead = newnode;
}

在这里插入图片描述

尾删

第一种方式删除
void SListPopBack(SLTNode** pphead)  // 尾删
{assert(*pphead != NULL);  //头指针是否为空//只有一个节点if ( (*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//两个或两个以上的节点else{SLTNode* p = NULL;//找尾节点SLTNode* tail = *pphead;while (tail->next != NULL){p = tail;//p指针记录倒数第二个节点 ,并且将节点置空tail = tail->next;}free(tail);//删除tail = NULL;p->next = NULL;}}

在这里插入图片描述

第二种
void SListPopBack(SLTNode** pphead)  // 尾删
{assert(*pphead != NULL);  //头指针是否为空//只有一个节点if ( (*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else  //不创建临时变量p的方式去尾删{//找尾节点SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}//删除free(tail->next);tail->next = NULL;}}

在这里插入图片描述

头删

void SingleListPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;}

在这里插入图片描述

查找

int  SingleListFind(SLTNode* phead, SingleListDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

pos之前插入

void SingleListInsert(SLTNode** pphead, SLTNode* pos, SingleListDataType x)
{assert(pos);assert(pphead);//只有一个节点相当于头插if (*pphead ==pos){SingleListPushFront(pphead ,x);}else//多个节点{//找到pos的前一个位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySingListNode(x);prev->next = newnode;newnode->next = pos;}
}

在这里插入图片描述

pos位置删除

void SingleListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);//只有一个节点相当于头删if (*pphead==pos){SingleListPopFront(pphead);}// 多个节点else{//找到pos的前一个位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}

在这里插入图片描述

pos后面插入

void SingleListInsertAfter(SLTNode* pos, SingleListDataType x)  //pos后面插入
{assert(pos);SLTNode* newnode = BuySingListNode(x);newnode->next = pos->next;pos->next = newnode;
}

在这里插入图片描述

pos位置后面删除

void SingleListEraseAfter(SLTNode* pos)   // 从pos后面删除
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

在这里插入图片描述

如果你觉得这篇文章对你有帮助,不妨动动手指给点赞收藏加转发,给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力!!!

http://www.lryc.cn/news/32739.html

相关文章:

  • 2.3 二分搜索技术
  • RWEQ模型的土壤风蚀模数估算、其变化归因分析
  • 学习streamlit-1
  • GPS定位知识介绍
  • 【Linux】理解Linux环境变量
  • ISCSI块存储-集群
  • 11.Maxwell 部署
  • 一文速学-GBDT模型算法原理以及实现+Python项目实战
  • 前端——2.HTML基本结构标签
  • OAK深度相机使用不同镜头和本地视频流进行模型推理
  • [项目] Boost搜索引擎
  • 解决新版QGIS找不到Georeferencer插件
  • c---冒泡排序模拟qsort
  • Java知识复习(十四)JS
  • 代码随想录刷题-数组-移除元素
  • 聚观早报 |拼多多跨境电商业务正式登陆澳洲;中国加快6G网络研发
  • MDK Keil5 创建Stm32工程-理论篇(这里以Stm32F103Zet6为例)
  • 应届大学生学什么技术好?哪些技术适合年轻人?
  • 车企数据分类分级的实践指南出炉!“数据安全推进计划”发布,奇点云参编
  • Nginx学习 (2) —— 虚拟主机配置
  • Java 动态代理简述和实例
  • Unity编译器扩展(Advanced Editor Scripting)
  • AFR机制及流程介绍
  • 9.Hbase 部署
  • 【maven 学习记录】
  • NB-IOT宣传这么多年,这次总算用好了吧
  • sort函数对结构体|pair对组|vector容器|map排序|二维数组的第x列 的排序
  • Java定时器Timer的使用
  • MySQL安装和配置
  • openpnnp - 载入板子后,要确定板子的放置角度