List集合源码分析

简介:   ArrayList底层数据结构是一个数组,查询元素速度快,增删速度稍慢  (1)DEFAULT_CAPACITY: 表示数组的初始大小,默认10  (2)size: 表示当前数组的大小

  ArrayList底层数据结构是一个数组,查询元素速度快,增删速度稍慢

  (1)DEFAULT_CAPACITY: 表示数组的初始大小,默认10

  (2)size: 表示当前数组的大小

  (3)modCount: 统计当前数组元素被修改的次数,只要修改,就+1

  public ArrayList() { //实际大小为{},长度为0的数组 this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

  说明: ArrayList无参构造方法初始化时,默认大小是空数组,并不是大家常说的10,

  10是在第一次add的时候扩容的数组容量值.

  ?

  public boolean add(E e) { //确保数组大小是否足够,不够执行扩容,size为当前数组的大小 ensureCapacityInternal(size + 1); // Increments modCount!! //直接把元素e保存到数组中 elementData[size++]=e; return true; }

  ?

  private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果是空数组{} if (elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //在最小容量minCapacity和DEFAULT_CAPACITY(10)选择一个较大的值 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity;}private void ensureExplicitCapacity(int minCapacity) { //记录修改次数 modCount++; //如果我们期望的最小容量>数组目前的长度就扩容 if (minCapacity - elementData.length > 0) grow(minCapacity);}private void grow(int minCapacity) { // overflow-conscious code int oldCapacity=elementData.length; //oldCapacity >> 1: 是把oldCapacity/2的意思 int newCapacity=oldCapacity + (oldCapacity >> 1); //如果扩容后的值<我们期望的值,扩容后的值等于我们期望的值 if (newCapacity - minCapacity < 0) newCapacity=minCapacity; //如果扩容后的值>jvm所能分配的数组的最大值,那么就用Integer的最大值 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity=hugeCapacity(minCapacity); //通过复制数组扩容 elementData=Arrays.copyOf(elementData, newCapacity);}

  注意:

  1.扩容的规则并不是翻倍,是原来容量大小的1.5倍

  2.ArrayList中数组的最大长度是Integer.MAX_VALUE,超过这个值,JVM就不会给数组分配内存空间了

  3.新增元素时,并没有对值进行严格的校验,所以ArrayList是允许null值的

  LinkedList底层数据结构是一个二手回收平台双向链表,链表中的每个节点都可以查找前一个节点或者向后查找后一个节点

  (1)链表每个节点叫做Node,Node有prev属性,代表前一个节点的地址,next属性代表后一个节点的地址

  (2)first是双向链表的头节点,它的前一个节点是null

  (3)last是双向链表的尾节点,它的后一个节点是null

  (4)链表中如果没有数据,first和last都null

  (5)因为是双向链表,只要内存空间足够大,链表的大小是没有限制的

  private static class Node { E item;//节点数据 Node next;//下一个节点的地址 Node prev;//前一个节点的地址 //初始化参数顺序是: 前一个节点地址,节点本身的数据,后一个节点地址 Node(Node prev, E element, Node next) { this.item=element; this.next=next; this.prev=prev; } }

  public boolean add(E e) { linkLast(e); return true;//链表节点数据可以重复,所以add方法始终返回true}

  //从尾部添加节点void linkLast(E e) { //把尾节点地址存储在l中 final Node l=last; //创建新的节点,参数含义如下 //l是新节点的前一个节点的地址,当前值是尾节点地址值 //e是当前新增节点中保存的数据,当前新增节点的下一个节点是null,因为是在末尾添加 final Node newNode=new Node<>(l, e, null); //last指向新增节点(新增节点作为尾节点) last=newNode; //如果链表为空(第一次添加节点)(l是尾节点,尾节点为空,链表即空),头部和尾部都是指向同一个节点,都是新建的节点 if (l==null) first=newNode; else //链表不是空(非第一次添加节点),把添加新节点之前的尾节点的下一个节点指向新添加的节点 l.next=newNode; //节点数+1 size++; //链表的实际修改次数+1 modCount++;}

  public E get(int index) { checkElementIndex(index);//检查索引值是否越界 return node(index).item; } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isElementIndex(int index) { return index >=0 && index < size; }

  ?核心根据索引获取节点数据的方法

  链表查询某个节点是比较慢的,需要挨个查找才可以

  根据链表索引位置查询元素Node node(int index) { //如果index处于链表的前半部分,从头开始查,size>>1 是 size/2的意思 if (index < (size >> 1)) { Node x=first; //知道for循环到index的前一个node停止 for (int i=0; i < index; i++) x=x.next; return x; } else { //如果index处于链表的后半部分,从尾开始查 Node x=last; //知道for循环到index的后一个node停止 for (int i=size - 1; i > index; i--) x=x.prev; return x; }}

  从源码中发现,LinkedList并没有采用从头循环到尾的做法,而是采取了简单二分查找法,

  首先看index是在链表的左半部分还是右半部分.如果是在左半部分,就从左侧开始找,

  如果实在链表的有伴部分,就从右侧开始找.这种方式,循环的次数至少降低了一半,提高查询性能.

目录
相关文章
|
Java 数据库连接 Maven
分布式——Maven多模块管理
Maven的多模块管理。所谓Maven的多模块管理其实:子模块继承父模块的Maven依赖,这样在多模块开发之下,多个模块的依赖版本就是一样的,这样就不会造成因模块依赖的版本不同而造成的冲突。其实Mavne管理的就是依赖的版本号。
分布式——Maven多模块管理
|
5月前
|
机器学习/深度学习 敏捷开发 供应链
从多维度解构 Lead Time:定义、应用与优化策略
当我们谈论lead time时,往往会发现这个词在不同领域的定义存在细微差异。这种现象并非偶然,而是源于其本质的抽象性与适用场景的多样性。为了深入理解这一概念,我们需要从底层逻辑出发,通过跨领域的对比分析和实际案例验证,逐步揭示其核心内涵。
1093 16
|
5月前
|
人工智能 自然语言处理 安全
学不会编程也能写测试?AI让测试更平权
在传统的软件开发体系中,测试常被划分为“技术型测试”(如自动化、性能、安全)和“业务型测试”(如功能验证、用户体验)。前者掌握技术话语权,后者则更多依赖经验和流程规范。然而,随着大语言模型(LLM)等AI技术的迅猛发展,这一固有格局正被悄然打破:
162 10
|
5月前
|
Kubernetes Linux Go
使用 Uber automaxprocs 正确设置 Go 程序线程数
`automaxprocs` 包就是专门用来解决此问题的,并且用法非常简单,只需要使用匿名导入的方式 `import _ "go.uber.org/automaxprocs"` 一行代码即可搞定。
247 78
|
5月前
|
存储 前端开发 JavaScript
|
5月前
|
JSON 监控 Java
日志与追踪的完美融合:OpenTelemetry MDC 实践指南
日志与追踪的完美融合:OpenTelemetry MDC 实践指南
314 24
|
5月前
|
JavaScript 前端开发 编译器
Vue与TypeScript:如何实现更强大的前端开发
Vue.js 以其简洁的语法和灵活的架构在前端开发中广受欢迎,而 TypeScript 作为一种静态类型语言,为 JavaScript 提供了强大的类型系统和编译时检查。将 Vue.js 与 TypeScript 结合使用,不仅可以提升代码的可维护性和可扩展性,还能减少运行时错误,提高开发效率。本文将介绍如何在 Vue.js 项目中使用 TypeScript,并通过一些代码示例展示其强大功能。
217 22
|
5月前
|
JSON 机器人 API
gewe微信机器人搭建教程
GeWe开放平台是基于 微信开放平台的二次封装API服务,开发者可以使用本服务来处理微信中的各种事件,并可以通过后台调用对应的 API 来驱动微信自动执行任务,如自动收发消息、自动化应答、自动群邀请、群管理等,封装了 RPA技术流程,简化开发者二次开发难度,提供了开发者与微信对接的能力,使用简单,操作快捷,支持多种语言接入。
205 17
|
5月前
|
数据采集 安全 BI
用Python编程基础提升工作效率
一、文件处理整明白了,少加两小时班 (敲暖气管子)领导让整理100个Excel表?手都干抽筋儿了?Python就跟铲雪车似的,哗哗给你整利索!
126 11
|
11月前
|
定位技术
域名前缀和后缀html,为什么域名前要加www前缀,www是什么意思?
为什么域名前要加www前缀?Michael F Liu号召大家把域名前面的www去掉,我深以为然。好域名都被瓜分光了,大家手里的域名都老长老长的,处理网域名[https://www.91chuli.com/](https://www.91chuli.com/)就有5个字母,前面再加上“www.”,多让直接访问者敲打5次键盘,何苦来呢?
13826 6