Press "Enter" to skip to content

Java List 常用集合 ArrayList、LinkedList、Vector

Java 中的 List 是非常常用的数据类型。List 是有序的 Collection,Java List 一共有三个实现类,分别是:ArrayList、Vector、LinkedList

 

 

本文分析基于 JDK8

 

ArrayList

 

ArrayList 继承自 AbstractList,实现了 List 接口。底层基于数组实现容量大小动态变化,初始容量为 10,允许值为 null,有序,非线程安全,擅长随机访问

 

ArrayList 还实现了 RandomAccess、Cloneable、Serializable 接口,所以 ArrayList 是支持快速访问、复制、序列化的

 

RandomAccess

标记接口,用来表明其支持快速随机访问。如果是实现了这个接口的 List,那幺使用 for 循环的方式获取数据会优于用迭代器获取数据

 

Serializable

标记该类支持序列化

 

Cloneable

允许在堆中克隆出一块和原对象一样的对象,并将这个对象的地址赋予新的引用。ArrayList 提供的是一种深克隆机制,即克隆除自身对象以外的所有对象,包括自身所包含的所有对象实例。实现方式是先调用 super.clone() 方法克隆出一个新对象,然后再手动将原数组中的值复制到一个新的数组,并赋值

 

ArrayList 扩容机制

 

扩容机制应该是面试中最常问的了。其他关于 ArrayList 的一些琐碎方法我就不细说了,主要介绍一下扩容机制。首先了解一下 ArrayList 的成员属性

 

// 表示 ArrayList 的默认容量大小
private static final int DEFAULT_CAPACITY = 10;
// 一个空的 Object 数组对象,长度为 0,如果使用默认构造函数创建,则 elementData 默认是该值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// ArrayList 中存放的实际元素个数
private int size;
// 当前元素对象存放的数组,不参与序列化
transient Object[] elementData;

 

执行 add 方法时,会先执行 ensureCapacityInternal 方法,判断当前数组容量是否足够,不够就扩容。然后将待添加元素加到 elementData 末尾

 

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // minCapacity > elementData.length 则扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

 

再分析一下 ensureCapacityInternal 方法,此时 minCapacity 是 size + 1,这里有两个嵌套方法 calculateCapacity 和 ensureExplicitCapacity,作用分别如下:

 

calculateCapacity

如果当前数组为空,则先设置容量为默认值 10,此时还未初始化数组

 

ensureExplicitCapacity

确认实际的容量,如果不够就扩容,关键的扩容函数 grow 就在这里

 

扩展数组大小,首先将容量扩大为原来的 1.5 倍,如果数组是空数组,则将数组初始化,默认容量为 10,如果不是,再判断是否超出最大容量,超过直接赋予最大值,否则赋予新值,复制原数组到新数组

 

private void grow(int minCapacity) {
    // 扩容前的容量
    int oldCapacity = elementData.length;
    // oldCapacity 右移一位,等于除以二
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 扩容之后还是不够,直接赋予新值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 扩容之后超出最大容量,直接赋予最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制原数组的值到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

 

LinkedList

 

LinkedList 继承自 AbstractSequentialList,实现了 List 和 Deque 接口,基于双向链表实现,每个节点都包含了对前一个和后一个元素的引用,可以被当作堆栈、队列或双端队列进行操作,有序,非线程安全

 

// 指向链表的第一个节点
transient Node<E> first;
// 指向链表的最后一个节点
transient Node<E> last;

 

JDK8 中 LinkedList 有一个静态内部类 Node,它包括的属性有:当前节点所包含的值,上一个节点,下一个节点

 

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

 

除此之外就没啥好分析的了,LinkedList 不存在容量不足的问题,克隆函数也是将所有元素全都克隆到新的 LinkedList 对象

 

Vector

 

Vector 是一个矢量队列,和 ArrayList 类似,继承自 AbstractList,实现了 List 接口,就连额外接口也是一样。不同之处在于:

Vector 使用 synchronized 保证线程同步
Vector 中遗留了大量传统的方法,这些方法不属于集合框架

Vector 有四个构造方法

 

// 创建一个默认大小为 10 的向量
public Vector()
// 创建指定大小的向量
public Vector(int initialCapacity)
// 创建指定大小的向量,并且指定增量。增量表示向量每次增加的元素数目
public Vector(int initialCapacity, int capacityIncrement)
// 创建一个包含集合 c 元素的向量
public Vector(Collection<? extends E> c)

 

Vector 的数据结构和 ArrayList 差不多,它包含了三个成员变量:

 

// 存放元素的动态数组
protected Object[] elementData;
// 动态数组的实际大小
protected int elementCount;
// 动态数组的增长系数
protected int capacityIncrement;

 

随着 Vector 中元素的增加,Vector 的容量也会动态增长,capacityIncrement 是与容量增长相关的增长系数,具体增长细节在 grow 函数中,和 ArrayList 类似

 

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 如果 capacityIncrement > 0,新的容量大小 = 旧的容量大小 + 增长系数
    // 否则容量扩大为原来的两倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

 

Stack

 

Stack 是 Vector 的子类,实现了一个标准的后进先出的栈。Stack 也是通过数组实现的,当然了,我们也可以将 LinkedList 当作栈来使用

 

Stack 只定义了默认构造函数,用来创建一个空栈

 

public Stack()

 

Stack 除了具有 Vector 的所有 API,还有自己实现的方法

 

// 判断堆栈是否为空
public boolean empty()
// 查看堆栈顶部的对象,但不从堆栈中移除它
public synchronized E peek()
// 移除堆栈顶部的对象,并作为此函数的值返回该对象
public synchronized E pop()
// 把对象压入堆栈顶部
public E push(E item)
// 返回对象在堆栈中的位置,以 1 为基数
public synchronized int search(Object o)

 

Stack 的扩容机制基于 Vector,不过由于没有指定增长系数,所有默认为 0,每次扩容数组长度增大为原来的两倍

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注