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

[java基础-集合篇]LinkedList源码粗析

LinkedList 的数据结构

实现List、Deque 接口,基于 双向链表实现的列表。与基于数组的 ArrayList 不同,基于链表的LinkedList 允许在列表的任何位置快速地插入和删除元素。
Java中LinkedList实现了Deque,它提供了 add, offer, remove, poll, element, peek 等方法,因此可以视LinkedList为一个基于链表的 双向队列
双向链表的高效删除、添加元素,相较低的查询效率LinkedList也具备。
LinkedList 的每个元素都包含三个部分:
  • 数据本身
  • 指向前一个元素的引用(前驱)
  • 指向后一个元素的引用(后继)
这种双向链接使得 LinkedList 可以很容易地向前或向后遍历,并且可以在 O(1) 时间内完成插入和删除操作。

LinkedList方法

get(int index)方法

调用node(int index)方法遍历链表返回指定index元素

add(E e)方法

使用add添加元素时,默认插入到尾部,所以不需要查找后更新|添加,实现复杂度是O(1)。
注意:LinkedList不需要扩容
由构造方法可以看出来,LinkedList是允许null值的,且null值数量不做限制

add(int index, E element)方法

找到原来的Index位置的元素,然后插入。 插入操作=创建一个新的节点+并将其连接到原index处节点前

remove()方法

这个方法是实现自Deque接口,具有队列性质,移除first节点

remove(int index)

这个是List的实现,遍历找出指定index的节点后然后移除

remove(Object o)方法

注意, 方法只会移除LinkedList链表中第一个匹配对象,如果返回false表示没有次对象。

LinkedList 的特点

  • 插入和删除操作快:由于双向链表的特性,可以在 O(1) 时间内完成插入和删除。
  • 不适合随机访问:相对于数组来说,链表的随机访问较慢,因为必须从头开始遍历链表直到找到所需的元素。
  • 内存消耗较大:每个元素除了存储自身的数据外,还需要额外的空间来保存前后节点的引用,因此比数组占用更多的内存。
  • 允许空值

优化点

remove(Object o)方法移除元素时,先进行空值 == null判断,然后item比较时使用 == null判断,这样比equals高效

LinkedList 相关的面试题

下面列出了一些与 LinkedList 相关的常见面试题:

1.解释什么是双向链表,并描述其优势。

- 双向链表是一种链表,其中每个节点包含对前一个节点和下一个节点的引用。这使得可以从前向后和从后向前遍历列表,也简化了插入和删除操作。

- 在 LinkedList 中,插入操作只需要修改相关节点的前后指针即可,因此时间复杂度为 O(1)。

2.LinkedList 和 ArrayList 之间的区别是什么?

- LinkedList 使用链表实现,适合频繁的插入和删除操作;ArrayList 使用数组实现,适合随机访问元素。

3.为什么 LinkedList 的 get(int index) 方法的时间复杂度是 O(n)?

- 因为 LinkedList 需要从头部或尾部开始遍历到指定索引的位置,最坏情况下可能需要遍历整个列表。

- LinkedList 提供了对 ListIterator 的支持,允许用户在迭代过程中添加、删除或修改元素。

4.如何检测 LinkedList 中是否存在环?(理论上标准的LinkedList不会出现环形链表)

- 常见的方法是使用 Floyd's Cycle-Finding Algorithm 或者称为龟兔赛跑算法,通过两个不同速度的指针来检测循环的存在。

5.如何反转一个 LinkedList?

- 反转 LinkedList 的一种方法是从头节点开始,逐个交换每个节点的前后指针,直到到达最后一个节点。

推荐资料

https://www.hello-algo.com/

相关文章:

[java基础-集合篇]LinkedList源码粗析

LinkedList 的数据结构 实现List、Deque 接口,基于 双向链表实现的列表。与基于数组的 ArrayList 不同,基于链表的LinkedList 允许在列表的任何位置快速地插入和删除元素。 Java中LinkedList实现了Deque,它提供了 add, offer, remove, poll, …...

面试:C++类成员初始化顺序

1、非静态数据成员:按它们在类定义的声明顺序初始化,不会按它们在初始化列表的顺序。 2、静态数据成员:在main函数启动之前,并且只初始化一次 3、基类构造函数:如果类从一个或多个基类继承而来,基类的构造…...

【Python】Python与C的区别

文章目录 语句结束符代码块表示变量声明函数定义注释格式Python的标识符数据输入input()函数数据输出print()函数 语句结束符 C 语言 C 语言中每条语句必须以分号;结束。例如,int a 10;、printf("Hello, World!");。分号是语句的一部分,用于…...

[开源]自动化定位建图系统(视频)

系统状态机: 效果展示: 1、 机器人建图定位系统-基础重定位,定位功能演示 2、 机器人建图定位系统-增量地图构建,手动回环检测演示 3、… 开源链接: https://gitee.com/li-wenhao-lwh/lifelong-backend Qt人机交互…...

ISP流程--去马赛克详解

前言 本期我们将深入讨论ISP流程中的去马赛克处理。我们熟知,彩色图像由一个个像元组成,每个像元又由红、绿、蓝(RGB)三通道构成。而相机传感器只能感知光的强度,无法直接感知光谱信息,即只有亮暗而没有颜色…...

Objective-C语言的软件工程

Objective-C语言的软件工程探讨 引言 在软件工程的领域中,编程语言的选择是至关重要的。Objective-C,作为一种为苹果公司的macOS和iOS操作系统而开发的编程语言,凭借其灵活性和强大的功能被广泛应用于应用开发。然而,随着Swift等…...

