讨论：如何高效使用List
?大家都知道Java list 的实现类有两个，分别是：ArrayList、LinkedList。实际工作中，使用最多的是ArrayList。ArrayList 的底次实现是数据，LinkedList的层次是链表。书上告诉我们：当需要在List中间插入数据时，应该使用LinkedList，ArrayList 有高效的访问效率。真的是这样的吗？看如下的代码：
List<Integer> arrays = new ArrayList<Integer>();for (int i = 0; i < 10000; i++) {arrays.add(i);}? 向一个List中插入10000个数据，应该使用ArrayList？我们来简单的分析一下ArrayList的代码：
?
public ArrayList(int initialCapacity) {super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);this.elementData = new Object[initialCapacity]; } /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() {this(10); }? 可以看出：ArrayList 存储数组的初始长度是 10 。那么，当数组满了时，ArrayList是怎么样做的呢？继续看代码：
?
?
public boolean add(E e) {ensureCapacity(size + 1); // Increments modCount!!elementData[size++] = e;return true; }?
public void ensureCapacity(int minCapacity) {modCount++;int oldCapacity = elementData.length;if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity)newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);} }? 注：当向ArrayList中添加一个数据时，调用 ensureCapacity 方法，判断数组的空间是否能满足存储当前数据的条件，如不能，使用Arrays.copyOf(oldArray,newLength) 把数组中的旧数据copy到一个新的、更长的数组中。在copy过程中，是这么做的：首先CPU寻址：找到一个连续的、空白的、满足指定长度的空闲内存块，找到后，进行搬数据操作。这个过程会随着数据越来越多，数组的长度越来越大，效率会急剧下降。因此，当我们使用List来存储“大数据”时，首选LinkedList。好处是：LinkedList 是使用链表来存储数据，向LinkedList中插入数据时，不会出现寻址和copy数据的操作，更正确的说，会更快的找到满足存储条件的空闲块。基于上述理由：代码修改为：
List<Integer> arrays = new LinkedList<Integer>();for (int i = 0; i < 1000; i++) {arrays.add(i);}?LinkedList 也存在不足之处：如下代码：
for (Integer val : arrays) {System.out.println(val);}?循环遍历List。如果List是LinkedList实现的，每遍历一个元素，都要寻找下个数据的地址，因为元素并不是存储在连续的内存块中。这时的寻址也会很“消费时间”。优化方法：把生成后的LinkedList再放入一个ArrayList中，生成一个ArrayList 对象，ArrayList 的存储在内存块中是连续存放的，在遍历时，不会因寻址“浪费时间”了。优化后的代码如下：
List<Integer> arrays = new LinkedList<Integer>();for (int i = 0; i < 1000; i++) {arrays.add(i);}arrays = new ArrayList<Integer>(arrays);for (Integer val : arrays) {System.out.println(val);}? 上面讲到的方法，并没有进行严格的测试，肯定会有不足之处。欢迎大家批评！
?
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; }arrays = new ArrayList<Integer>(arrays);
