List接口的实现类——ArrayList, LinkedList 和 Vector

1 概述

List 接口规定它的实现类需要有以下特性

  • 是一个有序集合
  • 可以包含多个相同的元素
  • 访问指定位置的元素
  • Java 集合框架实现List接口的有三个常用类ArrayList, LinkedList 和 Vector

2 ArrayList

  • ArrayList的底层实际上是在维护一个数组,由于数组的内存是连续的,所以可以很方便地通过索引index来访问指定位置的元素。

  • 数组在初始化的时候长度固定了,所以如何设置数组的长度成了一个问题。ArrayList提供了一个构造器来设置初始值。如果不传入这个值,会把elementData初始化为ArrayList里维护的一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

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提供的扩容策略是

    • 首先保证当前操作需要的最小容量 minCapacity
    • 然后假定我需要扩容的容量是 newCapacity = oldCapacity + (oldCapacity << 1) 也就是 现有容量的1.5倍
    • 取两个值更大的那个 newCapacity = max(minCapacity, newCapacity)
    • 再与数组理论上允许的最大值 MAX_ARRAY_SIZE(等于Integer.MAX_VALUE - 8) 比较, 如果minCapacity比MAX_ARRAY_SIZE还大,直接把容量扩充到Integer.MAX_VALUE
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; }
  • 总之,由于数组的特性,ArrayList 在访问元素的时候可以通过内存地址偏移量快速访问。在执行需要改变数组结构的操作时,性能就比较差。

3 LinkedList

  • LinkedList的底层维护的是一个双向链表,检索指定位置的元素时必须从头开始访问或从尾部开始遍历(会先判断离头近还是离尾巴近, get(index)方法实际调用了下面这个方法
Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
  • 双向链表在添加和插入元素的时候特别方便,只要维护前后节点就好了。所以LinkedList的添加和插入性能好。

4 Vector

Verctor 就是一个线程安全的ArrayList, 每个接口都使用了synchronized关键字修饰。

5 ListIterator

ListIterator是一个为List定制的接口,继承自Iterator。ListIterator 额外定义了hasPrevious()和previous()方法,所以可以从后往前迭代。

6 总结

  • ArrayList, LinkedList 和 Vector 都实现了List接口
  • Vector通过synchronized关键字修饰方法,是线程安全的。ArrayList和LinkedList不是线程安全的。
  • ArrayList在通过索引访问get(index)和修改set(index, e)时性能比LinkedList要好,在执行需要改变数组结构的操作比如插入,删除和容量不足时的添加操作时性能比LinkedList要差。
阅读(47)
评论(0)
updated@2020-11-02
评论区
目录