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开发过程中,可能经常会使用到List作为集合来使用,List是一个接口承于Collection的接口,表示着有序的列表。而我们要讨论的是它下面的实现类Arraylist/LinkedList/Vector的数据结构及区别。 ArrayList ArrayList:底层为数组…...

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

三维重建小有基础入门之特征点检测基础
前言:本文将从此篇开始,记录自己从普通CVer入门三维重建的学习过程,可能过程比较坎坷,都在摸索阶段,但争取每次学习都能进一步,提高自己的能力,同时,每篇文章都会按情况相应地推出B站…...

基于node.js+vue+mysql考研辅导学习打卡交流网站系统vscode
语言 node.js 框架:Express 前端:Vue.js 数据库:mysql 数据库工具:Navicat 开发软件:VScode 主要功能包括管理员:首页、个人中心、用户管理、每日打卡管理、考研学校管理、考研专业管理、直通车管理、学习教材管理、…...

【C++、数据结构】封装unordered_map和unordered_set(用哈希桶实现)
文章目录📖 前言1. 复用同一个哈希桶⚡1.1 🌀修改后结点的定义1.2 🌀两个容器各自模板参数类型:2. 改造之后的哈希桶⛳3. 哈希桶的迭代器🔥3.1 💥哈希桶的begin()和 end(…...
StratoVirt 的 vCPU 拓扑(SMP)
CPU 拓扑用来表示 CPU 在硬件层面的组合方式,本文主要讲解 CPU 拓扑中的 SMP(Symmetric Multi-Processor,对称多处理器系统)架构,CPU 拓扑还包括其他信息,比如:cache 等,这些部分会在…...
现在直播大部分都是RTMP RTMP VS RTC
一 RTMP 抓了下抖音直播的包,windows端,走的TCP,加密了,估计还是RTMP。 我以为直播带货,都是RTC了。 快手直播也是TCP,地址用了IPV6。 淘宝直播也是。现在大部分直播都是RTMP。 只有视频会议走的RTC。…...
【Unity实战100例】Unity循环UI界面切换卡片功能
目录 编辑 一:制作UI界面 二:代码逻辑 1.定义基础变量...

Monorepo or 物料市场?结合工作实际情况对公司现有前端体系的思考
前言 去年年中基于若依vue前端框架进行了改造,加上后端的配合,我写了一套脚手架和项目中后台模板。中后台模板中包含了许多基础代码,比如登录/注册、路由、权限等等相关功能。这个中后台模板是基于我们实际开发定制的,所以跟通用…...

GEE学习笔记八十八:在自己的APP中使用绘制矢量(上)
在GEE中尤其是自己的APP中调用绘制的矢量图形方法之前没有合适的方法,但是现在可以通过ui.Map.DrawingTools(...)以及ui.Map.GeometryLayer(...)结合来做。具体的API如下图: 在这一篇中我先通过一个简单的例子来展示一下使用这些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} #创建一个字典,key为州名,value为州缩写#Create a basic set of states and some cit…...
模糊的照片如何修复清晰?
相信有很多人用手机拍照时,觉得拍出来的照片一定是很漂亮的,结果拍了之后,拿出来一看模糊一片,根本看不清是什么。或者是只显示一半另一半模糊一片。而这些精彩瞬间很多时候是无法重拍的。虽然谁也不想拍出的照片出现模糊…...

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

【MyBatis】| MyBatis分页插件PageHelper
目录 一:MyBatis使⽤PageHelper 1. limit分⻚ 2. PageHelper插件 一:MyBatis使⽤PageHelper 1. limit分⻚ (1)概念: ①页码:pageNum(用户会发送请求,携带页码pageNum给服务器&am…...
Java枚举类详解
一、定义格式 public enum s { 枚举项1,枚举项2,枚举项3; } // 定义一个枚举类,用来表示春,夏,秋,冬这四个固定值 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 环境搭建、插件的安装)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 第 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进阶(一)——剪枝优化一、什么是剪枝?二、剪枝优化的策略1、优化搜索顺序2、排除等效冗余3、可行性剪枝4、最优性剪枝5、记忆化搜索三、例题1、AcWing 165. 小猫爬山(DFS 剪枝优化)2、AcWing 167. 木棒…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...
使用 uv 工具快速部署并管理 vLLM 推理环境
uv:现代 Python 项目管理的高效助手 uv:Rust 驱动的 Python 包管理新时代 在部署大语言模型(LLM)推理服务时,vLLM 是一个备受关注的方案,具备高吞吐、低延迟和对 OpenAI API 的良好兼容性。为了提高部署效…...
软件工程教学评价
王海林老师您好。 您的《软件工程》课程成功地将宏观的理论与具体的实践相结合。上半学期的理论教学中,您通过丰富的实例,将“高内聚低耦合”、SOLID原则等抽象概念解释得十分透彻,让这些理论不再是停留在纸面的名词,而是可以指导…...