集合类---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()添加元素：

 1     public boolean add(E e) {
 2         ensureCapacityInternal(size + 1);  // size为element数组的实际大小，若size+1<elementData.length,则不用动态扩容，否则需要将elementData进行动态扩容。
 3         elementData[size++] = e;
 4         return true;
 5     }
 6     private void ensureCapacityInternal(int minCapacity) {
 7         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 8             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 9         }
10  
11         ensureExplicitCapacity(minCapacity);
12     }
13  
14     private void ensureExplicitCapacity(int minCapacity) {
15         modCount++;
16  
17         if (minCapacity - elementData.length > 0)
18             grow(minCapacity);
19     }
20     //grow：elementData数组扩容
21     private void grow(int minCapacity) {
22         int oldCapacity = elementData.length;
23     //每次增长newCapacity=oldCapacity*1.5，为原来的1.5倍
24         int newCapacity = oldCapacity + (oldCapacity >> 1);
25     //如果oldCapacity*1.5倍后，容量还是比minCapacity要小，则将newCapacity的值直接置为minCapacity
26         if (newCapacity - minCapacity < 0)
27             newCapacity = minCapacity;
28     //如果增长的新长度大于了MAX_ARRAY_SIZE，则调用hugeCapacity来获取一个不大于Integer.MAX_VALUE的值。
29         if (newCapacity - MAX_ARRAY_SIZE > 0)
30             newCapacity = hugeCapacity(minCapacity);
31     //重新申请一个newCapacity长度的数组空间，并把elementData数组中内容拷贝过去。
32         elementData = Arrays.copyOf(elementData, newCapacity);
33     }
34     //hugeCapacity: elementData的最大容量
35     private static int hugeCapacity(int minCapacity) {
36         if (minCapacity < 0) // overflow
37             throw new OutOfMemoryError();
38     //当最小保证的容量minCapacity比MAX_ARRAY_SIZE还大时，返回Integer.MAX_VALUE；否则直接返回MAX_ARRAY_SIZE
39         return (minCapacity > MAX_ARRAY_SIZE) ?
40             Integer.MAX_VALUE :
41             MAX_ARRAY_SIZE;
42     }
View Code

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

1     public void add(int index, E element) {
2         rangeCheckForAdd(index);
3  
4         ensureCapacityInternal(size + 1);  // 确保数组的长度>=size+1
5     //将elementData中index到数组最后一个元素，整体向后移动一个位置，空出index这一个位置，将element填入
6         System.arraycopy(elementData, index, elementData, index + 1, size - index);
7         elementData[index] = element;
8         size++;
9     }
View Code

3）addAll()：

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

 1     public boolean addAll(int index, Collection<? extends E> c) {
 2         rangeCheckForAdd(index);
 3  
 4         Object[] a = c.toArray();
 5         int numNew = a.length;
 6     //确保数组能容下添加的所有元素，可能进行动态扩容
 7         ensureCapacityInternal(size + numNew);  
 8          //计算从Index到处数组最后一个元素需要移动的元素的个数
 9         int numMoved = size - index;
10         if (numMoved > 0)
11     //直接采用System.arraycopy将elementData数组中从index开始到最后一个元素位置这一段数据，移动到index+numNew位置
12             System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
13     //若index等于size，则直接在原数组后面添加
14         System.arraycopy(a, 0, elementData, index, numNew);
15         size += numNew;
16         return numNew != 0;
17     }
View Code

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一个区间的数值：

 1     //是一个前闭后开的区间，就是toIndex位置的元素不被移除，fromIndex位置元素被移除
 2     protected void removeRange(int fromIndex, int toIndex) {
 3         modCount++;
 4         //需要移动的元素的个数=toIndex到最后一个元素位置
 5         int numMoved = size - toIndex;
 6         System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
 7  
 8         // clear to let GC do its work
 9         int newSize = size - (toIndex-fromIndex);
10         for (int i = newSize; i < size; i++) {
11             elementData[i] = null;//设置为null，让gc有机会回收
12         }
13         size = newSize;
14     }
View Code

