集合类---List

一、ArrayList详解

1.继承关系

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

2.属性

//默认的数组长度

private static final int DEFAULT_CAPACITY = 10;

//存储list中元素的数组，transient关键字表示该对象在ArrayList序列化时不被序列化。

transient Object[] elementData;

//数组中实际元素的个数

private int size;

//数组的最大长度

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3.构造方法：

ArrayList的构造函数总共有三个：

（1）ArrayList()构造一个初始容量为 10 的空列表。

（2）ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

（3）ArrayList(int initialCapacity)构造一个具有指定初始容量的空列表。

所以如果调用List list = new ArrayList(10);会直接调用第三个构造函数。否则就需要扩容。

4.其他重要方法

1）add()添加元素：

     public boolean add(E e) {

         ensureCapacityInternal(size + 1);  // size为element数组的实际大小，若size+1<elementData.length,则不用动态扩容，否则需要将elementData进行动态扩容。

         elementData[size++] = e;

         return true;

     }

     private void ensureCapacityInternal(int minCapacity) {

         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

         }

         ensureExplicitCapacity(minCapacity);

     }

     private void ensureExplicitCapacity(int minCapacity) {

         modCount++;

         if (minCapacity - elementData.length > 0)

             grow(minCapacity);

     }

     //grow：elementData数组扩容

     private void grow(int minCapacity) {

         int oldCapacity = elementData.length;

     //每次增长newCapacity=oldCapacity*1.5，为原来的1.5倍

         int newCapacity = oldCapacity + (oldCapacity >> 1);

     //如果oldCapacity*1.5倍后，容量还是比minCapacity要小，则将newCapacity的值直接置为minCapacity

         if (newCapacity - minCapacity < 0)

             newCapacity = minCapacity;

     //如果增长的新长度大于了MAX_ARRAY_SIZE，则调用hugeCapacity来获取一个不大于Integer.MAX_VALUE的值。

         if (newCapacity - MAX_ARRAY_SIZE > 0)

             newCapacity = hugeCapacity(minCapacity);

     //重新申请一个newCapacity长度的数组空间，并把elementData数组中内容拷贝过去。

         elementData = Arrays.copyOf(elementData, newCapacity);

     }

     //hugeCapacity: elementData的最大容量

     private static int hugeCapacity(int minCapacity) {

         if (minCapacity < 0) // overflow

             throw new OutOfMemoryError();

     //当最小保证的容量minCapacity比MAX_ARRAY_SIZE还大时，返回Integer.MAX_VALUE；否则直接返回MAX_ARRAY_SIZE

         return (minCapacity > MAX_ARRAY_SIZE) ?

             Integer.MAX_VALUE :

             MAX_ARRAY_SIZE;

     }

2）add()在指定位置添加元素：

     public void add(int index, E element) {

         rangeCheckForAdd(index);

         ensureCapacityInternal(size + 1);  // 确保数组的长度>=size+1

     //将elementData中index到数组最后一个元素，整体向后移动一个位置，空出index这一个位置，将element填入

         System.arraycopy(elementData, index, elementData, index + 1, size - index);

         elementData[index] = element;

         size++;

     }

3）addAll()：

ArrayList内部是以数组的形式实现的，直接数组后面加数组，并增长数组长度。

     public boolean addAll(int index, Collection<? extends E> c) {

         rangeCheckForAdd(index);

         Object[] a = c.toArray();

         int numNew = a.length;

     //确保数组能容下添加的所有元素，可能进行动态扩容

         ensureCapacityInternal(size + numNew);

          //计算从Index到处数组最后一个元素需要移动的元素的个数

         int numMoved = size - index;

         if (numMoved > 0)

     //直接采用System.arraycopy将elementData数组中从index开始到最后一个元素位置这一段数据，移动到index+numNew位置

             System.arraycopy(elementData, index, elementData, index + numNew, numMoved);

     //若index等于size，则直接在原数组后面添加

         System.arraycopy(a, 0, elementData, index, numNew);

         size += numNew;

         return numNew != 0;

     }

