List完全解析

一 概览

image.png

List 接口的继承结构如图所示，其中的 RandomAccess 接口没有声明任何方法，只是作为标记。同样类似的还有Serializable和Cloneable接口，RandomAccess的注释如下

public interface **RandomAccess**

Marker interface used by  List  implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

The best algorithms for manipulating random access lists (such as  ArrayList ) can produce quadratic behavior when applied to sequential access lists (such as  LinkedList ). Generic list algorithms are encouraged to check whether the given list is an  instanceof  this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

It is recognized that the distinction between random and sequential access is often fuzzy. For example, some  List  implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a  List  implementation should generally implement this interface. As a rule of thumb, a  List  implementation should implement this interface if, for typical instances of the class, this loop:

for (int i=0, n=list.size(); i < n; i++)

list.get(i);

runs faster than this loop:

for (Iterator i=list.iterator(); i.hasNext(); )

i.next();

This interface is a member of the  [Java Collections Framework ][2].

可知，当数据量很大时对于声明了 RandomAccess 接口的类使用数组比使用 iterator 遍历速度更快，因此，一个常见的用法是，遍历大数据量的list时要作一个判断：

if (list instance of RandomAccess)

{

  for(int m = 0; m < list.size(); m++){

  }

} else {

  Iterator iter = list.iterator();

  while(iter.hasNext()){}

}

二 ArrayList篇

• trimToSize，由于 ArrayList 每次增长会预申请多一点空间，这样就会出现当 size() = 1000 的时候， ArrayList 已经申请了 1200 空间的情况，trimToSize 的作用则是去掉预留元素位置，就是删除多余的 200 ，改为只申请 1000, 内存紧张的时候会用到

• System.arraycopy( elementData , 0 , a , 0 , size ) 和Arrays.copyof的区别在于Arrays.copyof会多拷贝一份。System.arraycopy为什么快

• fastRemove，少了rangecheck，比普通的remove速度更快

• retainAll 和 removeAll 分别调用 batchRemove(c ,true ) 和 batchRemove(c ,false ) ;

• toArray(): 对该方法返回的数组，进行操作（增删改查）都不会影响源数据（ ArrayList 中 elementData ）。二者之间是不会相互影响的。

• subList(): 对返回的子集合，进行操作（增删改查）都会影响父集合。而且若是对父集合中进行删除操作（仅仅在删除子集合的首个元素）时，会抛出异常

• modCount，用来记录 ArrayList 结构发生变化的次数，如果一个动作前后 modCount 的值不相等，说明 ArrayList 被其它线程修改了，如果在创建迭代器之后的任何时候以任何方式修改了列表（增加、删除、修改），除了通过迭代器自己的 remove 或 add 方法，迭代器将抛出 ConcurrentModificationException 异常，需要注意的是：这里异常的抛出条件是检测到 modCount != expectedmodCount ，如果并发场景下一个线程修改了 modCount 值时另一个线程又 " 及时地 " 修改了 expectedmodCount 值，则异常不会抛出。所以不能依赖于这个异常来检测程序的正确性。【这个变量对于实现Iterator功能的非线程安全集合都适用，也就是说同样适用于HashMap，而线程安全的CopyOnWriteArrayList和ConcurrentHashMap都不用modCount机制】

public E next() {

this.checkForComodification();

...

}

final void checkForComodification() {

if(ArrayList.this.modCount != this.expectedModCount) {

throw new ConcurrentModificationException();

}

}
public boolean hasNext() {

return this.cursor != ArrayList.this.size;

}

如果删除的是 list 里倒数第二个值，这样触发 hasNext() 的时候结果正好为 false 退出循环不继续执行 next() 也就不会报错

ArrayList list = new ArrayList() {{
  add("a");
  add("b");
  add("c");
}};

for (String string:list){
  if (string.equals("a")) {  //这里若把a改成b则不会报错
    list.remove(string);
    }
}
System.out.println(list);

• Iterable只是返回了Iterator接口的一个实例，这里很是奇怪，为什么不把两个接口合二为一，直接在Iterable里面定义hasNext(),next()等方法呢？原因是实现了Iterable的类可以在实现多个Iterator内部类，例如LinkedList中的ListItr和DescendingIterator两个内部类，就分别实现了双向遍历和逆序遍历。Java中Iterable和Iterator接口

