每天一杯下(代)午(码)茶(片)!
在Java集合深入理解：Collection中我们熟悉了Java集合框架的基本概念和优点，也了解了根接口之一的Collection，这篇文章来加深Collection的子接口之一List的熟悉。List接口一个List是一个元素有序的、可以重复、可以为null的集合（有时候我们也叫它“序列”）。Java集合框架中最常使用的几种List实现类是ArrayList，LinkedList和Vector。在各种List中，最好的做法是以ArrayList作为默认选择。当插入、删除频繁时，使用LinkedList，Vector总是比ArrayList慢，所以要尽量避免使用它，具体实现后续文章介绍。为什么List中的元素“有序”、“可以重复”呢?首先，List的数据结构就是一个序列，存储内容时直接在内存中开辟一块连续的空间，然后将空间地址与索引对应。其次根据官方文档：Theuserofthisinterfacehasprecisecontroloverwhereinthelisteachelementisinserted.Theusercanaccesselementsbytheirintegerindex(positioninthelist),andsearchforelementsinthelist.
可以看到，List接口的实现类在实现插入元素时，都会根据索引进行排列。比如ArrayList，本质是一个数组：LinkedList,双向链表：由于List的元素在存储时互不干扰，没有什么依赖关系，自然可以重复（这点与Set有很大区别）。List接口定义的方法List中除了继承Collection的一些方法，还提供以下操作：位置相关：List和数组一样，都是从0开始，我们可以根据元素在list中的位置进行操作，比如说get,set,add,addAll,remove;
搜索：从list中查找某个对象的位置，比如indexOf,lastIndexOf;
迭代：使用Iterator的拓展版迭代器ListIterator进行迭代操作;
范围性操作：使用subList方法对list进行任意范围的操作。
Collection中提供的一些方法就不介绍了，不熟悉的可以去看一下。集合的操作remove(Object)
用于删除list中头回出现的指定对象；
add(E),addAll(Collection?extendsE)
注意：上述使用了ArrayList的转换构造函数:
publicArrayList(Collection
用于把新元素添加到list的尾部，下面这段语句使得list3等于list1与list2组合起来的内容：
Listlist3=newArrayList(list1);list3.addAll(list2);
Object的equlas()方法默认和==一样，比较的是地址是否相等。publicbooleanequals(Objecto){returnthis==o;}
因此和Set，Map一样，List中如果想要根据两个对象的内容而不是地址比较是否相等时，需要重写equals()和hashCode()方法。remove(),contains(),indexOf()等等方法都需要依赖它们：
Overridepublicbooleancontains(Objectobject){Object[]a=array;ints=size;if(object!=null){for(inti=0;is;i++){//需要重载Object默认的equalsif(object.equals(a[i])){returntrue;}}}else{for(inti=0;is;i++){if(a[i]==null){returntrue;}}}returnfalse;}OverridepublicintindexOf(Objectobject){Object[]a=array;ints=size;if(object!=null){for(inti=0;is;i++){if(object.equals(a[i])){returni;}}}else{for(inti=0;is;i++){if(a[i]==null){returni;}}}return-1;}两个List对象的所有位置上元素都一样才能相等。
位置访问，搜索基础的位置访问操作方法有：
get,set,add,remove
set,remove方法返回的是被覆盖或者被删除的元素；
indexOf,lastIndexOf
返回指定元素在list中的首次出现/最后一次出现的位置（获取lastIndexOf是通过倒序遍历查找）;
addAll(int,Collection)
在特定位置插入指定集合的所有元素。这些元素按照迭代器Iterator返回的先后顺序进行插入；
下面是一个简单的List中的元素交换方法：publicstaticEvoidswap(ListEa,inti,intj){Etmp=a.get(i);a.set(i,a.get(j));a.set(j,tmp);}
不同的是它是多态的，允许任何List的子类使用。Collections中的shuffle就有用到和下面这种相似的交换方法：
publicstaticvoidshuffle(List?list,Randomrnd){for(inti=list.size();i1;i--)swap(list,i-1,rnd.nextInt(i));}
这种算法使用指定的随机算法，从后往前重复的进行交换。和一些其他底层shuffle算法不同，这个算法更加公平（随机方法够随机的话，所有元素的被抽到的概率一样），同时够快（只要list.size()-1）次交换。
局部范围操作List.subList(intfromIndex,inttoIndex)方法返回List在fromIndex与toIndex范围内的子集。注意是左闭右开，[fromIndex,toIndex)。
注意！List.subList方法并没有像我们想的那样：创建一个新的List，然后把旧List的指定范围子元素拷贝进新List，根！本！不！是！subList返回的扔是List原来的引用，只不过把开始位置offset和size改了下，见List.subList()在AbstractList抽象类中的实现：
publicListEsubList(intstart,intend){if(start=0end=size()){if(start=end){if(thisinstanceofRandomAccess){returnnewSubAbstractListRandomAccessE(this,start,end);}returnnewSubAbstractListE(this,start,end);}thrownewIllegalArgumentException();}thrownewIndexOutOfBoundsException();}
SubAbstractListRandomAccess最终也是继承SubAbstractList,直接看SubAbstractList：
SubAbstractList(AbstractListElist,intstart,intend){fullList=list;modCount=fullList.modCount;offset=start;size=end-start;}
可以看到，的确是保持原来的引用。
所以，重点来了！由于subList持有List同一个引用，所以对subList进行的操作也会影响到原有List，举个栗子：
你猜运行结果是什么？
验证了上述重点。
所以，我们可以使用subList对List进行范围操作，比如下面的代码，一句话实现了删除shixinList部分元素的操作：shixinList.subList(fromIndex,toIndex).clear();
还可以查找某元素在局部范围内的位置：
inti=list.subList(fromIndex,toIndex).indexOf(o);intj=list.subList(fromIndex,toIndex).lastIndexOf(o);List与Array区别？List在很多方面跟Array数组感觉很相似，尤其是ArrayList，那List和数组究竟哪个更好呢？
相似之处：
都可以表示一组同类型的对象
都使用下标进行索引
不同之处：
数组可以存任何类型元素
List不可以存基本数据类型，必须要包装
数组容量固定不可改变；List容量可动态增长
数组效率高;List由于要维护额外内容，效率相对低一些
容量固定时优先使用数组，容纳类型更多，更高效。在容量不确定的情景下，List更有优势，看下ArrayList和LinkedList如何实现容量动态增长：ArrayList的扩容机制:publicbooleanadd(Eobject){Object[]a=array;ints=size;//当放满时，扩容if(s==a.length){//MIN_CAPACITY_INCREMENT为常量，12Object[]newArray=newObject[s+(s(MIN_CAPACITY_INCREMENT/2)?MIN_CAPACITY_INCREMENT:s1)];System.arraycopy(a,0,newArray,0,s);array=a=newArray;}a[s]=object;size=s+1;modCount++;returntrue;}可以看到：
当ArrayList的元素个数小于6时，容量达到最大时，元素容量会扩增12；
反之，增加当前元素个数的一半。
LinkedList的扩容机制：publicbooleanadd(Eobject){returnaddLastImpl(object);}privatebooleanaddLastImpl(Eobject){LinkEoldLast=voidLink.previous;LinkEnewLink=newLinkE(object,oldLast,voidLink);voidLink.previous=newLink;oldLast.next=newLink;size++;modCount++;returntrue;}可以看到，没！有！扩容机制！这是由于LinedList实际上是一个双向链表，不存在元素个数限制，使劲加就行了。
transientLinkEvoidLink;privatestaticfinalclassLinkET{ETdata;LinkETprevious,next;Link(ETo,LinkETp,LinkETn){data=o;previous=p;next=n;}}List与Array之间的转换在List中有两个转换成数组的方法：
Object[]toArray()
返回一个包含List中所有元素的数组；
T[]toArray(T[]array)
作用同上，不同的是当参数array的长度比List的元素大时，会使用参数array保存List中的元素；否则会创建一个新的数组存放List中的所有元素；
ArrayList中的实现：publicObject[]toArray(){ints=size;Object[]result=newObject[s];//这里的array就是ArrayList的底层实现，直接拷贝//System.arraycopy是底层方法，效率很高System.arraycopy(array,0,result,0,s);returnresult;}publicTT[]toArray(T[]contents){ints=size;//先判断参数能不能放下这么多元素if(contents.lengths){//放不下就创建个新数组
SuppressWarnings("unchecked")T[]newArray=(T[])Array.newInstance(contents.getClass().getComponentType(),s);contents=newArray;}System.arraycopy(this.array,0,contents,0,s);if(contents.lengths){contents[s]=null;}returncontents;}LinkedList的实现：publicObject[]toArray(){intindex=0;Object[]contents=newObject[size];LinkElink=voidLink.next;while(link!=voidLink){//挨个赋值，效率不如ArrayListcontents[index++]=link.data;link=link.next;}returncontents;}
OverrideSuppressWarnings("unchecked")publicTT[]toArray(T[]contents){intindex=0;if(sizecontents.length){Class?ct=contents.getClass().getComponentType();contents=(T[])Array.newInstance(ct,size);}LinkElink=voidLink.next;while(link!=voidLink){//还是比ArrayList慢contents[index++]=(T)link.data;link=link.next;}if(indexcontents.length){contents[index]=null;}returncontents;}数组工具类Arrays提供了数组转成List的方法asList:SafeVarargspublicstaticTListTasList(T...array){returnnewArrayListT(array);}使用的是Arrays内部创建的ArrayList的转换构造函数：
privatefinalE[]a;ArrayList(E[]storage){if(storage==null){thrownewNullPointerException("storage==null");}//直接复制a=storage;}迭代器Iterator,ListIteratorList继承了Collection的iterator()方法，可以获取Iterator，使用它可以进行向后遍历。在此基础上，List还可以通过listIterator(),listIterator(intlocation)方法（后者指定了游标的位置）获取更强大的迭代器ListIterator。使用ListIterator可以对List进行向前、向后双向遍历，同时还允许进行add,set,remove等操作。List的实现类中许多方法都使用了ListIterator，比如List.indexOf()方法的一种实现：
publicintindexOf(Ee){for(ListIteratorEit=listIterator();it.hasNext();)if(e==null?it.next()==null:e.equals(it.next()))returnit.previousIndex();//Elementnotfoundreturn-1;}ListIterator提供了add,set,remove操作，他们都是对迭代器刚通过next(),previous()方法迭代的元素进行操作。下面这个栗子中，List通过结合ListIterator使用，可以实现一个多态的方法，对所有List的实现类都适用：
publicstaticEvoidreplace(ListElist,Eval,EnewVal){for(ListIteratorEit=list.listIterator();it.hasNext();)if(val==null?it.next()==null:val.equals(it.next()))it.set(newVal);}List的相关算法：集合的工具类Collections中包含很多List的相关操作算法：
sort，归并排序
shuffle，随机打乱
reverse，反转元素顺序
swap，交换
binarySearch，二分查找
……
具体实现我们后续介绍，感谢治疗白癜风那最好北京看白癜风病最好的医院