addAll()是调用System.arraycopy()函数来进行添加list集的，以复制的方式进行。System.arraycopy()源码如下：

   /*

     * 源数组，也就是要x.addAll(y)中的y

     * @param      src      the source array.

     * 源数组开始复制的位置，也就是y从第几位开始添加进x

     * @param      srcPos   starting position in the source array.

     * 目的数组，也就是x

     * @param      dest     the destination array.

     * 从目的数组的哪个位置开始添加，也就是从x的第几位开始添加进y

     * @param      destPos  starting position in the destination data.

     * 要复制的数组长度，也就是y要添加进x的数据个数

     * @param      length   the number of array elements to be copied.

     */

    public static native void arraycopy(Object src,  int  srcPos,

                                        Object dest, int destPos,

                                        int length);

从上面可以看出，x.addAll(y)函数是在x集合的基础上再其里面加入y集合，而不是用y将x进行覆盖。

数组copy方法效率比较：

System.arraycopy > clone > Arrays.copyOf > for循环

4）remove一个区间的数值：

     //是一个前闭后开的区间，就是toIndex位置的元素不被移除，fromIndex位置元素被移除

     protected void removeRange(int fromIndex, int toIndex) {

         modCount++;

         //需要移动的元素的个数=toIndex到最后一个元素位置

         int numMoved = size - toIndex;

         System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);

         // clear to let GC do its work

         int newSize = size - (toIndex-fromIndex);

         for (int i = newSize; i < size; i++) {

             elementData[i] = null;//设置为null，让gc有机会回收

         }

         size = newSize;

     }

二、LinkedList详解

1.继承关系

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

（1）继承自AbstractSequentialList抽象类(该类继承自AbstractList抽象类)；实现了List、Deque、Cloneable和Serializable接口，对随机get、set、remove等做了基本实现。
（2）AbstractSequentialList抽象类：定义了具体方法get()、set()、add()、remove()、addAll()(提供对list的随机访问功能)和抽象方法abstract ListIterator<E> listIterator(int index)。
（3）Deque：双向队列，可以用作栈。继承自Queue接口，Queue接口又继承自Collection接口。
（4）实现方式是采用双向链表的形式。
（5）LinkedList可以被当作堆栈(实现了Deque接口)、队列或双端队列进行操作。

2.属性

transient int size = 0;//包含元素的个数

transient Node<E> first;//指向链表的第一个元素的指针

transient Node<E> last;//指向链表的最后一个元素的指针

3.数据结构

     private static class Node<E> {

         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;

         }

     }

4.方法

（1）addFirst():链表头部添加一个新元素，调用私有方法linkFirst实现

     public void addFirst(E e) {

         linkFirst(e);

     }

  //linkFirst:在链表首添加一个元素

  private void linkFirst(E e) {

         final Node<E> f = first;

         //new Node<>(指向前一个节点的指针，数据，指向后一个节点的指针)

         final Node<E> newNode = new Node<>(null, e, f);

         first = newNode;

         //链表原先为空，现在添加了一个节点，last指针和first指针都指向该节点

         if (f == null)

             last = newNode;

         //原先的首节点的prev指针指向新节点

         else

             f.prev = newNode;

         size++;

         //修改次数+1

         modCount++;

     }

（2）addLast、add：在链表尾部添加一个新节点，调用私有方法linkLast实现

     public void addLast(E e) {

         linkLast(e);

     }

     //类似的还有add方法也是调用linkLast实现

     public boolean add(E e) {

         linkLast(e);

         return true;

     }

     //linkLast：在链表的最后添加一个节点

     void linkLast(E e) {

         final Node<E> l = last;

         //新节点的prev指针指向原先的最后一个节点

         final Node<E> newNode = new Node<>(l, e, null);

         //修改last指针指向新的最后一个节点

         last = newNode;

         if (l == null)

             first = newNode;

         //原先的最后一个节点的next指针指向新节点

         else

             l.next = newNode;

         size++;

         modCount++;

     }

