List存储一个有序元素合集

List接口的实现类有: ArrayList,LinkedList,Vector,Stack

ArrayList一个数组型的List

默认容量为10

private static final int DEFAULT_CAPACITY = 10;

扩容

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

• 扩容的大小为原长度+1/2的原长度
• 如果扩容长度比传入的最小容量小，则使用最小容量,如果扩容长度超过设定的最大容量,则实用最大正整数
• 初始化默认长度为10,当添加到11个长度时,容量为15

add方法

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

• ensureCapacityInternal(size + 1);确保内部容量，不够则扩容
• elementData[size++] = e;赋值

remove方法

public E remove(int index) {
    //检查下标
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);
    //移动元素
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

subList内部类

生成subList对象

public List<E> subList(int fromIndex, int toIndex) {
    //检查边界
    subListRangeCheck(fromIndex, toIndex, size);
    //生成的时SubList对象,注意this
    return new SubList(this, 0, fromIndex, toIndex);
}

subList继承自AbstractList

private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;

SubList(AbstractList<E> parent,
    int offset, int fromIndex, int toIndex) {
    this.parent = parent;
    this.parentOffset = fromIndex;
    this.offset = offset + fromIndex;
    this.size = toIndex - fromIndex;
    this.modCount = ArrayList.this.modCount;
}

• 在构造方法中this.parent = parent,意味着对象为原始list
• this.parentOffset = fromIndex;和this.offset = offset + fromIndex;为原始索引

public void add(int index, E e) {
    rangeCheckForAdd(index);
    checkForComodification();
    parent.add(parentOffset + index, e);
    this.modCount = parent.modCount;
    this.size++;
}

• parent.add(parentOffset + index, e);原始list将被添加一个元素
• remove方法中E result = parent.remove(parentOffset + index);将在原始list中移除

结论:

• 在操作sublist的添加、移除等方法的时候,原始list将会被修改
• sublist是一个list的视图