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

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

news 2025/7/17 9:39:58

文章目录

  • 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)
  • 顺序表需要增容，而且存在一定的空间浪费，而单链表每次只需要申请一个节点大小，不存在浪费空间的情况
http://www.lryc.cn/news/466580.html

相关文章：

  • linux—基础命令及相关知识
  • Spring Boot 实现 WebSocket（注解方式）
  • windows下Qt的安装方法
  • 嵌入式面试题 ARM常见面试题
  • 分布式调度器--Spring Task 的使用
  • Java应用程序的测试覆盖率之设计与实现（四）-- jacoco-maven-plugin
  • UI 提供的 progress-step 要怎么实现?
  • DBSwitch和Seatunel
  • 【日志】力扣刷题 -- 轮转数组
  • Java 项目 Dockerfile 示例：从基础镜像选择到环境变量配置的详细指南
  • WebGL编程指南 - 高级变换与动画基础
  • 银行客户贷款行为数据挖掘与分析
  • 制程质量管理方案设计
  • uniapp移动端优惠券! 附源码!!!!
  • 【分布式技术】中间件-zookeeper安装配置
  • 高等数学 7.6高阶线性微分方程
  • LSP的建立
  • huggingface的数据集下载（linux下clone）
  • Java使用dom4j生成kml(xml)文件遇到No such namespace prefix: xxx is in scope on:问题解决
  • 深入探讨Java中的LongAdder：使用技巧与避坑指南
  • 【本科毕业设计】基于单片机的智能家居防火防盗报警系统
  • C语言 动态数据结构的C语言实现单向链表-2
  • Github 2024-10-23C开源项目日报 Top10
  • ubuntu20.04 opencv4.0 /usr/local/lib/libgflags.a(gflags.cc.o): relocation报错解决
  • android openGL ES详解——混合
  • 计网--物理层
  • 算法的学习笔记—数组中的逆序对(牛客JZ51)
  • Golang | Leetcode Golang题解之第498题对角线遍历
  • 什么是全局污染?怎么避免全局污染?
  • C# 串口通信教程