集合

ArrayList

• ArrayList可以加入null,并且多个
• ArrayList是由数组来实现数组存储的
• ArrayList基本等同于Vector, 除了ArrayList是线程不安全（执行效率高）
• ArrayList中维护一个Object类型的数组elemdntData. transient Object[] elementData;
  • transient 序列化时会忽略这个字段
• 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加元素的时候，扩容elementData为10， 如需要再次扩容，则扩容elementData为1.5倍。 ```java private static final int DEFAULT_CAPACITY = 10; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private int size;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; // 初始化ArrayList 用无参构造 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

//添加元素 public boolean add(E e) { // 第一次size是0， 所以传入的是1 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }

private static int calculateCapacity(Object[] elementData, int minCapacity) { // 因为在构造器中初始化 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 取 DEFAULT_CAPACITY（10） 和 minCapacity（1） 中较大的哪一个 10 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }

private void ensureExplicitCapacity(int minCapacity) { modCount++; // 记录当前集合被修改的次数

// overflow-conscious code
// minCapacity是使用ArrayList者需要的最小容量
// elementData.length 因为ArryList底层是数组，底层这个数组的长度比我需要的最小容量小，那就需要扩容
if (minCapacity - elementData.length > 0)
    grow(minCapacity);

}

//扩容 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容1.5倍 注意0的1.5倍也是0 // 注意0的1.5倍也是0，如果扩容后的容量没有需要的最小容量大，那就扩容到最小容量 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 ArrayList(int initialCapacity) `，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍。
```java
private static final Object[] EMPTY_ELEMENTDATA = {};
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 定义

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

• Vector 的方法被 synchronized 修饰， 是线程安全的。

• 扩容机制
  • 如果是无参，默认是10， 按2倍扩容
  • 如果是有参，就是指定的容量，按2倍扩容

LinkedList

• LinkedList底层实现了双向链表和双端队列特点
• 可以添加任意元素（元素可以重复），包括null
• 线程不安全，没有实现同步
• LinkedList底层维护了一个双向链表
• LinkedList中维护了两个属性first和last分别指向首节点和尾结点
• 每个节点（Node对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个节点，通过next指向后一个节点。最终实现双向链表。
• LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高。
• boolean add(E e) 源码 ```java public boolean add(E e) { linkLast(e); return true; }

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

private static class Node { E item; Node next; Node prev;

Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
}

}

- remove 删除的是第一个元素
```java
public E remove() {
    return removeFirst();
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
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;
}