二、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.数据结构

 1     private static class Node<E> {
 2         E item;
 3         Node<E> next;
 4         Node<E> prev;
 5  
 6         Node(Node<E> prev, E element, Node<E> next) {
 7             this.item = element;
 8             this.next = next;
 9             this.prev = prev;
10         }
11     }
View Code

4.方法

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

 1     public void addFirst(E e) {
 2         linkFirst(e);
 3     }
 4  //linkFirst:在链表首添加一个元素
 5  private void linkFirst(E e) {
 6         final Node<E> f = first;
 7         //new Node<>(指向前一个节点的指针，数据，指向后一个节点的指针)
 8         final Node<E> newNode = new Node<>(null, e, f);
 9         first = newNode;
10         //链表原先为空，现在添加了一个节点，last指针和first指针都指向该节点
11         if (f == null)
12             last = newNode;
13         //原先的首节点的prev指针指向新节点
14         else
15             f.prev = newNode;
16         size++;
17         //修改次数+1
18         modCount++;
19     }
View Code

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

 1     public void addLast(E e) {
 2         linkLast(e);
 3     }
 4     //类似的还有add方法也是调用linkLast实现
 5     public boolean add(E e) {
 6         linkLast(e);
 7         return true;
 8     }
 9     //linkLast：在链表的最后添加一个节点
10     void linkLast(E e) {
11         final Node<E> l = last;
12         //新节点的prev指针指向原先的最后一个节点
13         final Node<E> newNode = new Node<>(l, e, null);
14         //修改last指针指向新的最后一个节点
15         last = newNode;
16         if (l == null)
17             first = newNode;
18         //原先的最后一个节点的next指针指向新节点
19         else
20             l.next = newNode;
21         size++;
22         modCount++;
23     }
View Code

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

 1     public E removeFirst() {
 2         final Node<E> f = first;
 3         if (f == null)
 4             throw new NoSuchElementException();
 5         return unlinkFirst(f);
 6     }
 7 //unlinkFirst:删除链表中第一个节点，并取消链接(prev和next)，私有方法，供removeLast()调用
 8 //使用前提：f!=null，否则会抛出异常；并且f是链表的第一个节点，否则结果会删除链表首节点到f位置的所有节点(first=f.next)
 9     private E unlinkFirst(Node<E> f) {
10         // assert f == first && f != null;
11         final E element = f.item;
12         final Node<E> next = f.next;
13         f.item = null;
14         f.next = null; // help GC
15         first = next;
16         //链表中已经没有节点了
17         if (next == null)
18             last = null;
19         else
20             next.prev = null;
21         size--;
22         modCount++;
23         return element;
24     }
View Code

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

 1     public E removeLast() {
 2         final Node<E> l = last;
 3         if (l == null)
 4             throw new NoSuchElementException();
 5         return unlinkLast(l);
 6     }
 7 //unlinkLast:删除链表的最后一个节点，并删除链接，私有方法，供removeFirst方法调用
 8 //使用前提：f!=null,否则会抛出异常；并且l是链表的最后一个节点，否则会删除f到链表尾部的所有节点(last=l.prev)
 9 private E unlinkLast(Node<E> l) {
10         // assert l == last && l != null;
11         final E element = l.item;
12         final Node<E> prev = l.prev;
13         l.item = null;
14         l.prev = null; // help GC
15         last = prev;
16         //该链表中已经没有节点了
17         if (prev == null)
18             first = null;
19         else
20             prev.next = null;
21         size--;
22         modCount++;
23         return element;
24     }
View Code

三、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

1     public Vector() {
2         this(10);
3     }
View Code

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

