转载

一文讲清楚ArrayList的原理

01 原理

ArrayList底层采用数组实现，具有也具有数组的优缺点，同时支持动态扩容（扩展为原来的1.5倍）。所以它非常适合需要使用索引快速访问的场景。同时由于其自动扩容的功能，我们需要注意在初始化集合时需要指定大小。

##02 特点

具有连续的内存空间，支持随机访问：

修改操作性能好：

插入操作性能差(插入位置不在末尾时，需要内存复制)：

删除性能差（删除位置不在末尾时，需要内存复制） 。在实际应用中为了提高删除性能，有时候会先标记数据数字删除（会造成内存碎片多），到了内存不够的时候再去真正删除数据，并进行内存复制，如GC中标记-整理算法。具体流程如下（也可以先进行内存复制,再删除最后一位数据）：

## 03 具体代码

最后从源码里具体分析一下，ArrayList中的添加(add)，随机访问（get），删除(remove)，插入（add）,扩容操作(grow)。

添加（add）****：

public boolean add(E e) {       
  ensureCapacityInternal(size + 1); // 确保数组容量足够，否则进行扩容grow       
  elementData[size++] =e;// 为数组[size]赋值,当前数据长度+1        return true;}
复制代码

随机访问（get）:

public E get(int index) {       
   rangeCheck(index); //检查数组下标值是否超过list实际含有的数据量 
   return elementData(index);// 随机访问数组   
}
复制代码

删除(remove)：

public E remove(int index) {       
 rangeCheck(index);//检查数组下标值是否超过list实际含有的数据量        
 modCount++;// 迭代遍历时，用于确定list是否被操作过了       
 E oldValue =elementData(index);//旧值         
int numMoved = size - index - 1;        i
f (numMoved > 0) // 删除的位置不是末尾数据，进行数组的复制           
        System.arraycopy(elementData,index+1, elementData, index,  numMoved);
        elementData[--size] =null; //删除了一个值，所以原来的数组最后一位数据为null       
        return oldValue;   
 }
复制代码

插入（add）:

public void add(int index, E element) {        
rangeCheckForAdd(index);       
 ensureCapacityInternal(size + 1); // Increments modCount!!grow        
System.arraycopy(elementData, index,elementData, index + 1, size- index); //复制数组       
 elementData[index] =element;// 插入数据     
   size++;   
 }
复制代码

扩容（grow):

private void grow(int minCapacity) {        // overflow-conscious code
 int oldCapacity = elementData.length;      
 int newCapacity =oldCapacity + (oldCapacity >> 1);//新容量原来的1.5倍
 if (newCapacity - minCapacity < 0)            
        newCapacity = minCapacity;        
 if (newCapacity - MAX_ARRAY_SIZE >0) 
   newCapacity =hugeCapacity(minCapacity);  // minCapacity is usually close tosize, so this is a win:        
elementData =Arrays.copyOf(elementData, newCapacity);// 原来的数据复制到扩容后的数组中    }
复制代码

原文 https://juejin.im/post/5f0c7883e51d4534a90a96b9

正文到此结束