[置顶] 迭代器模式和java集合Collection（一）ArrayList

这里主要通过java集合Collection来学习迭代器模式。

1. 迭代器模式介绍

1.1. 一般性UML图

 

Iterator是迭代器接口，定义了迭代器必须要实现的两个接口hasNext()和next()。

Aggregate是容器定义了iterator()用于创建一个迭代器。

ConcreteIterator是具体迭代器类，实现了hasNext()和next()接口，实现了遍历集合的方法。

ConcreteAggregate是具体的容器类。

1.2. 简单的例子

public interface Iterator {

public Object next();
public boolean hasNext();
}

public interface Aggregate {

public Iterator iterator();
}

public class ConcreteAggregate implements Aggregate {

private String[] items = {"a", "b", "c", "d"};
private int current = 0;
private int count = items.length;
@Override
public Iterator iterator() {
return new ConcreteIterator();
}

private class ConcreteIterator implements Iterator {

@Override
public Object next() {
if(current >= count) {
                throw new NoSuchElementException();
}
return items[current++];
}

@Override
public boolean hasNext() {
return current < count;
}

}
}

public class TestIterator {

public static void main(String[] args) {
Aggregate aggregate = new ConcreteAggregate();
Iterator iterator = aggregate.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}

2. ArrayList

2.1. Uml

 

 先看一个简单的例子

public class TestArrayList {

public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}

结果

5

6

7

8

9

2.2. 构造函数

private transient Object[] elementData;
private static final Object[] EMPTY_ELEMENTDATA = {};
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
}

ArrayList 是通过数组来存储对象的，这个构造函数把一个空的数组赋予 elemenData ， elemenData 就是用来存储对象的数组。

2.3. add()方法

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(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);
}

主要看 grow() 方法中的这两句

int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity);

  当对象个数超过 elementData 的长度，把 elementData 的长度 增加 1/2 ， elementData 的 初始长度在ensureCapacityInternal() 方法中创建为 EFAULT_CAPACITY，即 10 。

这里可以看到ArrayList可能浪费的内存为对象个数1/2。

2.4. iterator()方法

    public Iterator<E> iterator() {
        return new Itr();
    }

2.5. 内部迭代器类Itr

 

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
int expectedModCount = modCount;

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

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

l Itr.next()方法返回elementDate[current]，同时lastRet=current;current自增1,lastRet标记上一个对象。

l Itr.hasNext()当current等于size时返回false。

l Itr.remove()调用ArrayList的remove方法删除lastRet标记的对象，同时cursor=lastRet;lastRet=-1。

2.6. ArrayList.remove(int index)

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

其实就是删除 elementData[index],index 后面的对象全部往前移动一位，可以看出 ArrayList 删除对象的时间复杂度是 O(n) 。

 

List接口主要是在Collection的基础上增加一些通过index来索引容器中的对象的方法。就不具体写了，下面在看一个HashMap的例子《

迭代器模式和java集合Collection（二）HashMap和Set》