List的架构

• List继承自Collection的接口,是一个有序队列的元素集合,每个元素都可通过下标索引获取。

• AbstractList是一个抽象类,继承了AbstractCollection,AbstractCollection实现了List中的绝大部分函数,为List的实现类提供了便利。

• List的基本实现主要是ArrayList、LinkedList和Vector。

ArrayList

• 底层基于数组实现,可将其视为一个可动态调整大小的数组。

• 查找/更新元素基于下标快速实现,时间复杂为O(1)。

• 添加/删除操作时:如果操作集合头部则剩下所有元素都需要移动位置,此时时间复杂度为O(n);如果操作集合尾部仅需一次操作,此时时间复杂度为O(1);由于概率得知每次操作时平均需要进行n/2次操作,所以时间复杂度为O(n/2)省略常数1/2,所以添加/删除操作的时间复杂度就为O(n)。

LinkedList

• 底层通过双向链表实现。

• 查找/更新操作时:如果操作集合头部或者尾部仅需一次操作,此时时间复杂度为O(1);如果操作集合中间位置则需要循环遍历n/2次;所以查找/更新操作的时间复杂度就为O(n)。

• 添加/删除操作时:需要先定位到元素再进行操作,所以时间复杂度与查找/更新一致为O(n)。

Vector

• 与ArrayList基本相同,通过数组实现。

• 通过synchronize关键字修饰方法来实现线程安全。

• 默认增长策略是2倍,可自定义增长因子(ArrayList是1.5倍,不可自定义)

List的源码解析

publicinterfaceList<E>extendsCollection<E>{/**返回当前集合中元素的数量;如果集合中包含的元素数量大于Integer.MAX_VALUE则直接返回Integer.MAX_VALUE**/intsize();/**返回当前集合是否不包含任何元素**/booleanisEmpty();/**返回一个包含当前集合中所有元素的Object数组**/Object[]toArray();/**返回一个包含当前集合中所有元素的指定类型T数组**/<T>T[]toArray(T[]a);/**返回当前集合是否包含指定的元素o**/booleancontains(Objecto);/**返回当前集合是否包含指定集合c中的所有元素**/booleancontainsAll(Collection<?>c);/**往当前集合中添加元素e**/booleanadd(Ee);/**往当前集合中指定位置index添加元素e**/voidadd(intindex,Ee);/**添加指定集合c中的所有元素到当前集合**/booleanaddAll(Collection<?extendsE>c);/**从当前集合指定位置index开始插入指定集合c中的所有元素**/booleanaddAll(intindex,Collection<?extendsE>c);/**从当前集合中移除指定元素e,如果集合中包含多个相同元素,则移除第一个**/booleanremove(Objecte);/**移除当前集合中指定位置index的元素**/Eremove(intindex);/**从当前集合中移除指定集合c中包含的所有元素**/booleanremoveAll(Collection<?>c);/**只保留当前集合与指定集合c中都存在的元素**/booleanretainAll(Collection<?>c);/**移除当前集合中所有的元素**/voidclear();/**将集合中每个元素替换为该元素运算的结果;JDK1.8新增方法　**/defaultvoidreplaceAll(UnaryOperator<E>operator){Objects.requireNonNull(operator);finalListIterator<E>li=this.listIterator();while(li.hasNext()){li.set(operator.apply(li.next()));}}/**根据给定的排序规则排序集合;JDK1.8新增方法**/defaultvoidsort(Comparator<?superE>c){Object[]a=this.toArray();Arrays.sort(a,(Comparator)c);ListIterator<E>i=this.listIterator();for(Objecte:a){i.next();i.set((E)e);}}/**返回当前集合中指定元素的下标**/Eget(intindex);/**用指定的元素element替换当前集合中指定位置index中的元素**/Eset(intindex,Eelement);/**返回当前集合中第一次出现指定元素o的下标位置;如果集合中不包含这个元素,则返回-1**/intindexOf(Objecto);/**返回当前集合中最后一次出现指定元素o的下标位置;如果集合中不包含这个元素,则返回-1**/intlastIndexOf(Objecto);/**返回当前集合的迭代器**/Iterator<E>iterator();/**返回当前集合的集合迭代器**/ListIterator<E>listIterator();/**返回当前集合指定起始位置index的集合迭代器**/ListIterator<E>listIterator(intindex);/**返回当前集合指定起始结束位置组成的新的集合**/List<E>subList(intfromIndex,inttoIndex);/**返回一个可分割迭代器,增加并行处理能力;继承自Iterable接口;JDK1.8新增的方法**/@OverridedefaultSpliterator<E>spliterator(){returnSpliterators.spliterator(this,Spliterator.ORDERED);}}