容器类 | Pluto

ArrayList

和Vector不同，ArrayList中的操作是线程不安全的。所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
实现了Cloneable接口，即覆盖了函数clone( )，能被克隆。
实现java.io.Serializable接口，意味着ArrayList支持序列化，能通过序列化去传输。

直接用transient修饰数组。

1 2	//类的版本控制的序列号 private static final long serialVersionUID = 8683452581122892189L;

1 2	transient Object[] elementData; //未设置从成私有属性，为了方便内部类访问

add()

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  
    //用来确保数组容量够
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

private void ensureExplicitCapacity(int minCapacity) {
    //记录修改次数
    modCount++;

    // 避免溢出
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}


private void grow(int minCapacity) {
    
    int oldCapacity = elementData.length;
    //容量扩大1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果扩大1.5倍还是小，则直接替换成minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
	//minCapacity通常接近于size，所以这是一个优势:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private void fastRemove(int index) {
    //记录修改次数
    modCount++;
    //计算需要移动的元素个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //释放引用以便原对象被垃圾回收
    elementData[--size] = null; 
}

foreach

编译器会把它转换成类似代码

Iterator it=intList.iterator();
while(it.hasNext()){
    sout(it.next());
}

jdk 1.7中实现 Iterable 接口，接口中要求实现Iterator方法。

1.8中，定义了一个抽象方法。

1	public abstract Iterator iterator();

	//迭代器允许调用者使用良好的语义在迭代期间从基础集合中删除元素。代替了枚举接口Enumeration
 
public interface Iterator<E> {
 
    boolean hasNext();

    E next();

    //从基础集合中移除此迭代器返回的最后一个元素(可选操作)。此方法在每次调用{@link #next}时只能调用一次。如果在迭代过程中以调用此方法以外的任何方式修改了底层集合，则迭代器的行为是未指定的。
  
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
	//为每个剩余元素执行给定的操作，直到处理完所有元素或操作引发异常。
    default void forEachRemaining(Consumersuper E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

其中Itr是一个成员内部类，实现了Iterator接口。

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    //表示期望的修改次数，与之前的外部类修改次数modcount进行比较，内部类可以访问外部类的实例变量，每次发生结构性变化，modcount就会增加，而每次迭代器操作，就会检查expectedModCount 和 modCount，这样就能检测出结构性变化。
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
    	return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
    	checkForComodification();
    int i = cursor;
    if (i >= size)
    	throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
    	throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
 }

LinkedList

modCount++同样也是为了记录修改次数，便于检测中间的结构性变化。

添加方法

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

获取元素方法

Node node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

若索引部分在前半部分，则从头结点开始查找，否则从尾结点开始查找。

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

插入新元素

void linkBefore(E e, Node succ) {
        // assert succ != null;
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

步骤：

新建一个节点，先获得待插入节点的前驱。

1
newNode = new Node<>(pred, e, succ);

后继的前驱指向新节点

1
succ.prev = newNode;

前驱的后继指向新节点

1
prev.next=newNode;

删除元素

 E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
     //先获取 x 的后继节点
        final Node next = x.next;
     //再获取 x 的前驱节点
        final Node prev = x.prev;
//若前驱节点为空，说明删除的是头结点，修改头结点为x的后继，若不为空，则令前驱节点的后继节点指向删除节点的后继节点，再将删除节点的前驱节点置为null。
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
//若后继节点为空，说明删除的是尾结点，修改尾结点为x的前驱，若不为空，则令后继节点的前驱节点指向删除节点的前驱节点，再将删除节点的后继节点置为null。
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

删除 x 节点，则让 x 的前驱和后继节点直接连接起来，

ArrayDeque

基于数组实现的双端队列，相当于实现了一个循环数组。

private static int calculateSize(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.< span>
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        return initialCapacity;
    }

最关键的地方是其中的位或运算.首先,那一大串的位或运算的目的是为了得到传入的numElements的下一个2的次方数。比如传入的10,则得到16；传入16,得到32。那么经过五次的位或运算和右移运算就能够得到2^k-1的数。最后,得到的数加1即可。

示意图如下：

0 0 0 0 1 ^ ^ ^ ^ ^
0 0 0 0 1 1 ^ ^ ^ ^
0 0 0 0 1 1 1 1 ^ ^
0 0 0 0 1 1 1 1 1 1