LinkedList 分析
LinkedList 简介
LinkedList 是一个基于双向链表实现的集合类,经常被拿来和 ArrayList 做比较。关于 LinkedList 和ArrayList的详细对比,我们 Java 集合常见面试题总结(上)有详细介绍到。

双向链表
不过,我们在项目中一般是不会使用到 LinkedList 的,需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替,并且,性能通常会更好!就连 LinkedList 的作者约书亚 · 布洛克(Josh Bloch)自己都说从来不会使用 LinkedList 。
另外,不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了,LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1),其他情况增删元素的平均时间复杂度都是 O(n) 。
LinkedList 插入和删除元素的时间复杂度?
- 头部插入/删除:只需要修改头结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。
- 尾部插入/删除:只需要修改尾结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。
- 指定位置插入/删除:需要先移动到指定位置,再修改指定节点的指针完成插入/删除,不过由于有头尾指针,可以从较近的指针出发,因此需要遍历平均 n/4 个元素,时间复杂度为 O(n)。
LinkedList 为什么不能实现 RandomAccess 接口?
RandomAccess 是一个标记接口,用来表明实现该接口的类支持随机访问(即可以通过索引快速访问元素)。由于 LinkedList 底层数据结构是链表,内存地址不连续,只能通过指针来定位,不支持随机快速访问,所以不能实现 RandomAccess 接口。
LinkedList 源码分析
这里以 JDK1.8 为例,分析一下 LinkedList 的底层核心源码。
LinkedList 的类定义如下:
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{//...
}
LinkedList 继承了 AbstractSequentialList ,而 AbstractSequentialList 又继承于 AbstractList 。
阅读过 ArrayList 的源码我们就知道,ArrayList 同样继承了 AbstractList , 所以 LinkedList 会有大部分方法和 ArrayList 相似。
LinkedList 实现了以下接口:
List: 表明它是一个列表,支持添加、删除、查找等操作,并且可以通过下标进行访问。Deque:继承自Queue接口,具有双端队列的特性,支持从两端插入和删除元素,方便实现栈和队列等数据结构。需要注意,Deque的发音为 "deck" [dɛk],这个大部分人都会读错。Cloneable:表明它具有拷贝能力,可以进行深拷贝或浅拷贝操作。Serializable: 表明它可以进行序列化操作,也就是可以将对象转换为字节流进行持久化存储或网络传输,非常方便。-
LinkedList 类图
LinkedList中的元素是通过Node定义的:
private static class Node<E> {E item;// 节点值Node<E> next; // 指向的下一个节点(后继节点)Node<E> prev; // 指向的前一个节点(前驱结点)// 初始化参数顺序分别是:前驱结点、本身节点值、后继节点Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;} }初始化
LinkedList中有一个无参构造函数和一个有参构造函数。// 创建一个空的链表对象 public LinkedList() { }// 接收一个集合类型作为参数,会创建一个与传入集合相同元素的链表对象 public LinkedList(Collection<? extends E> c) {this();addAll(c); }插入元素
LinkedList除了实现了List接口相关方法,还实现了Deque接口的很多方法,所以我们有很多种方式插入元素。我们这里以
List接口中相关的插入方法为例进行源码讲解,对应的是add()方法。add()方法有两个版本: add(E e):用于在LinkedList的尾部插入元素,即将新元素作为链表的最后一个元素,时间复杂度为 O(1)。add(int index, E element):用于在指定位置插入元素。这种插入方式需要先移动到指定位置,再修改指定节点的指针完成插入/删除,因此需要移动平均 n/2 个元素,时间复杂度为 O(n)。-
// 在链表尾部插入元素
public boolean add(E e) {
linkLast(e);
return true;
}// 在链表指定位置插入元素
public void add(int index, E element) {
// 下标越界检查
checkPositionIndex(index);// 判断 index 是不是链表尾部位置
if (index == size)
// 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可
linkLast(element);
else
// 如果不是则调用 linkBefore 方法将其插入指定元素之前
linkBefore(element, node(index));
}// 将元素节点插入到链表尾部
void linkLast(E e) {
// 将最后一个元素赋值(引用传递)给节点 l
final Node<E> l = last;
// 创建节点,并指定节点前驱为链表尾节点 last,后继引用为空
final Node<E> newNode = new Node<>(l, e, null);
// 将 last 引用指向新节点
last = newNode;
// 判断尾节点是否为空
// 如果 l 是null 意味着这是第一次添加元素
if (l == null)
// 如果是第一次添加,将first赋值为新节点,此时链表只有一个元素
first = newNode;
else
// 如果不是第一次添加,将新节点赋值给l(添加前的最后一个元素)的next
l.next = newNode;
size++;
modCount++;
}// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
// assert succ != null;断言 succ不为 null
// 定义一个节点元素保存 succ 的 prev 引用,也就是它的前一节点信息
final Node<E> pred = succ.prev;
// 初始化节点,并指明前驱和后继节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 将 succ 节点前驱引用 prev 指向新节点
succ.prev = newNode;
// 判断前驱节点是否为空,为空表示 succ 是第一个节点
if (pred == null)
// 新节点成为第一个节点
first = newNode;
else
// succ 节点前驱的后继引用指向新节点
pred.next = newNode;
size++;
modCount++;
}
相关文章:
LinkedList 分析
LinkedList 简介 LinkedList 是一个基于双向链表实现的集合类,经常被拿来和 ArrayList 做比较。关于 LinkedList 和ArrayList的详细对比,我们 Java 集合常见面试题总结(上)有详细介绍到。 双向链表 不过,我们在项目中一般是不会使用到 Link…...
【C/C++】模拟实现strlen
学习目标: 使用代码模拟实现strlen。 逻辑: strlen 需要输入一个字符串数组类型的变量,并且返回一个整型类型的数据。strlen 需要计算字符串数组有多少个元素。 代码1:使用计数器 #define _CRT_SECURE_NO_WARNINGS 1 #include&…...
mybatis从浅入深一步步演变分析
mybatis从浅入深一步步演变分析 版本一:不使用代理(非spring) package com.yimeng.domain;public class User {private int id;private String username;private String password;public int getId() {return id;}public void setId(int id…...
Java阶段三02
第3章-第2节 一、知识点 面向接口编程、什么是spring、什么是IOC、IOC的使用、依赖注入 二、目标 了解什么是spring 理解IOC的思想和使用 了解IOC的bean的生命周期 理解什么是依赖注入 三、内容分析 重点 了解什么是spring 理解IOC的思想 掌握IOC的使用 难点 理解IO…...
【Linux】掌握库的艺术:我的动静态库封装之旅
🌈个人主页:Yui_ 🌈Linux专栏:Linux 🌈C语言笔记专栏:C语言笔记 🌈数据结构专栏:数据结构 🌈C专栏:C 文章目录 1.什么是库1.2 认识动静态库1.2.1 动态库1.2.2…...
UE5动画控制 基础
素材 mixamo先去选择一个character 点击下载 就这个下载下来 然后选几个animation, 记得勾选 把动作下载了 without skin就是只要动作 然后把他们放在一个文件夹里先 UE里导入 找一个文件夹,直接拖拽进来那个character的fbx,默认配置就…...
流畅!HTMLCSS打造网格方块加载动画
效果演示 这个动画的效果是五个方块在网格中上下移动,模拟了一个连续的加载过程。每个方块的动画都是独立的,但是它们的时间间隔和路径被设计为相互协调,以创建出流畅的动画效果。 HTML <div class"loadingspinner"><…...
linux命令之top(Linux Command Top)
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 本人主要分享计算机核心技…...
数据结构-希尔排序(ShellSort)笔记
看动画理解 【数据结构】八大排序(超详解附动图源码)_数据结构排序-CSDN博客 一 基本思想 先选定一个整数gap,把待排序文件中所有记录分成gap个组,所有距离为gap的记录分在同一组内,并对每一组内的元素进行排序。 然后将gap逐渐减小重复上…...
Junit + Mockito保姆级集成测试实践
一、做好单测,慢即是快 对于单元测试的看法,业界同仁理解多有不同,尤其是在业务变化快速的互联网行业,通常的问题主要有,必须要做吗?做到多少合适?现在没做不也挺好的吗?甚至一些大…...
软件项目管理要点
一.项目管理 1.盈亏平衡分析 销售额固定成本可变成本税费利润 当利润为0的时候就是盈亏平衡点。 2.范围管理 范围定义的输入包括:项目章程、项目范围管理计划、组织过程资产、批准的变更申请。 3.时间管理 项目时间管理中的过程包括活动定义、活动排序、活动的资…...
ESP8266 连接 MQTT 服务器EMQX 连接MQTTX
目录 1.先用有一台自己的云服务器 2. 使用FinalShell连接阿里云云服务器ECS 3.安装宝塔 4.在云服务器打开8888端口 5.使用外网面板地址打开宝塔面板 6.安装Docker 7.下载emqx 8.打开emqxWeb 界面 9.下载MQTTX 10.EMQX加一个客户端 11.开始通信 12.加入单片机ESP8266 …...
Python中如何处理异常情况?
1、Python中如何处理异常情况? 在Python中,处理异常情况通常使用try/except语句。try语句块包含可能会引发异常的代码,而except语句块包含处理异常的代码。如果try块中的代码引发了异常,控制流将立即转到相应的except块。 以下是…...
openpnp - 在openpnp中单独测试相机
文章目录 openpnp - 在openpnp中单独测试相机概述笔记END openpnp - 在openpnp中单独测试相机 概述 底部相机的位置不合适, 重新做了零件,准备先确定一下相机和吸嘴的距离是多少才合适。 如果在设备上直接实验,那么拆装调整相机挺麻烦的。 准备直接在电…...
Spark窗口函数
1、 Spark中的窗口函数 窗口就是单纯在行后面加一个列 可以套多个窗口函数,但彼此之间不能相互引用,是独立的 窗口函数会产生shuffle over就是用来划分窗口的 (1) 分组聚合里面的函数,基…...
Idea、VS Code 如何安装Fitten Code插件使用
博主主页:【南鸢1.0】 本文专栏:JAVA 目录 编辑 简介 所用工具 1、Idea如何安装插件 1.idea下载插件 2.需要从外部下载然后在安装, 2、VS Code如何安装插件 总结 简介 Fitten Code是由非十大模型驱动的AI编程助手,它可以自动生成代…...
elasticsearch7.x在k8s中的部署
一、说明 二、思路 三、部署 1、建nfs服务器 2、建持久卷 3、部署elasticsearch 四、附件 ?pv.yaml内容 elasticsearch.yaml内容 一、说明 本文章内容主要的参考来源是https://www.cnblogs.com/javashop-docs/p/12410845.html,但参考文献中的elasticsearc…...
校园社团信息管理平台:Spring Boot技术实战指南
3系统分析 3.1可行性分析 通过对本校园社团信息管理系统实行的目的初步调查和分析,提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本校园社团信息管理系统采用SSM框架,JAVA作…...
【Linux】从内核角度理解 TCP 的 全连接队列(以及什么是 TCP 抓包)
文章目录 概念引入理解全连接队列内核方面理解Tcp抓包方法注意事项 概念引入 我们知道,TCP的三次握手是由TCP协议 自动处理的,建立连接的过程与用户是否进行accept无关,accept()的作用主要是为当前连接创建一个套接字,用于进行后…...
太速科技-712-6U VPX飞腾处理器刀片计算机
6U VPX飞腾处理器刀片计算机 一、产品概述 该产品是一款基于国产飞腾FT-2000四核处理器或D2000八核处理器的高性能6U VPX刀片式计算机。产品提供了可支持全网状交换的高速数据通道,其中P1、P2均支持1个PCIe x16 Gen3或2个PCIe x8 Gen3或4个PCIe x4 Gen3总…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: 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 解决方案&…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
C++_哈希表
本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说,直接开始吧! 一、基础概念 1. 哈希核心思想: 哈希函数的作用:通过此函数建立一个Key与存储位置之间的映射关系。理想目标:实现…...
