Java 7源码分析第8篇 - List集合基于数组的实现 - JAVA

ub.add("e");// 抛出ConcurrentModificationException l.add("e"); for (int i = 0; i < l.size(); i++) { System.out.println(l.get(i));// 打印的结果为：b c e,b和c来自sub,e是直接添加的 }

如上使用循环输出，也可以使用提供的listIterator()方法进行，源代码如下：

 public Iterator
   
     iterator() {
        return listIterator();
    }

    public ListIterator
    
      listIterator(final int index) { checkForComodification(); rangeCheckForAdd(index); return new ListIterator
     
      () { private final ListIterator
      
        i = l.listIterator(index+offset);// 被final修饰,不可改变 public boolean hasNext() { return nextIndex() < size; } public E next() { if (hasNext()) return i.next(); else throw new NoSuchElementException(); } public boolean hasPrevious() { return previousIndex() >= 0; } public E previous() { if (hasPrevious()) return i.previous(); else throw new NoSuchElementException(); } public int nextIndex() { return i.nextIndex() - offset; } public int previousIndex() { return i.previousIndex() - offset; } public void remove() { i.remove(); SubList.this.modCount = l.modCount; size--; } public void set(E e) { i.set(e); } public void add(E e) { i.add(e); SubList.this.modCount = l.modCount; size++; } }; }

2、ArrayList与Vector

先来看ArrayList写法如下：

public class ArrayList
   
     extends AbstractList
    
      implements List
     
      , RandomAccess, Cloneable, java.io.Serializable

AbstractList抽象类和List类中都分别定义实现了很多的方法，同时接口中也定义了方法，ArrayList实现了所有的方法，这些方法在前面已经讲的差不多了。其实现也比较简单。在ArrayList中，主要是通过Object[]数组来完成实现的，但是他比数组有一个非常明显的优势，数组不可以在操作期间动态指定大小，而ArrayList集合中可以放入我们想要放入的所有对象，而不用管数组的大小，这个由它自己进行管理。来看一下构造函数：

    // 数组缓冲区存储数组列表的元素
    private transient Object[] elementData;// 当进行串行化时，这个属性并不会被写入
    private int size;
    
    public ArrayList(int initialCapacity) {
        super();// 
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    public ArrayList() {// 默认分配的大小为10
        this(10);
    }
    // in the order they are returned by the collection's iterator.
    public ArrayList(Collection
    c) {
        elementData = c.toArray();// 
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

初始时可以指定大小，如果不指定则默认分配的大小为10。还提供了一个有Collection参数的接口，这就为List和其他的集合之间相互转换提供了便利。

看一下在添加时，ArrayList是怎么保证数组的大小的：

    private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code 
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

这是具体扩容方法，添加时：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments(增量) modCount!!
        elementData[size++] = e;
        return true;
    }
    public void add(int index, E element) {// 和上面的一个方法的区别
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 为了给index空开一个位置
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    }

要确保在添加一个元素时有空的位置可以使用，如果没有就要调用扩容方法了。Vector类也是基于数组实现的，其实现的代码与ArrayList非常相似，只不过在可能发生线程安全的方法上加上了Synchorized关键字，使得其执行的效率相比ArrayList就低了。

另外，还有一个继承Vector类实现的Stack，Stack也是线程安全的，实现代码也比较简单，在这里就不多说了。

Java 7源码分析第8篇 - List集合基于数组的实现(三)