Java中常见数据结构（一）——ArrayList

2019-04-13 本文已影响0人 vvweilong

Java中最常见的数据结构莫过于ArrayList与HashMap了
首先看看ArrayList类：
对于数据我们做的最多的无非为增删查三项了，那么我们首先看看ArrayList增删查方法。
增 add方法：

add方法
add（E e）方法在末尾加入一个元素e
add（int index,E e）方法在指定位置加入一个元素。
删 remove方法：

remove方法
remove(int index) 指定位置的删除
remove(E e)指定元素的删除
查 get方法

get方法
get（int index）查找指定位置的元素

ArrayList 从名字我们能看出底层的基本数据结构是由数组实现的，而数组的特性是随机查找的性能好，对于增加和删除操作效率较低，所以ArrayList 似乎是更适合用于数据查找的一种结构；为了应对改善这种性能缺陷我们有了另一个类 LinkedList
依然来看增删查三种方法

add(E e)

add(int index,E e)

remove(int index)

remove(Object o)

get(int index)
看方法似乎是一样的，那么ArrayList与LinkedList实现这些方法的区别在哪呢？
他们的区别也就是性能差异的地方了首先看 get方法

get方法对比
左边为ArrayList的实现，右边为LinkedList的实现
可以看到 ArrayList的指定位置查找直接用数组的随机查找能力返回了结果，而LinkedList 进入了node(index)来查找结果

node(index)
node(index)中对链表进行了一次遍历，来查找目标位置的元素，当next的次数到达index 指定的位置时返回结果
时间复杂度数组的随机查找为 O(1) 而链表实现的时间复杂度为遍历的O(n)
在看添加方法

add(index,e)对比

add(e)对比
可以看到每次add操作 ArrayList 都会对当前elementData数组的长度进行操作
而LinkedList则只对当前节点的前驱和后继进行了处理

我们知道数组一旦分配了空间长度就不能变了，但是ArrayList创建的时候我们并不知道需要的长度是多少，而底层又是不能改变长度数组结构，这里是怎么处理的呢？
数据长度的变化由add/remove 引起所以我们由add方法入手

add(index,e)
可以看见在加入新元素时首先进行了一次ensureCapacityInternal（size+1）操作
直觉这里是对底层数组的扩容操作进去看一下

ensureCapacityInternal中
首先判断了当前数组是否是默认空数组，如果是比较新的容量与默认容量的大小来决定目标容量minCapacity。
接着进入ensureExplicitCapacity
判断了一下目标容量minCapacity是否比当前已有容量大，如果需要扩容执行grow方法
进入grow方法中
旧容量oldCapacity 为现有元素的长度
新容量newCapacity = oldCapacity+(oldCapacity>>1);
即1.5倍原有容量
最终使用Arrays.copyOf(sourceArray,capacity);创建了新的数组