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

JAVA集合之List >> Arraylist/LinkedList/Vector结构

在Java开发过程中,可能经常会使用到List作为集合来使用,List是一个接口承于Collection的接口,表示着有序的列表。而我们要讨论的是它下面的实现类Arraylist/LinkedList/Vector的数据结构及区别。

ArrayList

ArrayList:底层为数组结构,而数组的查询速度都是O(1)很快的,增删稍慢(新增对象,如果超过数组设置的大小,需要扩容。删除对象,则需要对数组重排序)。

参考源码:

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{/*** Default initial capacity.*/private static final int DEFAULT_CAPACITY = 10;/*** Shared empty array instance used for empty instances.*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** Shared empty array instance used for default sized empty instances. */private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData; ......此处省略其他参数代码/*** 构造具有指定初始容量的空列表.** @param  initialCapacity  the initial capacity of the list* @throws IllegalArgumentException if the specified initial capacity*         is negative*/public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}.....省略其他代码
}

以上源码只贴了Arraylist构造函数,证明它是一个数组结构。对于add的扩容,及remove的重排序由于代码比较多就没有贴,大家可以直接去看源码(add 扩容方法:grow(int minCapacity)、remove重排序:System.arraycopy)

LinkedList

LinkedList:底层为链表结构,增删查等操作,如果是指定位置,则速度稍慢(需要遍历链表,直到指定位置),如果不是指定位置则速度快(默认操作链头、链尾)。

对于指定位置的操作,都会调用源码中node(int index)方法,该方法就是遍历链表,直到指定位置返回元素

