积土成山，风雨兴焉；积水成渊，蛟龙生焉；积善成德，而神明自得，圣心备焉。故不积跬步，无以至千里，不积小流无以成江海。齐骥一跃，不能十步，驽马十驾，功不在舍。面对悬崖峭壁，一百年也看不出一条裂缝来，但用斧凿，能进一寸进一寸，能进一尺进一尺，不断积累，飞跃必来，突破随之。

目录

Java标准库自带的java.util包提供了集合类：Collection，它是除Map外所有其他集合类的根接口。常用有：

• List：一种有序列表的集合。
• Set：一种保证没有重复元素的集合。

常用方法

源码分析

ArrayList源码分析

底层结构

一个Object类型的数组elementData。

结论

1. ArrayList中维护了一个Object类型的数组elementData。

ArrayList al = new ArrayList(); //点进去

//源码
public ArrayList() { //无参构造方法
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

this.elementData表示：

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

transient表示不会被序列化。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示：

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0。可见上面的源码。

3. 第一次添加时，则扩容elementData为10。

ArrayList al = new ArrayList();
al.add("abc"); //点进去

//源码


    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;


private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

可以看见，当第一次添加元素时，size为默认值0，会计算出一个最小容量minCapacity，如果是无参构造创建的，则会取默认的容量10。因为DEFAULT_CAPACITY为10。

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

4. 如果需再次扩容，则扩容elementData为1.5倍。

如果计算出的最小容量大于原容量minCapacity - elementData.length > 0，则会进行扩容。

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

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);
}

private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}

5. 若是使用指定大小的构造器，则初始elementData容量为指定的大小（大于0）。如果还需扩容，则扩容1.5倍。

ArrayList al = new ArrayList(20); //点进去

//源码

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

和Vector的区别在于扩容的倍数，Vector是扩容2倍。

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                   capacityIncrement : oldCapacity); //原长度再加上原长度
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList源码分析

底层结构

底层为双向链表。维护了两个属性first和last，分别指向首节点和尾结点。

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

Node中又有三个属性：item、next、prev，分别表示存储的数据、后一个节点、前一个节点。

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;
  }
}

源码

尾部添加元素：

public boolean add(E e) {
  linkLast(e);
  return true;
}


/**
 * Links e as last element.
 */
void linkLast(E e) {
  final Node<E> l = last;
  final Node<E> newNode = new Node<>(l, e, null);
  last = newNode;
  if (l == null)
    first = newNode;
  else
    l.next = newNode;
  size++;
  modCount++;
}