面试宝典:数据结构-ArrayList(下)

简介: 面试宝典:数据结构-ArrayList(下)

image.png


当 要 add 进第1个元素时,minCapacity为(size+1=0+1=)1


在Math.max()方法比较后,minCapacity 为10


然后紧接着调用ensureExplicitCapacity更新modCount的值


并判断是否需要扩容


image.png


oldCapacity为旧数组的容量


newCapacity为新数组的容量(oldCap+oldCap/2:即更新为旧容量的1.5倍)


检查新容量的大小是否小于最小需要容量,如果小于那就将最小容量置为数组的新容量


如果新容量大于MAX_ARRAY_SIZE,使用hugeCapacity比较二者


hugeCapacity逻辑:


对minCapacity和MAX_ARRAY_SIZE进行比较


若minCapacity大,将Integer.MAX_VALUE作为新数组的大小


若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小


MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8


add方法执行流程总结


image.png


  • 这是第一次调用add方法的过程,当扩容值capacity为10之后,


  • 继续添加第2个元素(先注意调用ensureCapacityInternal方法传递的参数为size+1=1+1=2)



  • 在ensureCapacityInternal方法中,elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA不成立,所以直接执行ensureExplicitCapacity方法


  • ensureExplicitCapacity方法中minCapacity为刚刚传递的2,所以第二个if判断(2-10=-8)不会成立,即newCapacity 不比 MAX_ARRAY_SIZE大,则不会进入 grow 方法。数组容量为10,add方法中 return true,size增为1。


  • 假设又添加3、4......10个元素(其中过程类似,但是不会执行grow扩容方法)


  • 当add第11个元素时候,会进入grow方法时,计算newCapacity为15,比minCapacity(为10+1=11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中return true,size增为11


add(int index,E element)方法


image.png


add(int index, E element)方法(在元素序列指定位置(假设该位置合理)插入)的过程大概是下面这些


  • 检测数组是否有足够的空间(这里的实现和上面的)
  • 将 index 及其之后的所有元素向后移一位
  • 将新元素插入至 index 处.
  • 将新元素插入至序列指定位置,需要先将该位置及其之后的元素都向后移动一位,为新元素腾出位置。这个操作的时间复杂度为O(N),频繁移动元素可能会导致效率问题,特别是集合中元素数量较多时
  • 在日常开发中,若非所需,我们应当尽量避免在大集合中调用第二个插入方法


ArrayList的remove方法


remove(int index) 按照下标删除


image.png


image.png


image.png


nteger.MAX_VALUE - 8


主要是考虑到不同的JVM,有的JVM会在加入一些数据头,当扩容后的容量大于MAX_ARRAY_SIZE,我们会去比较最小需要容量和MAX_ARRAY_SIZE做比较,如果比它大, 只能取Integer.MAX_VALUE,否则是Integer.MAX_VALUE -8。这个是从jdk1.7开始才有的


参考资料


https://www.cnblogs.com/lcj12121/p/11710065.html


相关文章
|
3月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
3月前
|
存储 Java 索引
【Java集合类面试二十四】、ArrayList和LinkedList有什么区别?
ArrayList基于动态数组实现,支持快速随机访问;LinkedList基于双向链表实现,插入和删除操作更高效,但占用更多内存。
|
22天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
1月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
33 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
1月前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
23 3
|
1月前
|
存储 缓存 索引
从底层数据结构和CPU缓存两方面剖析LinkedList的查询效率为什么比ArrayList低
本文详细对比了ArrayList和LinkedList的查询效率,从底层数据结构和CPU缓存两个方面进行分析。ArrayList基于动态数组,支持随机访问,查询时间复杂度为O(1),且CPU缓存对其友好;而LinkedList基于双向链表,需要逐个节点遍历,查询时间复杂度为O(n),且CPU缓存对其帮助不大。文章还探讨了CPU缓存对数组增删操作的影响,指出缓存主要作用于读取而非修改。通过这些分析,加深了对这两种数据结构的理解。
40 2
|
1月前
|
设计模式 安全 容器
数据结构第一篇【探究List和ArrayList之间的奥秘 】
数据结构第一篇【探究List和ArrayList之间的奥秘 】
24 5
|
26天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
2月前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表(Arraylist)
Java集合框架主要由接口、实现类及迭代器组成,包括Collection和Map两大类。Collection涵盖List(有序、可重复)、Set(无序、不可重复),Map则由键值对构成。集合通过接口定义基本操作,具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复,Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现,各有适用场景。其中ArrayList实现了动态数组功能,可根据需求自动调整大小。
40 11
|
1月前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
23 0