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

数据结构第三篇【链表的相关知识点一及在线OJ习题】

数据结构第三篇【链表的相关知识点一及在线OJ习题】

      • 链表
      • 链表的实现
      • 链表OJ习题
      • 顺序表和链表的区别和联系

本文章主要讲解关于链表的相关知识,喜欢的可以三连喔
😀😃😄😄😊😊🙃🙃
在这里插入图片描述
😀😃😄😄😊😊🙃🙃

链表

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
单向 双向
带头 不带头
循环 非循环

单链表,双向链表,循环链表如下图所示
在这里插入图片描述
带头,不带头,如下图所示
在这里插入图片描述
虽然有这么多的链表的结构,但是我们重点掌握两种:

  • 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

在这里插入图片描述

  • 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表.

在这里插入图片描述

链表的实现

// 1、无头单向非循环链表实现
public class SingleLinkedList {//头插法
public void addFirst(int data);//尾插法
public void addLast(int data);//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);//删除第一次出现关键字为key的节点
public void remove(int key);//删除所有值为key的节点
public void removeAllKey(int key);//得到单链表的长度
public int size();public void display();public void clear();}
 // 2、无头双向链表实现
public class DoubleLinkedList {//头插法
public void addFirst(int data);//尾插法
public void addLast(int data);//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);//删除第一次出现关键字为key的节点
public void remove(int key);//删除所有值为key的节点
public void removeAllKey(int key);//得到单链表的长度
public int size();public void display();public void clear();}

链表OJ习题

大家可以做做习题,感悟链表的精彩
删除链表中等于给定值 val 的所有节点

反转一个单链表

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

输入一个链表,输出该链表中倒数第k个结点。

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

链表的回文结构。

顺序表和链表的区别和联系

顺序表:一白遮百丑 白:空间连续、支持随机访问
丑:1.中间或前面部分的插入删除时间复杂度O(N)
2.增容的代价比较大。

链表:一(胖黑)毁所有
胖黑:以节点为单位存储,不支持随机访问
所有:1.任意位置插入删除时间复杂度为O(1) 2.没有增容问题,插入一个开辟一个空间。

在这里插入图片描述

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

相关文章:

  • RabbitMQ-发布/订阅模式
  • 客运提质增效新模式!苏州金龙客货邮融合公交闪耀2024道路运输展
  • 【Python实战】使用postman测试flask api接口
  • Docker大学生看了都会系列(二、Mac通过Homebrew安装Docker)
  • 探索 Android Studio 中的 Gemini:加速 Android 开发的新助力
  • linux运维——查看网卡实时流量脚本
  • 【三维重建NeRF(三)】Mip-NeRF论文解读
  • 安卓SystemServer进程详解
  • Android studio 连接 adb传输文件到电脑
  • Web学习篇(二)
  • 在Linux/Ubuntu/Debian系统中使用 `tar` 压缩文件
  • Idea-Linux远程开发部署
  • 智能硬件会是下一个风口行业吗?
  • mysql like 查询优化
  • 3389连接器,3389连接器如何进行安全设置
  • 代码随想录训练营Day56:Leetcode647、516
  • LLM主要类别架构
  • 试比较GD32E230系列与L233/235芯片在IIC上使用温度传感器SHT40的异同
  • 超强算力 Orange Pi Kunpeng Pro 开发板基础测评与体验
  • vs - ms官方查看pdb文件内容的例子工程
  • 【excel】设置二级可变联动菜单
  • 8月1-3日西安国际储能产业博览会
  • MySQL事务处理:ACID属性基础与实现概览
  • PostgreSQL 修改表结构卡住不动
  • wvp-gb28181-pro搭建流媒体服务器,内存占用过高问题
  • 项目-双人五子棋对战: websocket的讲解与使用 (1)
  • 性能飙升50%,react-virtualized-list如何优化大数据集滚动渲染
  • 颠覆传统:探索Web3对传统计算机模式的冲击
  • 最适合上班族和宝妈的兼职副业,一天500多,小众副业项目
  • HFish蜜罐实践:网络安全防御的主动出击