ArrayList结构图
ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList&＃xff0c;实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口&＃xff0c;所以ArrayList 是支持快速访问、复制、序列化的。
ArrayList类简介
- 1、ArrayList是内部是以动态数组的形式来存储数据的、知道数组的可能会疑惑&＃xff1a;数组不是定长的吗&＃xff1f;这里的动态数组不是意味着去改变原有内部生成的数组的长度、而是保留原有数组的引用、将其指向新生成的数组对象、这样会造成数组的长度可变的假象。
- 2、ArrayList具有数组所具有的特性、通过索引支持随机访问、所以通过随机访问ArrayList中的元素效率非常高、但是执行插入、删除时效率比较地下、具体原因后面有分析。
- 3、ArrayList实现了AbstractList抽象类、List接口、所以其更具有了AbstractList和List的功能、前面我们知道AbstractList内部已经实现了获取Iterator和ListIterator的方法、所以ArrayList只需关心对数组操作的方法的实现、
- 4、ArrayList实现了RandomAccess接口、此接口只有声明、没有方法体、表示ArrayList支持随机访问。
- 5、ArrayList实现了Cloneable接口、此接口只有声明、没有方法体、表示ArrayList支持克隆。
- 6、ArrayList实现了Serializable接口、此接口只有声明、没有方法体、表示ArrayList支持序列化、即可以将ArrayList以流的形式通过ObjectInputStream/ObjectOutputStream来写/读。
基础属性
ArrayList部分源码如下&＃xff1a;
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable{ private static final int DEFAULT_CAPACITY &＃61; 10; private static final Object[] EMPTY_ELEMENTDATA &＃61; {}; private transient Object[] elementData; private int size; //...省略部分代码}
如上代码中为ArrayList的主要属性:
- DEFAULT_CAPACITY&＃xff1a;默认容量&＃xff0c;即为初始值大小
- EMPTY_ELEMENTDATA&＃xff1a;共享的空数组&＃xff0c;用于初始化空实例
- elementData&＃xff1a;ArrayList内部结构&＃xff0c;是一个Object[]类型的数组
- size&＃xff1a;数组长度大小
构造方法
如下为ArrayList的构造方法:
1.public ArrayList(int initialCapacity)
2.public ArrayList()
3.public ArrayList(Collection extends E> c){
elementData &＃61; c.toArray();
size &＃61; elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() !&＃61; Object[].class)
elementData &＃61; Arrays.copyOf(elementData, size, Object[].class);
}
- 1.构造方法1&＃xff0c;表示接受指定地容量值&＃xff0c;初始化创建数组&＃xff0c;建议在可估算数组大小时,创建ArrayList可指定
- 2.构造方法2&＃xff0c;是默认的构造方法&＃xff0c;它将创建一个空数组
- 3.构造方法3&＃xff0c;接收一个Collection的实体&＃xff0c;将该Collection实体转换为ArrayList对象
主干流程
1.添加指定元素代码如下
public boolean add(E e) { ensureCapacityInternal(size &＃43; 1); // Increments modCount!! elementData[size&＃43;&＃43;] &＃61; e; return true;}
可以看到实际上只有3行代码&＃xff0c;其流程主要如下&＃xff1a;
1.扩容 (这里便解释了&＃xff0c;在介绍时提出的问题)&＃xff1a;
主要源码如下
private void ensureCapacityInternal(int minCapacity) {
if (elementData &＃61;&＃61; EMPTY_ELEMENTDATA) {
minCapacity &＃61; Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount&＃43;&＃43;;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//最大数组容量
private static final int MAX_ARRAY_SIZE &＃61; Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity &＃61; elementData.length;
int newCapacity &＃61; oldCapacity &＃43; (oldCapacity >> 1);
if (newCapacity - minCapacity <0)
newCapacity &＃61; minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity &＃61; hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData &＃61; Arrays.copyOf(elementData, newCapacity);
}
- 第一个方法的逻辑为&＃xff1a;判断是不是第一次添加元素&＃xff0c;若为第一次&＃xff0c;则设置初始化大小为默认的值10,否则使用传入的参数
- 第二个方法的逻辑为&＃xff1a;若长度大于数组长度&＃xff0c;则扩容
- 第三个方法的逻辑为:
1·扩容的大小为3/2倍原数组长度
2.若值newCapacity比传入值minCapacity还要小&＃xff0c;则使用传入minCapacity&＃xff0c;若newCapacity比设定的最大数组容量大&＃xff0c;则使用最大整数值
3.实际扩容&＃xff0c;使用了Arrays.copyof(elementData, newCapacity) (此处有两个问题 1.为啥扩容是原来的3/2倍原数组的长度? 2.调用Arrays.copyOf(elementData, newCapacity)方法具体做了什么操作? )
2.赋值&＃xff1a;将添加的值放置到size&＃43;&＃43;的位置上
3.返回&＃xff1a;返回true
2.添加指定元素到指定的位置上代码如下:
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size &＃43; 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index &＃43; 1,
size - index);
elementData[index] &＃61; element;
size&＃43;&＃43;;
}
其流程为:
- 1.校验下标&＃xff1a;调用rangeCheckForAdd方法进行下标校验&＃xff0c;不正确则会抛出IndexOutOfBoundsException异常
- 2.扩容&＃xff1a;详见上部分中做的介绍
- 3.移动数据&＃xff1a;将数据index后面的数据&＃xff0c;都向后移动
- 4.赋值&＃xff1a;将加入的值放置到index位置中
- 5.长度增加&＃xff1a;长度增加
常见问题
1.问题描述
在使用ArrayList比较常见的一个问题就是在遍历ArrayList的时候调用remove()方法进行元素的删除操作,从而得到意想不到的结果&＃xff0c;本人在开发过程中也遇到过这样的问题&＃xff0c;所以在这里提出了&＃xff0c;希望能够帮助到大家。
2.实例及分析
如下代码中&＃xff0c;在遍历List时&＃xff0c;调用了remove方法&＃xff0c;删除元素a
//arrayList中的值为 [a,a,c,a,a]for (int i &＃61; 0; i - 这段代码看似解决了删除列表中所有的a元素&＃xff0c;但是删除后得出List的结果为[a, c, a]&＃xff0c;为什么这种方式没有达到想要的效果&＃xff0c;其实仔细分析后会发现&＃xff0c;在调用remove()方法时List的长度会发生变化而且元素的位置会发生移动&＃xff0c;从而在遍历时list实际上是变化的&＃xff0c;例如
- 当i&＃61;0时&＃xff0c;此时list中的元素为[a,a,c,a,a],
- 但当i&＃61;1时&＃xff0c;此时List中的元素为[a,c,a,a],元素的位置发生了移动&＃xff0c;从而导致在遍历的过程中不能达到删除的效果
3.解决方案
通过上述的分析可以看出&＃xff0c;出现问题的原因是元素的位置发生了移动&＃xff0c;从而导致异常的结果 方案一、逆向遍历List删除,代码如下&＃xff0c;这种做法可行主要是因为remove()方法删除index处的元素时&＃xff0c;是将index&＃43;1到size-1索引处的元素前移&＃xff0c;而逆向遍历可以避免元素位置的移动
for (int i &＃61; arrayList.size()-1; i >&＃61;0 ; i--) {
if (arrayList.get(i) &＃61;&＃61; "a") {
arrayList.remove(i);
}
}
System.out.println(arrayList);
方案二、使用迭代器中的remove方法&＃xff0c;迭代器具体参考Iterator详解&＃xff0c;主要代码如下(这种方式比较推荐)
Iterator ite &＃61; arrayList.listIterator();while (ite.hasNext()){ if(ite.next() &＃61;&＃61; "a") ite.remove();}System.out.println(arrayList);
手写一个ArrayList
自己手写一个ArrayList,代码如下&＃xff1a;
public class MyArrayList implements Iterable { private T[] theItems; private int theSize; private static final int DEAULT_CAPACITY&＃61;10; public MyArrayList(){ theSize&＃61;0; ensureCapacity(DEAULT_CAPACITY); } public void add(T data){ if(size()&＃61;&＃61;theItems.length){ ensureCapacity(size()*2&＃43;1); } theItems[size()]&＃61;data; theSize&＃43;&＃43;; } public void add(int index,T data){ if(size()&＃61;&＃61;theItems.length){ ensureCapacity(size()*2&＃43;1); } for(int i&＃61;theSize;i>index;i--){ theItems[i]&＃61;theItems[i-1]; } theItems[index]&＃61;data; theSize&＃43;&＃43;; } public T get(int index){ if(index<0|index>&＃61;size()){ throw new IndexOutOfBoundsException("index error"); } return theItems[index]; } public T remove(int index){ T removeData&＃61;get(index); for(int i&＃61;index;inewCapacity){ return; } T[] old&＃61;theItems; theItems&＃61; (T[]) new Object[newCapacity]; for(int i&＃61;0;i iterator() { return null; } &＃64;Override public void forEach(Consumer super T> action) { } &＃64;Override public Spliterator spliterator() { return null; }}
总结
- 1.ArrayList是基于数组实现的&＃xff0c;它的内存储元素的数组为 elementData;elementData的声明为&＃xff1a;transient Object[] elementData;
- 2.ArrayList中EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的使用&＃xff1b;这两个常量&＃xff0c;使用场景不同。前者是用在用户通过ArrayList(int initialCapacity)该构造方法直接指定初始容量为0时&＃xff0c;后者是用户直接使用无参构造创建ArrayList时。
- 3.ArrayList默认容量为10。调用无参构造新建一个ArrayList时&＃xff0c;它的elementData &＃61; DEFAULTCAPACITY_EMPTY_ELEMENTDATA, 当第一次使用 add() 添加元素时&＃xff0c;ArrayList的容量会为 10。
- 4.ArrayList的扩容计算为 newCapacity &＃61; oldCapacity &＃43; (oldCapacity » 1);且扩容并非是无限制的&＃xff0c;有内存限制&＃xff0c;虚拟机限制。
- 5.ArrayList的toArray()方法和subList()方法&＃xff0c;在源数据和子数据之间的区别&＃xff1b;
- 6.注意扩容方法ensureCapacityInternal()。ArrayList在每次增加元素(可能是1个&＃xff0c;也可能是一组)时&＃xff0c;都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时&＃xff0c;就设置新的容量为旧的容量的1.5倍加1&＃xff0c;如果设置后的新容量还不够&＃xff0c;则直接新容量设置为传入的参数(也就是所需的容量)&＃xff0c;而后用Arrays.copyof()方法将元素拷贝到新的数组。从中可以看出&＃xff0c;当容量不够时&＃xff0c;每次增加元素&＃xff0c;都要将原来的元素拷贝到一个新的数组中&＃xff0c;非常之耗时&＃xff0c;也因此建议在事先能确定元素数量的情况下&＃xff0c;才使用ArrayList&＃xff0c;否则不建议使用。
京公网安备 11010802041100号