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的视图