列表和队列之ArrayList（一）

程序员文章站 2024-03-22 10:50:04

...

分析ArrayList

前面介绍泛型的时候，我们实现了一个简单的动态数组容器类DynamicList,现在我们逐步理解Java中真正的动态数组容器类ArrayList。

1.基本用法

ArrayList是一个泛型容器，新建ArrayList需求实例化泛型参数，比如：

List<Integer> intList = new ArrayList<>();
List<String> strList = new ArrayList<>();

ArrayList的主要方法有：

public boolean add(E e) //添加元素到末尾
public boolean isEmpty() 
public int size() 
public E get(int index) 
public int indexOf(Object o) //查找元素，如果找到，返回索引位置，否则返回-1
public int lastIndexOf(Object o) //从后往前找
public boolean contains(Object o) 
public E remove(int index) 
public boolean remove(Object o)
public void clear() 
public void add(int index, E element)
public E set(int index, E element)

2.基本原理

ArrayList的用法是比较简单的，它的基本原理也是比较容易理解的。ArrayList的内部有一个数组elementData，一般会有一些预留的空间，有一个整数size记录实际元素的个数。

1.add方法的原理：

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

它先调用ensureCapacityInternal方法确保数组容量是足够的，然后再将新增的元素添加到集合末尾。详细理解可参看源码。

2.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; //将size减1，同事释放引用里边原对象被垃圾回收
   return oldValue;
}

增加modCount,然后计算要移动元素的个数，从index往后的元素移动一位，然而时间调用的是System.arraycopy方法来实现的。 elementData[--size] = null; 将size减1，同时将最后一个位置设置为null，设置为null后不再引用原对象，如果原对象也不再被其他对象引用，将被垃圾回收。

3.迭代

1.迭代器接口

ArrayList实现了Iterable接口，Iterable表示可迭代，接口定义如下：

public interface Iterable<T> {
   Iterator<T> iterator();
}

接口定义很简单，就是要实现Iterator方法，Iterator方法声明如下：

public Iterator<E> iterator()

它返回一个实现了Iterator接口的对象，Java7中Iterator接口定义如下：

public interface Iterator<E> {
  boolean hasNext();
  E next();
  void remove();
}

2.ListIterator

除了iterator()方法，ArrayList还提供了两个返回Iterator的接口方法：

public ListIterator<E> listIterator()
public ListIterator<E> listIterator(int index)

ListIterator扩展了Iterator接口，增加了一些方法，向前遍历、添加元素、修改元素、返回索引位置等方法。

public interface ListIterator<E> extends Iterator<E> {
  boolean hasPrevious();
  E previous();
  int nextIndex();
  int previousIndex();
  void set(E e);
  void add(E e);
}

3.迭代的陷阱

关于迭代器，有一种常见的误区，就是在迭代中间调用容器的删除方法。比如删除一个整数ArrayList中所有小于5的元素，大多数人会这样写：

public void remove(ArrayList<Integer> list){
  for(Integer a : list){
    if(a<=5){
      list.remove(a);
    }
  }
}

然而运行时会抛出异常：java.util.ConcurrentModificationException

发生了并发修改异常，这是为什么呢？因为迭代器内部维护了索引位置相关的数据，要求在迭代过程中，容器不能发生结构性变化，否则这些索引位置就会失效。所谓结构性变化就是添加、插入、删除等操作。只有修改元素内容不算借款性变化。

如何避免异常呢？可以使用迭代器的remove方法，代码如下：

public static void remove(ArrayList<Integer> list){
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
      if(it.next()<=100){
        it.remove();
      }
    }
}

迭代器如何知道发生了结构性变化呢？它自己的remove方法为何又可以使用呢？请关注下一篇博文，我们深入分析迭代器的实现原理。