Java常用数据结构之List
前言
作为Java系开发者对Java集合类的使用应该是较为频繁的，也是面试中经常会被问的问题。一直想整理一下Java集合和Android中的优化集合类，借这次机会把Java中的常用集合都整理一遍。由于JDK 11已出，本系列文章中的源码都来自JDK 11（集合这部分应该没什么变化）。
List类关系
List集合中常用的就是ArrayList和LinkedList，（曾经被问到这两个类的祖先基类是啥？）直接上类图：
可以看到关键接口类：List、Collection和Iterable属于继承关系，相当于做了一个职责区分（设计模式的职责单一原则）。而AbstractCollection、AbstractList和AbstractSequentialList是抽象类，对外提供了可扩展的模板（设计模式中的模板模式）。如果你想自己设计一个List，可以直接继承AbstractList或者AbstractSequentialList类，实现其中的特定方法即可。
AbstractList和AbstractSequentialList
AbstractList实现了部分List接口中的方法，为想实现List接口的开发者提供了便利。
如果开发人员想要实现一个不可修改的List，那么只需要继承该类，然后重写两个方法：get(int)和size()方法。
如果开发人员想要实现一个可修改的List，那么需要重写set()方法，如果不重写会抛出UnsupportedOperationException异常，如果size()的大小是可变的，那么开发人员还需要重写add(int, E)和 remove(int)方法。
AbstractList实现了两种默认迭代器：
private class Itr implements Iterator
private class ListItr extends Itr implements ListIterator
也就是说，子类可以不用实现iterator()和listIterator()方法。
该类只有一个成员变量：该List在结构上已经被修改的次数。
protected transient int modCount = 0;
Iterator迭代器和ListIterator迭代器会使用到该变量，如果迭代器的expectModCount与该变量的值不同，那就会抛出ConcurrentModificationException异常，在官方文档中称其为fail-fast。
AbstractList实现了两种子列表：
private static class SubList extends AbstractList
private static class RandomAccessSubList
extends SubList implements RandomAccess
SubList中的方法调用其实还是调用的父类方法，即AbstractList。这里主要说一下RandomAccess类，它是一个空接口，用来标记是否可以随机访问。能随机访问代表在查找的时候可以用效率更高的算法（相较于顺序访问，典型例子Arraylist）。
AbstractSequentialList继承自AbstractList，是对顺序访问列表的一种扩展。它的iterator()方法直接返回的是listIterator()。
/**
* Returns an iterator over the elements in this list (in proper
* sequence).<p>
*
* This implementation merely returns a list iterator over the list.
*
* @return an iterator over the elements in this list (in proper sequence)
*/
public Iterator<E> iterator() {
return listIterator();
}
1
2
3
4
5
6
7
8
9
10
11
ArrayList分析
ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输；实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问；实现了Cloneable接口，能被克隆（浅拷贝）。
关键点
1、ArrayList是基于数组实现的，是动态数组，动态增长内容容量，每次扩展为原来的1.5倍，默认容量大小10。
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* Returns a capacity at least as large as the given minimum capacity.
* Returns the current capacity increased by 50% if that suffices.
* Will not return a capacity greater than MAX_ARRAY_SIZE unless
* the given minimum capacity is greater than MAX_ARRAY_SIZE.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 这里就是扩展1.5倍
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2、ArrayList不是线程安全的，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList，也可以用CopyOnWriteArrayList类。
3、ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用ArrayList，否则建议使用LinkedList。
特点
ArrayList中允许元素为null。
ArrayList查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。
LinkedList分析
LinkedList比ArrayList多实现了一个Deque接口，即：双端队列。LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆（浅拷贝）；
关键点
1、LinkedList是基于双向链表（已经不再是双向循环列表）实现的；除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2、LinkedList同样是非线程安全的
特点
LinkedList中允许元素为null。
不存在容量不足的问题，所以这里没有扩容的方法。
插入删除效率高，查找效率低。
总结
多线程环境下使用ArrayList和LinkedList时注意线程同步。
根据数据特点和使用环境进行选择。