一、数据结构
1.1 数组
ArrayList是一种数组类型的数据结构，数组是内存中一段地址连续的空间。
public static void main(String[] args) {
List<String> fruitList = new ArrayList<>();
fruitList.add("apple");
fruitList.add("banana");
fruitList.add("orange");
fruitList.add("grape");
}
我们使用如上代码创建的一个数组可以用示意图表示为：
数组结构示意图
1.2 链表
在JDK1.7之前的版本中，LinkedList是一种链表类型的数据结构（双向循环链表），它所包含元素的内存空间地址是离散排列的，每一个元素除了包含所代表的内容之外，还需要维护两个指针，分别指向上一个和下一个元素，除此之外，第一个节点称为头节点，是整个循环链表的开始，也是结束。
public static void main(String[] args) {
List<String> fruitList = new LinkedList<>();
fruitList.add("apple");
fruitList.add("banana");
fruitList.add("orange");
fruitList.add("grape");
}
我们使用如上代码创建的一个链表可以用示意图表示为：
双向循环链表结构示意图
而在JDK1.7及以后LinkedList取消了双向链表的循环特性，新增了明确的链头和链尾，其结构示意图和上述类似，只不过取消了循环的指针。
详细内容可以参考：JDK1.7-LinkedList循环链表优化
二、常见操作
2.1 尾部增加元素
ArrayList和LinkedList添加元素到尾部的代码，一模一样，可是它们内部的实现却完全不同。
首先看下ArrayList是如何实现的：
public boolean add(E e) {
// 确保新增加的元素有空间
ensureCapacityInternal(size + 1);
// 将新增加的元素置于尾部
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// elementData是一个Object[]数组，存放当前链表中所有的内容
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 确保最有足够的空间
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 超过当前已经分配的空间时需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 右移动一位代表除以2，所以此处是扩大到原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果三倍扩容还不够就置为需要的空间大小
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果需要的比数组最大长度还长就扩容为整数的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 将存储当前链表中内容的Object[]数组扩容到指定大小
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
因此，可以得出结论，当需要增加到尾部的元素不超过当前链表的已分配大小时，直接添加即可，非常快；当超过已分配大小的时候，需要花点时间先扩容。
然后对比看下LinkedList是如何实现的:
public boolean add(E e) {
// 将元素添加到链表的尾部
linkLast(e);
return true;
}
void linkLast(E e) {
// 链尾节点
final Node<E> l = last;
// 新建一个节点，存储需要新增的元素
final Node<E> newNode = new Node<>(l, e, null);
// 更新链尾节点为该新增的节点
last = newNode;
// 表示该新增的节点是该链表的第一个节点
if (l == null)
first = newNode;
else
// 原链尾节点指向该新增的节点
l.next = newNode;
size++;
modCount++;
}
该段源码较为简单明了，就是在内存中随便找了一个空间新建一个节点存储需要新增的内容，然后将其加入到原链表的关系中去。这中间没有涉及到空间大小检测和扩容，效率要比ArrayList高。
2.2 任意位置增加元素
ArrayList的实现如下：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
// 每次都要拷贝数组
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
可以看到，如果在ArrayList任意位置添加元素，由于数组是内存中地址连续的空间，因此每次都需要挪动数组内容，为新加入的元素腾出空间，在ArrayList比较长的时候，性能堪忧。
再看看LinkedList的实现：
public void add(int index, E element) {
checkPositionIndex(index);
// 加入到链尾的情况
if (index == size)
linkLast(element);
else
// 加入到任意位置的情况
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// 需要插入位置的原节点的前一个节点
final Node<E> pred = succ.prev;
// 新建一个节点，存储需要新增的元素
final Node<E> newNode = new Node<>(pred, e, succ);
// 该位置原节点的前一个节点设置为新增的这个节点
succ.prev = newNode;
// 如果该位置原节点没有前一个节点，则当前新增的节点就为头节点
if (pred == null)
first = newNode;
else
// 该位置原节点的前一个节点往后指向当前新增的节点
pred.next = newNode;
size++;
modCount++;
}
LinkedList在任意位置新增节点和在尾部新增节点的操作基本类似，没有空间和扩容的限制，更不存在挪动其它元素节点的情况，唯一需要做的就是找到需要操作的链表的位置，如下是这个操作的源码：
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
可以看到，如果我们是在LinkedList的头部或者尾部新增节点，那效率非常高，这个在上面已经说明过了；但是如果要在中间某个位置新增节点，则需要通过for循环遍历找寻到该位置，所以，如果LinkedList很长的话，这步操作可能会比较影响性能。
2.3 任意位置删除元素
同在任意位置增加元素，此处不再赘述。
三、扩容机制
3.1 数组扩容
这个在如上ArrayList新增元素部分已经说明过了，参照源码的阅读，整个扩容步骤大致如下：
- 首先检测已分配空间是否足够；
- 不够的情况下首先扩容1.5倍；
- 扩容1.5倍还不够，就扩容到需要增加内容后的指定大小；
- 如果需要扩容的指定大小比数组最大值还大，就扩容到整数的最大值；
3.2 链表扩容
链表不存在空间检测和扩容的情况，只要内存足够，就可以一直新增元素。
四、循环遍历上的差异
4.1 使用for循环
我们使用如下的代码分别对ArrayList和LinkedList进行测试：
public static void main(String[] args) {
// List<String> fruitList = new LinkedList<>();
// List<String> fruitList = new ArrayList<>();
for(int i=0;i<1000000;i++){
fruitList.add("apple"+ i);
}
// 遍历fruitList
String fruitName;
Long startTime = System.currentTimeMillis();
for(int j = 0; j < fruitList.size(); j++){
fruitName = fruitList.get(j);
}
System.out.println("time cost:" + (System.currentTimeMillis() - startTime));
}
运行结果：
- ArrayList:16
- LinkedList:等待很久都没有结果
4.2 使用迭代器
public static void main(String[] args) {
// List<String> fruitList = new LinkedList<>();
// List<String> fruitList = new ArrayList<>();
for(int i=0;i<1000000;i++){
fruitList.add("apple"+ i);
}
// 遍历fruitList
String fruitName;
Long startTime = System.currentTimeMillis();
for(Iterator<String> iterator = fruitList.iterator(); iterator.hasNext();){
fruitName = iterator.next();
}
System.out.println("time cost:" + (System.currentTimeMillis() - startTime));
}
运行结果:
- ArrayList:16
- LinkedList:16
4.3 使用foreach
public static void main(String[] args) {
// List<String> fruitList = new LinkedList<>();
// List<String> fruitList = new ArrayList<>();
for(int i=0;i<1000000;i++){
fruitList.add("apple"+ i);
}
// 遍历fruitList
String fruitName;
Long startTime = System.currentTimeMillis();
for(String name : fruitList){
fruitName = name;
}
System.out.println("time cost:" + (System.currentTimeMillis() - startTime));
}
运行结果:
- ArrayList:16
- LinkedList:32
4.4 结论分析
对于ArrayList，使用三种循环中的任何一种，效果都是差不多的。其实这也很好理解，数组天然对随机访问具有优势。
对于LinkedList，在使用迭代器遍历的时候，效率最高，其次是foreach循环，最不可接受的是使用for循环。
为什么不同的遍历循环会表现出不一样的性能呢？除了ArrayList和LinkedList的数据结构不同外，各个遍历循环的内部机制其实也是不同的。
- 迭代器
迭代器是创造一个类似指针的东西，其保留的是当前遍历过程中当前读取元素的位置。
在当前元素获取后，就调用next跑到下一个元素的位置，如此，无论是ArrayList还是LinkedList，使用迭代器进行遍历其实就是将所有元素挨个走了一遍。
- foreach语句
我们编译如上foreach的实验代码后，获取到class文件，然后使用反编译工具进行反编译，得到的结果如下(ArrayList和LinkedList的结果是一样的)：
public static void main(String args[])
{
List fruitList = new LinkedList();
for (int i = 0; i < 0xf4240; i++)
fruitList.add((new StringBuilder()).append("apple").append(i).toString());
Long startTime = Long.valueOf(System.currentTimeMillis());
for (Iterator iterator = fruitList.iterator(); iterator.hasNext();)
{
String name = (String)iterator.next();
String fruitName = name;
}
System.out.println((new StringBuilder()).append("time cost:").append(System.currentTimeMillis() - startTime.longValue()).toString());
}
最明显的可以看到，foreach语句变成了迭代器语句，因此可以认为，foreach的遍历，其底层其实使用的就是迭代器。
- for循环
for循环没有指针，其每次的迭代都是重新寻找当前元素。
对于ArrayList而言，数组优良的随机读写特性使得for循环寻找当前元素几乎不用花时间，整个遍历过程的复杂度为O(n)；
但是对于LinkedList就不同了，每个元素的寻找过程都是从链表头或者链表尾开始一个个地寻找，整个遍历过程的复杂度为O(n^2)，难怪那么慢呢。
五、使用总结
在学习了数组和链表的特性后，相信我们一定能深刻地认识到：
- 在需要频繁查找元素的时候，优先使用ArrayList;
- 在需要频繁插入和删除任意位置元素的时候，优先使用LinkedList;
- foreach其实就是迭代器的语法糖；
- 在使用LinkedList的时候，千万不要使用for循环。
网友评论