JDK list简单解析

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就不可以在出现在迭代器模式下。

Vector 类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。但是，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开始追寻

AbstractSequentialList：此类提供了 List 接口的骨干实现，从而最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作。对于随机访问数据（如数组），应该优先使用 AbstractList，而不是先使用此类，从某种意义上说，此类与在列表的列表迭代器上实现“随机访问”方法（get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)）的AbstractList 类相对立，而不是其他关系。

#1  transient Node<E> first;

    /**

     * Pointer to last node.

     * Invariant: (first == null && last == null) ||

     *            (last.next == null && last.item != null)

     */

    transient Node<E> last;

#2  private static class Node<E> {//明显是有前驱和后驱节点，以及相应的属性值，所以从可以看出linkedlist是至少具备双向链表的特性（双向链表具体请自修C）

        E item;

        Node<E> next;

        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {

            this.item = element;

            this.next = next;

            this.prev = prev;

        }

    }

#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进行控制

ArrayList的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的，但并不是通过继承来实现的，却继承了abstractlist，。这一般需要很大的开销，但是当遍历操作的数量大大超过可变操作的数量时，这种方法可能比其他替代方法更 有效。在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时，它也很有用。“快照”风格的迭代器方法在创建迭代器时使用了对数组状态的引用。此数组在迭代器的生存期内不会更改，因此不可能发生冲突，并且迭代器保证不会抛出 ConcurrentModificationException。创建迭代器以后，迭代器就不会反映列表的添加、移除或者更改。在迭代器上进行的元素更改操作（remove、set 和 add）不受支持。这些方法将抛出 UnsupportedOperationException。