1     public synchronized void trimToSize() {
2         modCount++;
3         int oldCapacity = elementData.length;
4         if (elementCount < oldCapacity) {
5             elementData = Arrays.copyOf(elementData, elementCount);
6         }
7     }
View Code

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

 1     public synchronized void ensureCapacity(int minCapacity) {
 2         if (minCapacity > 0) {
 3             modCount++;
 4             ensureCapacityHelper(minCapacity);
 5         }
 6     }
 7     //调用了ensureCapacityHelper：
 8     private void ensureCapacityHelper(int minCapacity) {
 9         // overflow-conscious code
10         if (minCapacity - elementData.length > 0)
11             grow(minCapacity);
12     }
13     //调用了grow:
14     private void grow(int minCapacity) {
15         // overflow-conscious code
16         int oldCapacity = elementData.length;
17         //如果capacityIncrement<0,则newCapacity=oldCapacity+oldCapacity；
18         //否则则newCapacity=oldCapacity+capacityIncrement；
19         int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
20                                          capacityIncrement : oldCapacity);
21         //如果增长后仍不能保证满足minCapacity，则令newCapacity = minCapacity
22         if (newCapacity - minCapacity < 0)
23             newCapacity = minCapacity;
24         //若增长后的大小大于允许的最大长度，则调用hugeCapacity
25         if (newCapacity - MAX_ARRAY_SIZE > 0)
26             newCapacity = hugeCapacity(minCapacity);
27         //调用Arrays.copyof方法将elementData拷贝到一个容量为newCapacity的数组中。
28         //Arrays.copyOf(elementData, newCapacity)实际上是通过System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));来实现的
29         elementData = Arrays.copyOf(elementData, newCapacity);
30     }
31     //调用了hugeCapacity
32     private static int hugeCapacity(int minCapacity) {
33         if (minCapacity < 0) // overflow
34             throw new OutOfMemoryError();
35         //MAX_ARRAY_SIZE=Integer.MAX_VALUE-8
36         return (minCapacity > MAX_ARRAY_SIZE) ?
37             Integer.MAX_VALUE :
38             MAX_ARRAY_SIZE;
39     }
View Code

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

 1     public synchronized void setSize(int newSize) {
 2         modCount++;
 3         if (newSize > elementCount) {
 4         //若newSize<elementData.length,则不用扩容，否则需要扩容
 5             ensureCapacityHelper(newSize);
 6         } else {
 7         //若newSize<elementData的实际大小(elementCount),则将newSize及其后面的数组都置为空
 8             for (int i = newSize ; i < elementCount ; i++) {
 9                 elementData[i] = null;
10             }
11         }
12         elementCount = newSize;
13     }
View Code

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

1     public synchronized int capacity() {
2         return elementData.length;
3     }
4     public synchronized int size() {
5         return elementCount;
6     }
7     public synchronized boolean isEmpty() {
8         return elementCount == 0;
9     }
View Code

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

 1     public synchronized void removeElementAt(int index) {
 2         modCount++;
 3         if (index >= elementCount) {
 4             throw new ArrayIndexOutOfBoundsException(index + " >= " +
 5                                                      elementCount);
 6         }
 7         else if (index < 0) {
 8             throw new ArrayIndexOutOfBoundsException(index);
 9         }
10         int j = elementCount - index - 1;
11         if (j > 0) {
12         //将elementData从index+1到elementCount为止的元素向前移动一个位置，覆盖Index处的元素
13             System.arraycopy(elementData, index + 1, elementData, index, j);
14         }
15         elementCount--;
16         elementData[elementCount] = null; /* to let gc do its work */
17     }
18     //remove也是删除，但是没有判断index是否小于0
19     public synchronized E remove(int index) {
20         modCount++;
21         if (index >= elementCount)
22             throw new ArrayIndexOutOfBoundsException(index);
23         E oldValue = elementData(index);
24  
25         int numMoved = elementCount - index - 1;
26         if (numMoved > 0)
27             System.arraycopy(elementData, index+1, elementData, index,
28                              numMoved);
29         elementData[--elementCount] = null; // Let gc do its work
30  
31         return oldValue;
32     }
View Code

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

 1     public synchronized void insertElementAt(E obj, int index) {
 2         modCount++;
 3         if (index > elementCount) {
 4             throw new ArrayIndexOutOfBoundsException(index
 5                                                      + " > " + elementCount);
 6         }
 7         //先保证容量大于elementCount+1
 8         ensureCapacityHelper(elementCount + 1);
 9         //将elementData数组中index到elementCount之间的元素向后移动一位，给Index处空出位置
10         System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
11         elementData[index] = obj;
12         elementCount++;
13     }
View Code

四、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快。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cing/p/8023245.html