• Iterator，ListIterator以及Spliterator
  实现 Spliterator，然后用 StreamSupport 就可以构造一个 Stream 了，相当方便。对于 Spliterator 接口的设计思想，应该要提到的是 Java7 的 Fork/Join( 分支 / 合并 ) 框架，总得来说就是用递归的方式把并行的任务拆分成更小的子任务，然后把每个子任务的结果合并起来生成整体结果。JDK8源码之Spliterator并行遍历迭代器

Normally, an application developer would not consume the  Spliterator  API directly. But if you are providing an API, and implement your own collection-like class, you can implement  Spliterator  to adapt your collection to the  Stream  API. This supports a functional approach, parallel processing, and other features.

For example, I wrote a utility to enumerate IP addresses in a network, specified by CIDR notation. It's not really a collection; that is, it doesn't carry list of all of the addresses in memory at once, only the network number and netmask. But by exposing a  Spliterator , it can be easily adapted to a  Stream . (Each  Spliterator  just tracks the current IP address and maximum address in its share of the network.)

Another example from the core Java runtime is  [DirectoryStream for traversing the file system. ][13]

Methods of Iterator:

* hasNext()

* next()

* remove()

Methods of ListIterator:

* add(E e)

* hasNext()

* hasPrevious()

* next()

* nextIndex()

* previous()

* previousIndex()

* remove()

* set(E e)

Methods of Spliterator:

* tryAdvance(Consumer<? super E> action) //就是顺序处理每个元素，类似 Iterator ，如果还有元素要处理，则返回 true ，否则返回 false

* forEachRemaining(Consumer<? super T> action) 

* trySplit()      //为 Spliterator 专门设计的方法，区分与普通的 Iterator ，该方法会把当前元素划分一部分出去创建一个新的 Spliterator 作为返回，两个 Spliterator 变会并行执行，如果元素个数小到无法划分则返回 null

* estimateSize()  //用于估算还剩下多少个元素需要遍历

* characteristics()  //表示该 Spliterator 有哪些特性，用于可以更好控制和优化 Spliterator 的使用

• 什么时候应该使用 List list = new ArrayList() 替代 ArrayList list = new ArrayList() ？

When you write:
List < String > list = new ArrayList < String >();
Then you are sure you'll use only the functionality of the  *interface*  [List ][8].
( ArrayList  implements  List , so  List  is more flexibl). Using this, allows you to change the  ArrayList  to other types in the future (like  LinkedList ..).

• ArrayList 初始化方式

//普通
ArrayList<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");

//双括号法
ArrayList<String> list = new ArrayList<String>() {{
    add("A");
    add("B");
    add("C");
}}

//java7提供了Arrays.asList，但是通过 asList 返回的 List ，一定不能进行 add 操作，否则会抛出异常
List<String> places = Arrays.asList("Buenos Aires", "Córdoba", "La Plata");
//转型为ArrayList就没有问题
ArrayList<String> places = new ArrayList<>(Arrays.asList("Buenos Aires", "Córdoba", "La Plata"));

//如果只有一个元素
List<Long> idList = Collections.singletonList(1001);

//guava框架
List<String> places = ImmutableList.of("Buenos Aires", "Córdoba", "La Plata");

//自定义工厂方法
public static ArrayList<String> createArrayList(String ... elements) {
    ArrayList<String> list = new ArrayList<String>(); 
    for (String element : elements) {
        list.add(element);
    }
    return list;
}

....

ArrayList<String> places = createArrayList("São Paulo", "Rio de Janeiro", "Brasília");

//创建n个相同的副本
ArrayList<Object> list = new ArrayList<Object>(Collections.nCopies(1000, new Object()));  

//stream风格
List<String> strings = Stream.of("foo", "bar", "baz").collect(toList());

• 线程安全
  List是非线程安全的，但只有在发生resize的时候才可能触发不安全的操作，因此，如果你的List初始容量足够大，是可以进行多线程操作的，当然，并发的场合还是推荐使用并发容器CopyOnWriteList

三 LinkedList篇

和ArrayList的一大区别在于没有实现RandomAccess接口，另外ArrayList 里是实现了 Iterator 类，然后用ListIterator扩展了Iterator类，而LinkedList里是只实现了ListIterator类，通过接口窄化间接实现Iterator功能，最后，LinkedList 的实现是基于Deque的，所以它可以窄化实现为Stack和Queue。

四 vector 篇

就是把ArrayList所有public方法加上synchronized

五 stack 篇

就是扩展了vector ，增加了push，pop，peep方法