无参add 源码参考:

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{transient int size = 0;transient Node<E> first;transient Node<E> last;......省略N多代码public boolean add(E e) {linkLast(e);return true;}/*** Links e as last element. 默认从尾部新增元素*/void linkLast(E e) {//获取尾部元素final Node<E> l = last;//将尾部元素作为上一个元素,并创建一个新的当前元素final Node<E> newNode = new Node<>(l, e, null);//将新元素更新为最后一个元素last = newNode;if (l == null)    // 如果为空,则将新元素赋值到第一个元素(first)first = newNode;else              //否则将新增前的最后一个元素的next存放新元素l.next = newNode;size++;modCount++;}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对于无参数新增,只需要往Last元素的Next放入新增的元素,然后更新全局Last位置即可,所以没有速度的影响。对于addFirst、addLast等代码没贴,可自行了解,都差不多。

有参add 源码参考:

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{    public void add(int index, E element) {checkPositionIndex(index);    // 检查位置是否存在if (index == size)            // 如果指定位置是最后一个,则从尾部插入linkLast(element);else// node(index) 会遍历链表到指定位置,返回指定位置的元素// linkBeforelinkBefore(element, node(index));}// 检查位置是否存在private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}/*** Links e as last element. 默认从尾部新增元素*/void linkLast(E e) {//获取尾部元素final Node<E> l = last;//将尾部元素作为上一个元素,并创建一个新的当前元素final Node<E> newNode = new Node<>(l, e, null);//将新元素更新为最后一个元素last = newNode;if (l == null)    // 如果为空,则将新元素赋值到第一个元素(first)first = newNode;else              //否则将新增前的最后一个元素的next存放新元素l.next = newNode;size++;modCount++;}/*** 返回指定位置的元素*/Node<E> node(int index) {//如果小于链表的大小,则从第一个元素开始循环获取到指定位置的元素 if (index < (size >> 1)) {Node<E> x = first;                 //链表的第一个元素开始for (int i = 0; i < index; i++)    //循环链表,直到指定位置x = x.next;                   return x;                         } else {                               //否则获取最后一个元素返回Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}/*** 在指定位置的元素前插入新元素*/void linkBefore(E e, Node<E> succ) {// 指定位置的前一个元素final Node<E> pred = succ.prev; // 创建新元素   final Node<E> newNode = new Node<>(pred, e, succ);// 将新元素作为指定位置元素的前一个元素succ.prev = newNode;// 指定位置的前一个元素如果为空,则将新元素放入到first if (pred == null)first = newNode;else// 指定位置前一个元素的next 放入新元素pred.next = newNode;size++;modCount++;}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对于指定位置新增,需要调用node(int index)方法,用于遍历获取指定位置的元素。对于性能来说是有影响的。

remove、get方法也一样,只要是指定位置的操作,都会调用node(int index)方法对链表进行遍历获取

Vector

Vector:底层为数组结构,与ArrayList差不多,但是线程同步的,因为效率低,基本被ArrayList替代了

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}public synchronized E remove(int index) {modCount++;if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);E oldValue = elementData(index);int numMoved = elementCount - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--elementCount] = null; // Let gc do its workreturn oldValue;}public synchronized E get(int index) {if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);return elementData(index);}}

源码上可以看到add、get、remove等都加上了synchronized所以只能单线程执行。

相关文章:

JAVA集合之List >> Arraylist/LinkedList/Vector结构

在Java开发过程中&#xff0c;可能经常会使用到List作为集合来使用&#xff0c;List是一个接口承于Collection的接口&#xff0c;表示着有序的列表。而我们要讨论的是它下面的实现类Arraylist/LinkedList/Vector的数据结构及区别。 ArrayList ArrayList&#xff1a;底层为数组…...

Linux多进程开发

一、进程概述 1、程序和进程 程序是包含一系列信息的文件&#xff0c;这些信息描述了如何在运行时创建一个进程&#xff1a; 二进制格式标识&#xff1a;每个程序文件都包含用于描述可执行文件格式的元信息。内核利用此信息来解释文件中的其他信息。&#xff08;ELF可执行连…...

三维重建小有基础入门之特征点检测基础

前言&#xff1a;本文将从此篇开始&#xff0c;记录自己从普通CVer入门三维重建的学习过程&#xff0c;可能过程比较坎坷&#xff0c;都在摸索阶段&#xff0c;但争取每次学习都能进一步&#xff0c;提高自己的能力&#xff0c;同时&#xff0c;每篇文章都会按情况相应地推出B站…...

基于node.js+vue+mysql考研辅导学习打卡交流网站系统vscode

语言 node.js 框架&#xff1a;Express 前端:Vue.js 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发软件&#xff1a;VScode 主要功能包括管理员&#xff1a;首页、个人中心、用户管理、每日打卡管理、考研学校管理、考研专业管理、直通车管理、学习教材管理、…...

【C++、数据结构】封装unordered_map和unordered_set(用哈希桶实现)

文章目录&#x1f4d6; 前言1. 复用同一个哈希桶⚡1.1 &#x1f300;修改后结点的定义1.2 &#x1f300;两个容器各自模板参数类型&#xff1a;2. 改造之后的哈希桶⛳3. 哈希桶的迭代器&#x1f525;3.1 &#x1f4a5;哈希桶的begin&#xff08;&#xff09;和 end&#xff08;…...

StratoVirt 的 vCPU 拓扑(SMP)

CPU 拓扑用来表示 CPU 在硬件层面的组合方式&#xff0c;本文主要讲解 CPU 拓扑中的 SMP&#xff08;Symmetric Multi-Processor&#xff0c;对称多处理器系统&#xff09;架构&#xff0c;CPU 拓扑还包括其他信息&#xff0c;比如&#xff1a;cache 等&#xff0c;这些部分会在…...

现在直播大部分都是RTMP RTMP VS RTC

一 RTMP 抓了下抖音直播的包&#xff0c;windows端&#xff0c;走的TCP&#xff0c;加密了&#xff0c;估计还是RTMP。 我以为直播带货&#xff0c;都是RTC了。 快手直播也是TCP&#xff0c;地址用了IPV6。 淘宝直播也是。现在大部分直播都是RTMP。 只有视频会议走的RTC。…...

【Unity实战100例】Unity循环UI界面切换卡片功能

目录 ​编辑 一:制作UI界面 二:代码逻辑 1.定义基础变量...

Monorepo or 物料市场?结合工作实际情况对公司现有前端体系的思考

前言 去年年中基于若依vue前端框架进行了改造&#xff0c;加上后端的配合&#xff0c;我写了一套脚手架和项目中后台模板。中后台模板中包含了许多基础代码&#xff0c;比如登录/注册、路由、权限等等相关功能。这个中后台模板是基于我们实际开发定制的&#xff0c;所以跟通用…...

GEE学习笔记八十八:在自己的APP中使用绘制矢量(上)

在GEE中尤其是自己的APP中调用绘制的矢量图形方法之前没有合适的方法&#xff0c;但是现在可以通过ui.Map.DrawingTools(...)以及ui.Map.GeometryLayer(...)结合来做。具体的API如下图&#xff1a; 在这一篇中我先通过一个简单的例子来展示一下使用这些API后可以实现什么效果&a…...

“笨办法”学Python 3 ——练习 39. 字典,可爱的字典

练习39 源代码 # create a mapping of state to abbreviation #创建一个州与缩写的映射 states {Oregon:OR,Florida:FL,California: CA, New York: NY,Michigan:MI} #创建一个字典&#xff0c;key为州名&#xff0c;value为州缩写#Create a basic set of states and some cit…...

模糊的照片如何修复清晰?

相信有很多人用手机拍照时&#xff0c;觉得拍出来的照片一定是很漂亮的&#xff0c;结果拍了之后&#xff0c;拿出来一看模糊一片&#xff0c;根本看不清是什么。或者是只显示一半另一半模糊一片。而这些精彩瞬间很多时候是无法重拍的。虽然谁也不想拍出的照片出现模糊&#xf…...

如何理解​session、cookie、token的区别与联系?

session、cookie、token。 相信学过接口的朋友都特别熟悉了。 但是对我一个刚接触接口测试的小白来说&#xff0c;属实有点分不清楚。 下文就是我通过查阅各种资料总结出来的一点理解&#xff0c;不准确的地方还请各位指正。 &#xff08;文末送洗浴中心流程指南&#xff09…...

【MyBatis】| MyBatis分页插件PageHelper

目录 一&#xff1a;MyBatis使⽤PageHelper 1. limit分⻚ 2. PageHelper插件 一&#xff1a;MyBatis使⽤PageHelper 1. limit分⻚ &#xff08;1&#xff09;概念&#xff1a; ①页码&#xff1a;pageNum&#xff08;用户会发送请求&#xff0c;携带页码pageNum给服务器&am…...

Java枚举类详解

一、定义格式 public enum s { 枚举项1,枚举项2,枚举项3; } // 定义一个枚举类&#xff0c;用来表示春&#xff0c;夏&#xff0c;秋&#xff0c;冬这四个固定值 public enum Season {SPRING,SUMMER,AUTUMN,WINTER; } 二、枚举的特点 1、所有枚举类都是Enum的子类 2、我们可以通…...

C语言数组

一.数组定义 数组由数据类型相同的一系列元素组成 如 int main(){ float candy[365]; char code[12]; int states[50]; … } cnady是包含了365个float元素的数组。code是包含了12个char类型的数组。states包含了50个int类型的数组。 二.数组初始化和取值 我们使用花括号包含值&…...

Scala 入门(第一章Scala 环境搭建、插件的安装)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 第 1 章 Scala 入门1.1 概述1.1.1 为什么学习 Scala1.1.2 Scala 发展历史1.1.3 Scala 和 Java 关系1.1.4 Scala 语言特点1.2 Scala 环境搭建1.3 Scala 插件安装1.4 HelloWorl…...

math@多项式@求和式乘法@代数学基本定理

文章目录多项式求和式乘法应用代数学基本定理相关证明高次方程其他关于多项式的参考多项式求和式乘法 S∏j1(∑k1ajk)⁣ ⁣ ⁣j∏j1m(∑k1njajk)⁣ ⁣ ⁣jS\prod_{j1}\left(\sum\limits_{k1}a_{jk}\right)_{\!\!\!j} \\\prod_{j1}^{m}\left(\sum\limits_{k1}^{n_j}a_{jk}\r…...

Kafka系列之:基于SCRAM和Ranger机制完成动态新增kafka读写账号、赋予账号对指定Topic的读写权限

Kafka系列之:基于SCRAM和Ranger机制完成动态新增kafka读写账号、赋予账号对指定Topic的读写权限 一、需求背景二、添加写用户三、查看用户是否添加到zookeeper中四、查看用户五、赋予用户topic写权限六、生产者配置文件七、ranger给用户权限八、往Topic写数据九、删除添加的用…...

第五十三章 DFS进阶(一)——剪枝优化

第五十四章 DFS进阶&#xff08;一&#xff09;——剪枝优化一、什么是剪枝&#xff1f;二、剪枝优化的策略1、优化搜索顺序2、排除等效冗余3、可行性剪枝4、最优性剪枝5、记忆化搜索三、例题1、AcWing 165. 小猫爬山&#xff08;DFS 剪枝优化&#xff09;2、AcWing 167. 木棒…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...