（3）removeFirst:删除链表的头节点

     public E removeFirst() {

         final Node<E> f = first;

         if (f == null)

             throw new NoSuchElementException();

         return unlinkFirst(f);

     }

 //unlinkFirst:删除链表中第一个节点，并取消链接(prev和next)，私有方法，供removeLast()调用

 //使用前提：f!=null，否则会抛出异常；并且f是链表的第一个节点，否则结果会删除链表首节点到f位置的所有节点(first=f.next)

     private E unlinkFirst(Node<E> f) {

         // assert f == first && f != null;

         final E element = f.item;

         final Node<E> next = f.next;

         f.item = null;

         f.next = null; // help GC

         first = next;

         //链表中已经没有节点了

         if (next == null)

             last = null;

         else

             next.prev = null;

         size--;

         modCount++;

         return element;

     }

（4）removeLast：删除链表的最后一个节点

     public E removeLast() {

         final Node<E> l = last;

         if (l == null)

             throw new NoSuchElementException();

         return unlinkLast(l);

     }

 //unlinkLast:删除链表的最后一个节点，并删除链接，私有方法，供removeFirst方法调用

 //使用前提：f!=null,否则会抛出异常；并且l是链表的最后一个节点，否则会删除f到链表尾部的所有节点(last=l.prev)

 private E unlinkLast(Node<E> l) {

         // assert l == last && l != null;

         final E element = l.item;

         final Node<E> prev = l.prev;

         l.item = null;

         l.prev = null; // help GC

         last = prev;

         //该链表中已经没有节点了

         if (prev == null)

             first = null;

         else

             prev.next = null;

         size--;

         modCount++;

         return element;

     }

三、Vector详解

1.继承关系

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

（1）继承自AbstractList类
（2）List接口：继承自Collection接口，同时自己也定义了一系列索引访问功能。
（3）RandomAccess：空接口，实现该接口代表该类拥有随机访问list对象的能力。
（4）Cloneable:空接口，实现该接口，重写Object的clone方法，否则会抛出异常。调用super.clone()实现对象的复制，如果对象中有引用，可以在super.clone后面进行处理。
（5）java.io.Serializable：空接口，实现该接口代表该类可序列化

2.属性

protected Object[] elementData;//内部还是采用一个数组保存list中的元素

protected int elementCount;//数组实际包含的元素的个数

protected int capacityIncrement;//每次增长的大小(不是增长率)，当值小于等于0时，容量每次增长的容量为elementData.length(即倍增原数组的大小)

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //数组的最大容量

3.方法

(1)构造方法，如果不提供初始容量，则默认数组大小为10

     public Vector() {

         this(10);

     }

(2)同步方法：trimToSize,将数组的容量修改成实际容量的大小，即令elementData.length=elementCount

     public synchronized void trimToSize() {

         modCount++;

         int oldCapacity = elementData.length;

         if (elementCount < oldCapacity) {

             elementData = Arrays.copyOf(elementData, elementCount);

         }

     }

(3)同步方法:ensureCapacity,保证数组的最小容量

     public synchronized void ensureCapacity(int minCapacity) {

         if (minCapacity > 0) {

             modCount++;

             ensureCapacityHelper(minCapacity);

         }

     }

     //调用了ensureCapacityHelper：

     private void ensureCapacityHelper(int minCapacity) {

         // overflow-conscious code

         if (minCapacity - elementData.length > 0)

             grow(minCapacity);

     }

     //调用了grow:

     private void grow(int minCapacity) {

         // overflow-conscious code

         int oldCapacity = elementData.length;

         //如果capacityIncrement<0,则newCapacity=oldCapacity+oldCapacity；

         //否则则newCapacity=oldCapacity+capacityIncrement；

         int newCapacity = oldCapacity + ((capacityIncrement > 0) ?

                                          capacityIncrement : oldCapacity);

         //如果增长后仍不能保证满足minCapacity，则令newCapacity = minCapacity

         if (newCapacity - minCapacity < 0)

             newCapacity = minCapacity;

         //若增长后的大小大于允许的最大长度，则调用hugeCapacity

         if (newCapacity - MAX_ARRAY_SIZE > 0)

             newCapacity = hugeCapacity(minCapacity);

         //调用Arrays.copyof方法将elementData拷贝到一个容量为newCapacity的数组中。

         //Arrays.copyOf(elementData, newCapacity)实际上是通过System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));来实现的

         elementData = Arrays.copyOf(elementData, newCapacity);

     }

     //调用了hugeCapacity

     private static int hugeCapacity(int minCapacity) {

         if (minCapacity < 0) // overflow

             throw new OutOfMemoryError();

         //MAX_ARRAY_SIZE=Integer.MAX_VALUE-8

         return (minCapacity > MAX_ARRAY_SIZE) ?

             Integer.MAX_VALUE :

             MAX_ARRAY_SIZE;

     }

