关于Java的List对象
这篇文章的目标是什么？
在Java中，有很多方便使用的集合类。我认为List和Set是它们的代表，但是根据每个实现的不同，它们各自具有不同的特点，比如插入速度快但访问速度慢等等。在这篇文章中，我打算通过查看Java的实现来复习一些基础知识。
这次我们将专注于集合中最常用的List系列，尤其是ArrayList和LinkedList。
源代码分别引用自
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#ArrayList
以及
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/LinkedList.java#LinkedList.Node。
ArrayList和LinkedList的区别
在数据处理方面有所差异。
ArrayList在内部具有一个对象数组，元素被存储在其中。LinkedList将元素存储在节点中，并通过连接这些节点来实现有序的集合。
ArrayList 是
transient Object[] elementData; // non-private to simplify nested class access
只需要一个选项：对于这个数组来说，基本概念就是该数组的实体。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
我通过add和get方法来操作，类似这样的方式。
在add方法中，通过ensureCapacityInternal来检查数组的容量并存储数据，如果超过了数组的最大容量，就会调用grow方法来扩展数组。默认情况下，数组的大小会扩展为原来大小的1.5倍。
一方，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;
}
}
这个节点保留着指向下一个节点和前一个节点的引用。
而LinkedList本身保留着Node的first和last。
以这种方式，从头部或尾部开始，依次遍历节点到达目标索引。
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;
}
}
因为具有这样的特性，一般来说，ArrayList的访问时间要比LinkedList快得多。这些方面明显是ArrayList作为标记接口具有RandomAccess的明确表示。
然而，如果在列表的中间插入元素，ArrayList会使用System.arraycopy来复制数组。所以在这样的情况下，应该使用LinkedList。
对于拓展for循环、foreach等
通常我们会使用for等循环语句来遍历List的所有元素，但是写法确实有很多种。根据我初步的观察，大致可以分为以下四种方式。
1: 用于循环的”for”语句
for(int i=0; i<list.size(); i++) {
list.get(i);
}
2：迭代器
Iterator itr = list.iterator();
while(itr.hasNext()){
itr.next();
}
3: 增强型for循环
for(Object o : list) {
}
4: 对于每个元素（从Java8开始）
list.forEach(o -> { });
这一次我们也调查了这四个实现的性能。
对于第一个实现，我认为现在没必要再说了。
关于第二个实现的迭代器，大体上都是拥有实现Iterator接口的内部类，并在其中管理名为cursor的当前位置。特别是对于LinkedList来说，当尝试通过get方法访问元素时，它会从链表的开头（或末尾）开始搜索，所以使用这个迭代器进行访问会更快速。
至于第三个所谓的增强for循环，根据这篇文章，它似乎是这样工作的。
for(Object o : list) {
System.out.println(o.toString());
}
以下是一种选项的中文释义：
这是
Object o;
for(Iterator it = list.iterator(); it.hasNext(); System.out.println(o.toString()) {
o = it.next();
}
这个结果就是，它会在内部调用迭代器。通过使用增强的for循环，可以方便地进行使用迭代器的调用。
4的forEach。这是从Java 8开始添加的格式。它接受一个Consumer作为参数，并逐个应用于每个元素。
然而，这个forEach最初是在Iterable中实现的。
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
换句话说，默认情况下通常使用增强型for循环。
顺便提一下，在ArrayList中，forEach方法被覆写为以下的形式。
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
除了并列访问的异常处理机制，可以看出我们使用普通的for循环（1）来访问元素的方法。ArrayList是RandomAccess，所以相比使用Iterator访问元素，直接使用get方法的访问速度更快，所以实现采用了这种方式。
最后，为了好好利用这些方法，我们对这四种方法进行了性能测量。测试对象是Java8的LinkedList和ArrayList。测试环境是MacBook Air（11英寸）1.7GHz Core i7 / 8GB RAM。对于长度为1000的固定列表，我们分别重复30,000次对所有元素的访问，并测量其速度。
结果如下所示。
我认为基本上会趋于预期值。我很担心Iterator和增强for循环的值不一致，这可能是由于误差引起的吗？关于forEach，我们可以将其视为调用Lambda所带来的额外开销，是这样理解吗？这些值是这样得到的。
鑑於收到了評論，我決定進行追加。 yú le , wǒ .)
确实，如果使用LinkedList，会出现无法使用的情况。但是相比ArrayList，LinkedList在某些情况下具有优势。这种情况是在列表中插入元素的情况。
因此，我在列表中插入元素，并重复这个动作30000次，同时测量性能。
结果如下所示。
因此，結果顯示LinkedList明顯比其他更快。
整理
我在Java中调查了ArrayList和LinkedList这两个最常用的列表的基本特性。此外，我还进行了一些性能测量，探究了诸如for循环和增强for循环等迭代方法的性能特性。
如果有任何批评或评论，请您务必告诉我！
