Java 常用集合类 – List

List 继承自 Collection 接口,用来存储一组相同类型的元素。List 集合代表一个元素有序、可重复的集合,和Set的区别是:元素可重复并且有顺序。

List 主要有 ArrayList、LinkedList、Vector 等几种实现方式。Java List 的架构图如下:

ArrayList

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承以下接口:

  • AbstractList,List,规定了 List 的操作规范
  • RandomAccess 支持快速随机访问
  • Cloneable 支持克隆
  • Serializable 表示序列化

ArrayList 内部由数组实现,元素允许有 null。每个 ArrayList 实例都有一个容量(Capacity),该容量是指用来存储列表元素的数组的大小(默认初始容量为10),可以随着插入数据动态扩容。

ArrayList 的特点:==适合快速随机访问,插入效率低==。当 ArrayList 内部数组的容量不够时,会对数组进行扩容,扩容大小为原大小的1.5倍:newCapacity = oldCapacity + (oldCapacity >> 1),并将旧数组中的元素拷贝到新数组后丢弃旧数组,频繁的扩容操作会影响效率。

因为 ArrayList 的初始容量比较小,所以如果能预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。

fail-fast 和 fail-safe

在 ArrayList 内部有一个重要的属性 modCount,在操作 ArrayList 实例的元素时,会改变 modCount 的值,例如:

// 移除 index 位置的元素
public E remove(int index) {
    // 判断是否越界
    rangeCheck(index);

    modCount++;

    // ...
}

那么什么是 fail-fast?在用迭代器遍历一个集合对象时,直接访问集合的数据,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出 ConcurrentModificationException。fail-fast 会在以下两种情况下抛出异常:

  1. 单线程环境,集合被创建后,在遍历它的过程中修改了结构。
  2. 多线程环境,当一个线程在遍历这个集合,而另一个线程对这个集合的结构进行了修改。

fail-fast 机制是如何检测的?

为了保证数据在遍历的过程中无法被修改,迭代器内部维护了一个 modCount 变量,当集合改变,modCount 值会被修改,而迭代器的 hasNext()next() 方法中会检查 modCount 值是否为 expectedmodCount (数据没有被修改)。如果是的话就返回遍历,否则抛出异常。

注意:java.util 包下的集合类都是快速失败的,不能在多线程下发生并发修改。如有需要,要在代码中加锁控制。

与 fail-fast 相对的是 fail-safe,采用安全失败机制的集合容器,在遍历时不直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历,因此不会抛出 ConcurrentModificationException

fail-safe 的缺点?

  1. 因为迭代器遍历的是集合的拷贝,在遍历期间无法保证读取的数据是集合中的最新状态。
  2. 需要复制集合,产生大量的无效对象,并且开销大

注意:java.util.concurrent 包下的容器都是安全失败,可以在多线程下并发使用,并发修改。

LinkedList

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

继承以下接口:

  • AbstractSequentialList,List,规定了 List 的操作规范
  • Deque 支持当作双向队列使用
  • Cloneable 支持克隆
  • Serializable 表示序列化

LinkedList 内部由双向链表实现,包含两个重要成员:header 和 size(分别表示链表表头和节点数),而双向两表的节点使用 Entry 来表示。

LinkedList 的特点:==适合顺序访问,随机访问效率低==。不存在 ArrayList 的扩容问题。

遍历方式

LinkedList 支持多种遍历方式:

// 通过迭代器遍历
for(Iterator iter = list.iterator(); iter.hasNext();)
    iter.next();

// 通过随机访问遍历
int size = list.size();
for (int i=0; i<size; i++)
    list.get(i);        

// 使用 for 循环遍历
for (Integer integ:list) 
    ;

// 通过 pollFirst() 遍历
while(list.pollFirst() != null)
    ;

// 通过 pollLast() 遍历
while(list.pollLast() != null)
    ;

// 通过 removeFirst() 遍历
while(list.removeFirst() != null)
    ;

// 通过 removeLast() 遍历
while(list.removeLast() != null)
    ;

经测试,使用 removeFist()removeLast() 效率最高,但用会删除原始数据;若只读取,使用 for 循环的方式较优。
随机访问效率最低,不建议使用!

作为队列和栈使用

LinkedList 可以作为 FIFO(先进先出)的队列使用:

队列操作 可用方法 描述
入队列 add(e)、addLast(e)、offer(e)、offerLast(e) 添加到链表末尾
出队列 remove()、removeFirst()、poll()、pollFirst() 删除链表头并返回
获取 element()、getFirst()、peek()、peekFirst() 返回链表头元素

LinkedList 可以作为 LIFO(后进先出)的栈使用:

栈操作 可用方法 描述
入栈 push(e)、addFirst(e) 添加到链表头
出栈 pop()、removeFirst() 删除链表头并返回
获取 peek()、peekFirst() 返回链表头元素

Vector

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector 是矢量队列,继承接口与 ArrayList 相同,操作也与 ArrayList 几乎一样,但是 Vector 是线程同步的,方法上添加来 synchronized 修饰。

与 ArrayList 的另一个不同是,Vector 的扩容方式,用户可以设置每次扩容增加的值(capacityIncrement),默认新的数组大小是旧的数组大小的一倍:

int newCapacity = (capacityIncrement > 0) ?
                (oldCapacity + capacityIncrement) : (oldCapacity * 2);

Stack

public class Stack<E> extends Vector<E> 

Stack 完全继承自 Vector,实现了一个后进先出的堆栈类。


经典面试题

  1. 用两个栈实现一个队列
    在实现 delete 时,难点是如何将栈中最底层的数据拿出来。简单方法可以将一个栈(1)中的数据依次拿出来压入到另一个为空的栈(2),达到元素的顺序反转。为了实现效率的提升,在 delete 时,判断栈(2)是否有数据,如果有的话,直接删除栈顶元素,在栈(2)为空时才将栈(1)的数据压入到栈(2)中。

  2. 用两个队列实现一个栈
    因为队列是先进先出,所以要拿到队列中最后压入的数据,只能每次将队列中数据 pop 到只剩一个,此时这个数据为最后压入队列的数据,在每次 pop 时,将数据压入到另一个队列中。每次执行 delete 操作时,循环往复。


Add a Comment

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

5 × 3 =