(4)同步方法：setSize，将elementData.length设置为newSize

     public synchronized void setSize(int newSize) {

         modCount++;

         if (newSize > elementCount) {

         //若newSize<elementData.length,则不用扩容，否则需要扩容

             ensureCapacityHelper(newSize);

         } else {

         //若newSize<elementData的实际大小(elementCount),则将newSize及其后面的数组都置为空

             for (int i = newSize ; i < elementCount ; i++) {

                 elementData[i] = null;

             }

         }

         elementCount = newSize;

     }

(5)同步方法:capacity,返回数组的大小；size，返回数组包含的元素的个数；isEmpty，判断数组是否没有元素

     public synchronized int capacity() {

         return elementData.length;

     }

     public synchronized int size() {

         return elementCount;

     }

     public synchronized boolean isEmpty() {

         return elementCount == 0;

     }

(6)同步方法:删除index处的元素

     public synchronized void removeElementAt(int index) {

         modCount++;

         if (index >= elementCount) {

             throw new ArrayIndexOutOfBoundsException(index + " >= " +

                                                      elementCount);

         }

         else if (index < 0) {

             throw new ArrayIndexOutOfBoundsException(index);

         }

         int j = elementCount - index - 1;

         if (j > 0) {

         //将elementData从index+1到elementCount为止的元素向前移动一个位置，覆盖Index处的元素

             System.arraycopy(elementData, index + 1, elementData, index, j);

         }

         elementCount--;

         elementData[elementCount] = null; /* to let gc do its work */

     }

     //remove也是删除，但是没有判断index是否小于0

     public synchronized E remove(int index) {

         modCount++;

         if (index >= elementCount)

             throw new ArrayIndexOutOfBoundsException(index);

         E oldValue = elementData(index);

         int numMoved = elementCount - index - 1;

         if (numMoved > 0)

             System.arraycopy(elementData, index+1, elementData, index,

                              numMoved);

         elementData[--elementCount] = null; // Let gc do its work

         return oldValue;

     }

(7)同步方法:insertElementAt,在index处插入obj

     public synchronized void insertElementAt(E obj, int index) {

         modCount++;

         if (index > elementCount) {

             throw new ArrayIndexOutOfBoundsException(index

                                                      + " > " + elementCount);

         }

         //先保证容量大于elementCount+1

         ensureCapacityHelper(elementCount + 1);

         //将elementData数组中index到elementCount之间的元素向后移动一位，给Index处空出位置

         System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);

         elementData[index] = obj;

         elementCount++;

     }

四、Stack详解

Stack继承于Vector，在其基础上实现了Stack所要求的后进先出(LIFO)的弹出与压入操作，其提供了push、pop、peek三个主要的方法：

push操作通过调用Vector中的addElement来完成；

pop操作通过调用peek来获取元素，并同时删除数组中的最后一个元素；

peek操作通过获取当前Object数组的大小，并获取数组上的最后一个元素。

ArrayList, LinkedList和Vector区别：

1.实现方式：

ArrayList和Vector采用数组按顺序存储元素，默认初始容量是10。

LinkedList基于双向循环链表实现（含有头结点）。

2.线程安全性

Vector线程安全，效率低，开销大。

ArrayList和LinkedList非线程安全。

3.扩容机制

ArrayList扩容为原来的1.5倍。不可以设置容量增量。

Vector扩容为原来容量+容量增量的2倍。可以设置容量增量。

4.增删改查效率

在集合末尾增加、删除元素，修改和查询时用ArrayList和Vector快。

在指定位置插入、删除元素，LinkedList快。

巴特西

集合类---List

最新文章

热门文章