jdk中list接口继承与collection(放置一组元素的容器，为set与list的父类接口)，iterable
list中使用比较多为arraylist,vector,linkedlist,stack(其实没有注意到stack是基于vector实现的)，，前面均为abstarctlist的继承实现，后者copyonwritearraylist为list,RandomAccess,cloneable,seriaizable（用于实现以复制方式保证的线程安全），接下来简略，简单的叙述一下各个数据类型怎么实现的，主要从基本数据类型和其中构建的算法 ? 1.abstractlist，这个抽象类，首先一如既往的基本实现了list接口的方法，没有什么大的表现 2.Arraylist内部存储数据使用数组形式，内部支持容器操作，排序（因为是数组存储，内部装换成Array，其实就是对array数组进行操作，具体要参考Array的源码），即具有数组特性的list.其他诸如扩容（2倍），添加，删除与map类似，不再阐述 针对几个操作复制，排序 在内部中实际进行操作的Array类，对Objetc[]进行管理，比如mao.toarray操作中实际上是把object[]导入到Array中调用toarray（）方法，而在Array类中调用实际处理的是system.arraycopy（native方法）效率非常高，也就是说将list转换成数组（实际上重新复制创建的新数组，并不是返回list内部保存的object[]引用） ? ??private?void?grow(int?minCapacity)?{ ????????//?overflow-conscious?code ????????int?oldCapacity?=?elementData.length; ????????int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1); ????????if?(newCapacity?-?minCapacity?<?0) ????????????newCapacity?=?minCapacity; ????????if?(newCapacity?-?MAX_ARRAY_SIZE?>?0) ????????????newCapacity?=?hugeCapacity(minCapacity); ????????//?minCapacity?is?usually?close?to?size,?so?this?is?a?win: ????????elementData?=?Arrays.copyOf(elementData,?newCapacity); ????} ? ??public?static?long[]?copyOf(long[]?original,?int?newLength)?{ ????????long[]?copy?=?new?long[newLength]; ????????System.arraycopy(original,?0,?copy,?0, ?????????????????????????Math.min(original.length,?newLength)); ????????return?copy; ????} ? ??public?static?native?void?arraycopy(Object?src,??int??srcPos, ????????????????????????????????????????Object?dest,?int?destPos, ????????????????????????????????????????int?length); 至于排序实现：在内部中Array.sort，其中自然用到了compator接口已经实现，但是arraylist是不能显示调用sort进行排序，所以需要实现导出array，来进行排序，或者使用collections根据对arraylist进行排序，返回结果依旧正确，网上有许多示例资料，前提是arraylist元素要实现compator接口，这种方式通常是实现自定义的排序方式，不然进行装饰操作的sort没有能力进行计算比较 A.Array.sort(arraylist.toarray())调用native sort进行默认排序 B.collections.sort(list<T entends Comparable>)进行自定义排序（也支持默认排序，两种方式其实都使用了Array,但是没有第一种方便） ? 3.Vector存储元素为Object[]?elementData,扩容方式是（1+factor）*capacity,随机访问速度快,实现线程安全的方式是同步机制synchronized，大体的实现和方法类别基本与arraylist差不多，其注意事项有如下（来源于jdk api），其中出现的迭代器快速失败需要非常注意，导致的原因为修改了原来的存储数据的数据结构，比如追加元素；其中有些数据类型，在取数据的时候也会修改数据类型，归于内部实现不一样，比如LinkedHashMap.get()，queue,stack就不可以在出现在迭代器模式下。Vectorclass="Apple-converted-space">?类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。但是，Vector?的大小可以根据需要增大或缩小，以适应创建?Vector?后进行添加或移除项的操作。
每个向量会试图通过维护?capacity?和?capacityIncrement?来优化存储管理。capacity?始终至少应与向量的大小相等；这个值通常比后者大些，因为随着将组件添加到向量中，其存储将按?capacityIncrement?的大小增加存储块。应用程序可以在插入大量组件前增加向量的容量；这样就减少了增加的重分配的量。
由 Vector 的 iterator 和 listIterator 方法所返回的迭代器是快速失败的：如果在迭代器创建后的任意时间从结构上修改了向量（通过迭代器自身的 remove 或 add 方法之外的任何其他方式），则迭代器将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就完全失败，而不是冒着在将来不确定的时间任意发生不确定行为的风险。Vector 的 elements 方法返回的 Enumeration?不是?快速失败的。?
?4.LinkedList的描叙（jdk api）,双向链表的构造（#1），以及对单个节点的实现处理（#2），从中可以看出具有高速度连续访问获取数据的优势，但是随即访问速度没有arraylist高效，此类实现?Deque?接口（本身取数据节点和增加数据节点就已经修改了原来的数据结构，没有类似于get()的读取数据但不修改数据结构），为?add、poll?提供先进先出队列操作，以及其他堆栈和双端队列操作。但是类似于toarray可以通过循环返回其object[]数组，至于linkedlist是双向列表，怎么进行get（）？从#3可以得出应该是对index作为循环次数从first开始追寻????}
#3? ???public?E?get(int?index)?{ ????????try?{ ????????????return?listIterator(index).next(); ????????}?catch?(NoSuchElementException?exc)?{ ????????????throw?new?IndexOutOfBoundsException("Index:?"+index); ????????} ????} ? ??/** ?????*?Returns?the?(non-null)?Node?at?the?specified?element?index. ?????*/ ????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; ????????} ????} ? ?5.Stack栈，顾名思义，先进后出的特性，基于vector实现，线程安全,按照JDK API的说法，是通过5个操作类对vector进行扩展得到的 允许将向量视为堆栈。它提供了通常的?push?和?pop?操作，以及取堆栈顶点的?peek?方法、测试堆栈是否为空的?empty?方法、在堆栈中查找项并确定到堆栈顶距离的?search?方法。? 如下： ??public?E?push(E?item)?{//入栈 ????????addElement(item); ????????return?item; ????} ?public?synchronized?E?pop()?{//出栈 ????????E???????obj; ????????int?????len?=?size(); ????????obj?=?peek(); ????????removeElementAt(len?-?1); ????????return?obj; ????} ? ?public?synchronized?E?peek()?{//检测栈顶部元素并返回，但不移除 ????????int?????len?=?size(); ????????if?(len?==?0) ????????????throw?new?EmptyStackException(); ????????return?elementAt(len?-?1); ????} ? ? ?public?boolean?empty()?{ ????????return?size()?==?0; ????} ??public?synchronized?int?search(Object?o) {//查找堆栈中对象序号 ????????int?i?=?lastIndexOf(o); ????????if?(i?>=?0)?{ ????????????return?size()?-?i; ????????} ????????return?-1; ????} ? 6.CopyOnwriteArrayList摘自jdk API，内部操作读取和增加通过vector的synchronized同步控制，至于数组的复制是使用ReentranLock进行控制monospace;">ArrayList的一个线程安全的变体，其中所有可变操作（add、set?等等）都是通过对底层数组进行一次新的复制来实现的，但并不是通过继承来实现的，却继承了abstractlist，。这一般需要很大的开销，但是当遍历操作的数量大大超过可变操作的数量时，这种方法可能比其他替代方法更?有效。在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时，它也很有用。“快照”风格的迭代器方法在创建迭代器时使用了对数组状态的引用。此数组在迭代器的生存期内不会更改，因此不可能发生冲突，并且迭代器保证不会抛出?ConcurrentModificationException。创建迭代器以后，迭代器就不会反映列表的添加、移除或者更改。在迭代器上进行的元素更改操作（remove、set?和?add）不受支持。这些方法将抛出?UnsupportedOperationException。
相关文章
