欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 财经 > 金融 > 【数据结构与算法】第3课—数据结构之单链表

【数据结构与算法】第3课—数据结构之单链表

2024/10/22 22:40:41 来源：https://blog.csdn.net/weixin_70620792/article/details/143091673  浏览:  次   关键词：【数据结构与算法】第3课—数据结构之单链表

文章目录

  • 1. 什么是链表
  • 2. 单链表
    • 2.1 单链表的初始化和打印
    • 2.2 单链表的尾插和头插
    • 2.3 单链表的尾删和头删
    • 2.4 单链表查找节点
    • 2.5 单链表在指定位置之前/之后插入数据
    • 2.6 单链表删除节点和删除pos之后的节点
    • 2.7 销毁链表
  • 3. 单链表和顺序表对比

1. 什么是链表

  • 链表是在逻辑结构上连续，而在物理结构上不一定连续的存储结构
  • 链表由一个一个的节点组成，并且这些节点是在堆上申请空间
  • 单链表的每个节点一般有两个变量，一个变量存储数据，另一个变量里面是下一个节点的地址，最后一个节点里面的那个变量存储的是空指针

在这里插入图片描述

在这里插入图片描述

2. 单链表

  • 从前往后，单向的一个链表

2.1 单链表的初始化和打印

  • 初始化

在这里插入图片描述

  • 打印单链表

在这里插入图片描述

2.2 单链表的尾插和头插

  • 尾插

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • 头插

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

2.3 单链表的尾删和头删

  • 尾删

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • 头删

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

2.4 单链表查找节点

在这里插入图片描述

在这里插入图片描述

2.5 单链表在指定位置之前/之后插入数据

  • 单链表在指定位置之前插入数据

在这里插入图片描述

在这里插入图片描述

  • 单链表在指定位置之后插入数据

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

2.6 单链表删除节点和删除pos之后的节点

  • 单链表删除节点pos

在这里插入图片描述

在这里插入图片描述

  • 单链表删除节点pos之后的节点

在这里插入图片描述

在这里插入图片描述

2.7 销毁链表

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

3. 单链表和顺序表对比

  • 顺序表头部/中间的插入删除的时间复杂度是O(N),而单链表头部的插入删除、删除指定位置之后的节点、指定位置之后插入数据的时间复杂度是O(1)
  • 而顺序表尾部插入/删除的时间复杂度是O(1),单链表尾部插入/删除、删除指定位置节点、指定位置之前插入节点的时间复杂度是O(N)
  • 顺序表需要增容，而且存在一定的空间浪费，而单链表每次只需要申请一个节点大小，不存在浪费空间的情况

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词

C# 实现进程间通信的几种方式（完善） 【Qt】控件——Qt多元素控件、常见的多元素控件、多元素控件的使用、List Widget、Table Widget、Tree Widget 【文件的权限 修改文件权限 修改文件属主】 2010-408真题 滑线变阻器的工作原理是什么？ java-如何对vo里面的字段或者Map里面数据进行排序