Posts Java ArrayList
Post
Cancel

Java ArrayList

ArrayList 继承于 AbstractList ,实现了 List、RandomAccess、Cloneable、Serializable 接口。

ArrayList 的底层数据结构是数组,元素超出容量时会进行扩容操作。

ArrayList 中的属性

1
2
3
4
5
6
7
8
9
10
11
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;

private int size;

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  • DEFAULT_CAPACITY:默认容量为 10。
  • EMPTY_ELEMENTDATA:通过构造方法指定的容量为 0 时,使用该空数组。
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA:调用无参构造方法时,使用该数组。
  • elementData:保存添加的元素,在 ArrayList 被序列化时,该属性不会被序列化。
  • size:ArrayList 保存的元素个数。
  • MAX_ARRAY_SIZE:ArrayList 能够容纳的最大长度,231 - 1 - 8。

ArrayList 的构造方法

  • ArrayList():构造一个容量为 10 的空列表。
  • ArrayList(int initialCapacity):构造一个指定容量的空列表。
  • ArrayList(Collection<? extends E> c):构造一个列表,将给定集合中的元素按照迭代器返回的顺序复制到列表中。

使用无参构造方法创建 ArrayList 时,elementData 的长度是 0,当第一次添加元素时,它会扩容到 DEFAULT_CAPACITY

使用指定容量构造 ArrayList 时,elementData 的长度为指定的长度。

ArrayList()

1
2
3
4
5
6
7
/**
 * Constructs an empty list with an initial capacity of ten.
 * 构造一个容量为 10 的空列表,当第一次添加元素时,elementData 会扩容到 10。
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(int initialCapacity)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Constructs an empty list with the specified initial capacity.
 * 构造一个指定容量的空列表
 *
 * @param  initialCapacity  the initial capacity of the list    列表的初始容量
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative      指定容量 < 0 时抛出异常
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    }
}

ArrayList(Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 构造一个列表,并将给定的集合中的元素按照迭代器返回的顺序复制到列表中。
 *
 * @param c the collection whose elements are to be placed into this list   将被复制到列表中的元素的集合
 * @throws NullPointerException if the specified collection is null     集合为空时抛出异常
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

集合转换为数组后,如果不是 Object[] 类型,会使用 Arrays.copyOf 方法返回一个新的 Object 数组。

元素操作的基本方法

方法名说明时间复杂度
E get(int index)返回指定索引的元素O(1)
E set(int index, E element)替换指定索引的元素,返回旧元素O(1)
boolean add(E e)向列表的末尾添加元素O(1)
void add(int index, E element)在指定位置插入元素O(N)
E remove(int index)删除指定位置的元素,返回旧元素O(N)
boolean remove(Object o)删除列表中与给定对象相同的元素O(N)
boolean contains(Object o)判断列表中是否包含指定元素O(N)
int indexOf(Object o)返回指定元素在列表中的索引O(N)

其中,contains 方法直接 返回 indexOf(o) >= 0 。

对列表操作的方法

clear()

清空列表,将所有元素的引用指向 null,等待垃圾回收器回收,此操作不减小数组容量。

1
2
3
4
5
6
7
8
9
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

subList(int fromIndex, int toIndex)

返回列表的指定区域(子列表),对返回的列表做修改会影响整个列表。

1
2
3
4
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

迭代器方法

iterator()

返回一个迭代器,如果在迭代器遍历过程中调用了列表的 add,remove 等方法,会抛出 ConcurrentModificationException

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

listIterator()

返回一个迭代器,该迭代器可以向前后两个方向遍历元素。ListIter 继承于 Iter 。

1
2
3
public ListIterator<E> listIterator() {
    return new ListItr(0);
}

listIterator(int index)

返回一个从指定位置开始的迭代器。

1
2
3
4
5
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

扩容方法

ArrayList 有两个与扩容有关的方法:

  • void grow(int minCapacity)
  • int hugeCapacity(int minCapacity)

grow(int minCapacity)

1
2
3
4
5
6
7
8
9
10
11
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);
}

minCapacity 为添加新元素后数组的长度(此时还未添加)。

首先将新长度(newCapacity)设置为原来的 1.5 倍,然后计算新的长度是否能够达到 minCapacity,如果不能,则把新长度设置为 minCapacity 的大小。

如果新长度比 ArrayList 能够容纳的最大长度还要大,调用 hugeCapacity 方法来计算。否则,将列表长度调整为新长度。

hugeCapacity(int minCapacity)

1
2
3
4
5
6
7
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

这里为什么要判断 minCapacity < 0 ?

假如列表中已经有 oldCapacity = 231 - 1 个元素,在添加新元素的时候,minCapacity 为原来的长度 + 1,溢出变为 minCapacity = -231,newCapacity 扩大到 1.5 倍也溢出为负数(绝对值 < minCapacity),此时 grow 方法中 newCapacity - minCapacity > 0(绝对值小的负数 - 绝对值大的负数),最后调用该方法时传递的 minCapacity 就是 -231,将抛出异常。

最后如果 minCapacity 大于 ArrayList 能容纳的最大长度,就返回整型最大值,否则返回 MAX_ARRAY_SIZE

函数式接口方法

ArrayList 有 4 个参数为函数式接口的方法:

1. forEach(Consumer<? super E> action)

消费列表中的元素,可以对列表中的元素作出处理。以下代码打印列表中所有的偶数:

1
2
3
4
5
6
ArrayList<Integer> list = ...;

list.forEach(e -> {
    if (e % 2 == 0)
        System.out.printf("%d ", e);
});

2. removeIf(Predicate<? super E> filter)

删除列表中满足给定条件的元素。以下代码删除列表中所有偶数元素:

1
2
3
list.removeIf(e -> {
    return e % 2 == 0;
});

也可以这样写:

1
list.removeIf(e -> e % 2 == 0);

3. replaceAll(UnaryOperator operator)

替换列表中满足给定条件的元素。以下代码将所有偶数元素替换为 0 :

1
2
3
list.replaceAll(e -> {
    return e % 2 == 0 ? 0 : e;
});

也可以这样写:

1
list.replaceAll(e -> e % 2 == 0 ? 0 : e);

4. sort(Comparator<? super E> c)

使用给定的规则对列表元素排序。如果元素的类型已经实现了 Comparable 接口,可以直接传递方法引用。

以下代码对列表进行升序排序:

1
list.sort(Integer::compareTo);

逆序可以使用 Comparator.reverseOrder :

1
list.sort(Comparator.reverseOrder());

也可以在 lambda 表达式中写判断逻辑。

OLDER POST NEWER POST

Comments powered by Disqus.

内容

Search Results