【Java】ArrayList 底层是如何实现的？

底层是如何实现的？"/>

【Java】ArrayList 底层是如何实现的？

• ArrayList 底层基于数组实现，查询效率是非常高，增删效率非常低——错误
• ArrayList 底层基于数组实现，根据index下标查询效率非常高——正确（误区——不是查询效率比较高）
• 增——底层基于数组实现 扩容——效率低

ArrayList底层是基于数组实现的

根据index下标查询效率非常高，时间复杂度为O(1)

如果根据元素值查询 效率非常低 时间复杂度O(n) 

---

ArrayList 新增 如果底层数组容量不够的情况下

就会触发动态扩容机制 效率非常低的

---

ArrayList 删除操作，将删除后面的元素向前移动一位

效率也是非常低。

package com.collection.Demo07;import java.util.ArrayList;public class Test01 {public static void main(String[] args) {/*** ArrayList 底层基于数组实现的* ArrayList 根据index 下标查询效率非常高，而不是查询效率非常高*/ArrayList<String> arrayList = new ArrayList<>();
//        arrayList.get(0);//get(index)
//        arrayList.set(0,"mayikt");//set(index,"值")
//        Object[] objects = new Object[10];
//        objects[0]="mayikt01";
//        objects[1]="mayikt02";
//        objects[2]="mayikt03";}/*** 时间复杂度* O(1): 基于数组的下标 index 查询 只需要查询一次，例如：Array[0]* O(n): 从头查询到尾部，例如:根据元素查询 将整个数组遍历 从头遍历到尾部*//*** ArrayList.get(index) 根据index下标查询的* 时间复杂度 O(1)* 如果 需要根据元素值查询 需要开发者 自定义* .set()也是一样，是根据index下标查询并更改的* 时间复杂度 O(1)* 如果是根据元素的值 修改 效率是非常的低的——时间复杂度 O(n)*//*** 为什么arrayList集合增加删除效率非常低* 数组——原生数组没有扩容的机制* ArrayList 最开始底层默认初始化数组的容量——10** 动态扩容如何实现的？——扩容机制 效率非常低* 当10个空间满了，想存入第11个元素时，就会动态的创建一个原来数组的1.5倍(15)的新数组* 然后将旧数组中的10个元素copy到新的数组中，之后才可以添加第11个元素** 删除效率也是非常低的？* 加入现在就10个元素，删除第2个元素* 当删除之后，后面的下标为3-9的元素整体向前移一位，* 然后将下标为9的位置置为null*/
}

底层源码实现

ArrayList<String> arrayList = new ArrayList<>();

• 数组 初始化是没有容量的
• 懒加载的形式，正真需要使用的时候才会加载，例如（arrayList.add()）

package com.collection.Demo07;public class MayiktArrayList<E> {/*** 分析源码的技巧* 1. 先看构造函数，通过无参构造函数可以得出* public ArrayList() {*    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;* }* transient Object[] elementData;* 默认底层初始化了一个空数组** 2. 看方法实现* 2.1 分析add()底层实现* 2.1.1 判断是否需要扩容* 2.1.2 直接通过index赋值*/private Object[] elementData;//集合需要存放元素private int size; //默认0public MayiktArrayList() {//无参构造函数 默认初始化容量大小 10elementData = new Object[10];}public void add(E e) {//第1次存放元素——index=0//第2次存放元素——index=1//所以这里定义了变量 sizeelementData[size++] = e;}
}

下一篇文章：Vector 与 ArrayList 集合区别