Objective-C语言的语法糖

Objective-C语言的语法糖探秘 在编程语言的发展历程中,语法糖(Syntactic Sugar)是一个颇具趣味性和重要性的概念。它让编程的表达更加简洁直观,同时提高了代码的可读性和可维护性。Objective-C 作为一种面向对象的编程语言&#…...

设计模式中的代理模式

在Java中,代理模式(Proxy Pattern)可以通过静态代理和动态代理两种主要方式实现。 一、静态代理模式 在编译时就已经确定了代理类和被代理类的关系。 代理类和目标对象通常实现相同的接口或继承相同父类。 缺点是对于每个需要代理的目标对象…...

15个学习Python 的编程游戏网站

从小很多人都会在想,那些枯燥的教学课程要是全部变成游戏就好了,这样的话那期末成绩不得立即起飞了嘛?那对于编程很多人也有这样的想法,边玩边学就好了 这不已经有很多程序员开发了多款边玩边学的编程游戏供大家使用,…...

微信小程序实现拖拽盒子效果

要实现一个当前盒子高度由里面的盒子进行支配高度拖拽的效果 // wxml<view class"exmation-item" wx:elif"{{type4}}"> <view class"exmation-item-drag-box" id"drag-box"> <!-- 内容 --><view class"exm…...

Linux-蓝牙协议

SPP (Serial Port Profile): 串口协议&#xff08;SPP&#xff09;是一个蓝牙配置文件&#xff0c;允许设备通过蓝牙模拟传统的串行端口通信。它通常用于无线串口连接&#xff0c;允许设备如计算机和外设&#xff08;例如打印机或条形码扫描器&#xff09;之间进行数据传输。A…...

moviepy 将mp4视频文件提取音频mp3 - python 实现

DataBall 助力快速掌握数据集的信息和使用方式&#xff0c;会员享有 百种数据集&#xff0c;持续增加中。 需要更多数据资源和技术解决方案&#xff0c;知识星球&#xff1a; “DataBall - X 数据球(free)” -------------------------------------------------------------…...

imageio 图片转mp4 保存mp4

目录 安装&#xff1a; imageio 图片转mp4 numpy 保存mp4 安装&#xff1a; FFMPEG: pip install imageio[ffmpeg] pyav: pip install imageio[pyav] imageio 图片转mp4 import glob import osimport cv2 import imageio from natsort import natsortedfrom PIL import …...

Postman接口测试04|批量运行测试用例、参数化、Mock Server、Cookie鉴权、Newman生成测试报告

目录 十一、Postman批量运行测试用例 十二、实现数据驱动&#xff08;也称参数化&#xff09; 1、csv文件 1️⃣编辑csv文件 2️⃣更新参数的值 3️⃣修改测试脚本和断言 5️⃣批量运行测试用例 2、Json文件 1️⃣编辑Json文件 2️⃣其他操作和处理csv文件相同 十三、…...

学技术学英语:http状态码 401 Unauthorized vs 403 Forbidden

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#xff1a;先看关键单词&#xff0c;再看英文&#xff0c;最后看中文总结&#xff0c;再回头看一遍英文原文&#xff0c;效果更佳&#xff01;&#xff01; 关键词 unauthorized未授权的/ˌʌnˈɔːθəraɪzd/authentication认证/…...

@LocalBuilder装饰器: 维持组件父子关系

一、前言 当开发者使用Builder做引用数据传递时&#xff0c;会考虑组件的父子关系&#xff0c;使用了bind(this)之后&#xff0c;组件的父子关系和状态管理的父子关系并不一致。为了解决组件的父子关系和状态管理的父子关系保持一致的问题&#xff0c;引入LocalBuilder装饰器。…...

React(二)——Admin主页/Orders页面/Category页面

文章目录 项目地址一、侧边栏1.1 具体实现 二、Header2.1 实现 三、Orders页面3.1 分页和搜索3.2 点击箭头显示商家所有订单3.3 页码按钮以及分页 四、Category页面4.1 左侧商品添加栏目4.2 右侧商品上传栏 五、Sellers页面六、Payment Request 页面&#xff08;百万数据加载&a…...

移动端屏幕分辨率rem,less

谷歌模拟器&#xff1a;能直接看到移动端效果 屏幕分辨率 右键电脑桌面 &#xff0c;点击显示设置 PC端是逻辑分辨率&#xff0c;移动端代码也是参考逻辑分辨率 网页端宽度和逻辑分辨率尺寸相同 手机屏幕尺寸不同&#xff0c;网页宽度均为 100% 所以就需要添加视口标签&#x…...

Docker Desktop 构建java8基础镜像jdk安装配置失效解决

Docker Desktop 构建java8基础镜像jdk安装配置失效解决 文章目录 1.问题2.解决方法3.总结 1.问题 之前的好几篇文章中分享了在Linux(centOs上)和windows10上使用docker和docker Desktop环境构建java8的最小jre基础镜像&#xff0c;前几天我使用Docker Desktop环境重新构建了一个…...

数据结构:栈(Stack)和队列(Queue)—面试题(一)

目录 1、括号匹配 2、逆波兰表达式求值 3、栈的压入、弹出序列 4、最小栈 1、括号匹配 习题链接https://leetcode.cn/problems/valid-parentheses/description/ 描述&#xff1a; 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] …...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...