ArrayList和LinkedList

ArrayListArrayList实现RandomAccess、Cloneable、Serializable接口RandomAccess接口使ArrayList支持随机读取。下面是Collections中的一个简单应用示例：)返回Collections.indexedBinarySearch(list,key);否则返回Collections.iteratorBinarySearch(list,key);}在二分查找方法中，根据是否实现RandomAccess接口选择不同的遍历方式。ArrayList是List接口的一个实现类。底层是一个基于数组的存储结构，可以用来加载数据。数据存储在数组变量中。瞬态对象[]元素数据；//non-private简化嵌套类访问non-private，方便嵌套类访问transient是一个关键字，它的作用可以用一句话概括：在不需要序列化的属性前加上关键字被序列化，这个属性将不会被序列化。你可能觉得ArrayList可以序列化很奇怪，但是源码实现了java.io.Serializable接口。为什么数组变量需要用transient来定义？关于transient，文末会给出答案。当我们创建一个新的实例时，ArrayList默认会将数组的大小初始化为10。Size，List的大小应该由存储的数据量来决定。在源码中，真正的容量其实是用一个变量size表示的//ArrayList的大小（它包含的元素个数）.privateintsize;在源代码中，数据默认从数组的第一个索引开始存储。当我们添加数据时，ArrayList会将数据填充到上一个索引的后面，这样ArrayList中的数据是有序排列的。而且，由于ArrayList本身是基于数组存储的，所以在查询的时候，只需要根据索引下标找到对应的元素即可。查询性能非常高，这是我们非常喜欢ArrayList的最重要原因。不过，阵法的容量是一定的。如果要存储的数据大小超过了数组的大小，会不会出现数组越界的问题？关于这一点，我们不必担心。ArrayList已经为我们做了动态扩展。如果添加新数据后发现List的大小已经超过了数组的容量，则会添加一个1.5倍于原容量的新数组。然后将原数组的数据原封不动的复制到新数组中，再将新数组赋值给原数组对象即可完成。privatevoidgrow(intminCapacity){//溢出意识代码intoldCapacity=elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);如果(newCapacity-minCapacity<0)newCapacity=minCapacity;如果(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//minCapacity通常接近大小，所以这是一个胜利：elementData=Arrays.copyOf(elementData,newCapacity);}组的最大容量为Integer.MAX_VALUE（2,147,483,648），而-8只是为了避免一些机器内存溢出/***要分配的数组的最大大小。*一些虚拟机在数组中保留了一些头字。*尝试分配更大的数组可能会导致*OutOfMemoryError:RequestedarraysizeexceedsVMlimit*/privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;privatestaticinthugeCapacity(intminCapacity){if(minCapacity<0)//溢出抛出新的OutOfMemoryError()；返回（最小容量>MAX_ARRAY_SIZE）？Integer.MAX_VALUE:MAX_ARRAY_SIZE;}扩容后数组容量充足，可以正常添加数据。另外，ArrayList提供了一种支持指定索引添加的方法，即数据可以插入集合中，删除时索引下标相同。指定索引，然后复制下面的数据，并向前移动，这样原索引位置的数据就会被删除。通过index进行add和remove的方法底层使用了System.arraycopy方法publicvoidadd(intindex,Eelement){rangeCheckForAdd(index);确保容量内部（尺寸+1）；//递增modCount!!System.arraycopy(elementData,index,elementData,index+1,size-index);元素数据[索引]=元素；size++;}publicEremove(intindex){rangeCheck(index);模数++；EoldValue=elementData(index);intnumMoved=大小-索引-1;如果(numMoved>0)System.arraycopy(elementData,index+1,elementData,index,numMoved);元素数据[--大小]=空；//明确让GC完成它的工作returnoldValue;}并且System.arraycopy方法是一个本地方法publicstaticnativevoidarraycopy(Objectsrc,intsrcPos,Objectdest,intdestPos,intlength);这里插入一个知识点：java的拷贝操作分为浅拷贝和深拷贝，深拷贝可以拷贝对象的值和对象的内容，浅拷贝是对象引用的拷贝。System.arraycopy将对象放入二维数组或一维数组时，复制结果是一个一维引用变量传递给复制的一维数组。当副本被修改时，原始数组将受到影响。对于一个简单的一维数组，这种拷贝属性值传递，修改拷贝不会影响原值。这里不难发现，这种基于数组的查询虽然效率很高，但是在增删改数据的时候会非常消耗性能，因为每增减一个元素，对应索引后面的所有元素都会被移动，所以数据量小也没关系。但是要存储上万条数据会很吃力，所以如果是频繁增删改查的情况，不建议使用ArrayList。既然不推荐使用ArrayList，请问这种情况下还有其他的collection可用吗？当然有，这就是我们下面要说的LinkedListLinkedListLinkedList是基于双向链表的。它不需要指定初始容量。链表中的任意一个存储单元都可以通过前向或后向指针从前面或后面获取。存储单元。在LinkedList的源码中，其存储单元由一个内部类Node表示：privatestaticclassNode{Eitem;下一个节点；节点上一个；Node(Nodeprev,Eelement,Nodenext){this.item=element;这个.下一个=下一个；this.prev=prev;}}因为保存了前后节点的地址，所以LinkedList在增删数据时不需要像ArrayList那样整块移动数据，只需要引用指定索引位置前后的两个节点即可。删除数据也是一样的原理，只需要改变索引位置前后两个节点的指向地址即可。这样的链表结构使得LinkedList可以非常高效的进行数据的增删改查，在频繁增删改查的情况下可以很好的使用，但是也存在一些不足。虽然增删改数据很快，但是查询起来就不是那么好了。LinkedList是基于双向链表存储的。在查询索引位置对应的数据时，会先计算链表总长度一半的值，判断索引在这个值的左边。还是右边，然后决定从头节点开始遍历还是从尾节点开始遍历。Nodenode(intindex){//assertisElementIndex(index);if(index<(size>>1)){Nodex=first;for(inti=0;ix=最后一个；for(inti=size-1;i>index;i--)x=x.prev;返回x;}}虽然已经使用了二分法进行优化，但是还是有可能遍历链表的一半长度。如果数据量很大，这样的查询无疑会很慢。这也是LinkedList最郁闷的地方。你不能两者兼得。我们既要快速查，又要快速增删。这么好的事怎么会发生在我们身上呢？所以一般建议在增删改查多，查询少的情况下使用LinkedList。另外，LinkedList占用的内存也比较大。毕竟每个Node都维护着指向前后地址的节点。如果数据量很大，会占用大量的内存空间。从表面上看，LinkedList的Node存储结构似乎占用了更多的空间，但别忘了前面引入ArrayList扩容时，默认会将数组的容量扩容到原来的1.5倍。如果只增加一个元素，那么几乎有一半的原始数组空间会被浪费掉。如果原数组很大，那么这部分空间就会浪费很多。所以，如果数据量很大，数据是实时添加的，ArrayList占用的空间不一定比LinkedList小。这个答案比较谨慎，听起来更容易同意，但你认为这是完美的答案吗？还记得我前面提到的瞬态变量吗？它的作用已经说了，不想被序列化的对象可以用它来修饰，用transient修饰elementData就是我不想让elementData数组被序列化。你为什么这样做？这是因为在序列化ArrayList的时候，ArrayList中的elementData，也就是数组可能没有满。比如elementData有10个大小，但是我只用了其中的3个，那么需要把整个elementData序列化吗？？显然这是没有必要的，所以在ArrayList中重写了writeObject方法：s.defaultWriteObject();//写出大小作为与clone()行为兼容的容量s.writeInt(size);//以正确的顺序写出所有元素。for(inti=0;i