Java Collection 01 - List

  在Java语言规范中,List作为Java集合框架中的一员,提供了对同类型数据进行存储、插入、删除和查找等需求的实现过程。其实现机制和特点使得List是一个有序的,可存储重复数据的数据结构。本文演示代码段的执行环境基于JDK版本1.7

概述

  List是Java集合体系中的成员之一,直接继承于Collection。同Collection一样,List本身只是一个接口定义,其定义了对List进行操作的方法API。List是一个有序的(即输入顺序=存储顺序=输出顺序),可存放重复数据的数据结构,甚至可以向其中存储null元素。List的一些特点如下:

  1. List元素的位置下标都从0开始递增,且提供了四种方法来根据下标值获取元素,但是由于实现的不同,根据下标获取元素的时间复杂度可能随List集合元素数量成正比关系(例如LinkedList)。鉴于此,在不确定List实现方式的情况下建议采用iterate的方式获取数组元素。
  2. List还可以通过两种方法高效地在集合中的任意位置插入或者移除多个元素。
  3. List会限制保存在其中的对象类型,有些实现会限制null元素,而其他一些实现会限制特定的数据对象类型。尝试向这种List集合实现中加入不满足条件的元素会对外抛出异常。尝试查找不满条件的元素时根据实现的不同可能会对外抛出异常,或者直接返回false标识查找失败。

  常见的List实现包括AbstractListArrayListLinkedListVectorAbstractSequentialListStack等。其结构如图1所以:

图 - 1

关于上述几个具体实现类之间,分别有其适应的应用场景和特点:

  • ArrayList

      ArrayList直接继承于AbstractList,实现了List<E>, RandomAccess, Cloneable, java.io.Serializable四个接口;

      基于数组实现,在初始化时会指定数组长度,默认为0。可以执行扩容操作,扩容规则是按照当前数组容量的1.5倍进行扩容;

      由于是数组实现,所以具有随机访问元素的特点。可以在常量时间里完成元素访问,但是元素插入效率不高,需要将插入位置(如果不是在尾部插入的话)及之后的元素统一后移以释放插入空间;

      多线程环境中无法保证线程安全,不太适用于多线程环境。如果必须要用,那么需要用Collections.synchronizedList(new ArrayList(…))做一层包装;

  • LinkedList

      LinkedList直接继承于AbstractSequentialList,除了List<E>, Cloneable, Serializable接口外还实现了Deque<E>接口。而AbstractSequentialList则直接继承于AbstractList;

      基于双端链表实现,没有初始长度限制,实际上长度限制仅受限于内存容量。也没有扩容操作等;

      由于是链表实现,所以具有顺序访问的特点。访问元素时只能从首部/尾部元素逐个遍历直至到达目标元素,时间复杂度在O(n)。但是元素插入效率高;

      多线程环境中无法保证线程安全,不太适用于多线程环境。如果必须要用,那么需要用Collections.synchronizedList(new LinkedList(…))做一层包装;

  • Vector

      Vector直接继承于AbstractList,实现了List<E>, RandomAccess, Cloneable, java.io.Serializable四个接口;

      同样基于数组实现,在初始化时会指定数组长度,默认为10。可进行扩容操作,扩容长度由内部字段capacityIncrement指定,如果在初始化时未指定该字段,那么会按照当前数组容量的两倍执行扩容处理;

      同样因为采用了数组实现,所以具有随机访问元素的特点。可以在常量时间里完成元素访问,但是元素插入效率不高,需要将插入位置(如果不是在尾部插入的话)及之后的元素统一后移以释放插入空间;

      是ArrayList的线程安全版本。底层实现和依赖数据结构基本相同,由于在方法上采用了synchronized关键字来保证多线程环境下的线程安全要求。

  • Stack

      Stack是Vector的直接实现子类。具有Vector的所有特性,但是Stack是一种具有先进后出(FILO)属性的数据结构,常用于栈等场景中。

部分方法

方法声明 备注
int size(); 返回list集合中的元素总数
boolean isEmpty(); 判断list集合是否为空,为空时返回true
boolean contains(Object o); 判断list集合中是否含有元素o
Iterator<E> iterator(); 返回可以游历list集合的一个迭代器对象
Object[] toArray(); 将当前list集合中的元素以数组方式返回
<T> T[] toArray(T[] a); 将当前list集合中的元素以数组方式存储到参数a中
boolean add(E e); 加入一个元素到list集合尾部
boolean remove(Object o); 从list集合中移除一个元素
boolean containsAll(Collection<?> c); 当前list集合中是否包含集合c的所有元素
boolean addAll(Collection<? extends E> c); 将集合c中的元素都加入到list集合中
boolean addAll(int index, Collection<? extends E> c); 将集合c中的元素都加入到list集合中自index位置起的位置中
boolean removeAll(Collection<?> c); 从list集合中移除c中所有元素
boolean retainAll(Collection<?> c); 保留当前list集合中出现在c中的元素,其他元素都移除
void clear(); 清空list集合
boolean equals(Object o); 相等性判断
int hashCode(); 生成list集合的散列值
E get(int index); 根据下标获取元素
E set(int index, E element); 替换下标位置index处的元素为element
void add(int index, E element); 将元素加入到下标位置index处
E remove(int index); 移除下标位置index出的元素
int indexOf(Object o); 返回对象在list集合中第一次出现的下标位置
int lastIndexOf(Object o); 返回对象在list集合中最后一次出现的下标位置
ListIterator<E> listIterator(); 返回一个list迭代器
ListIterator<E> listIterator(int index); 返回一个list迭代器
List<E> subList(int fromIndex, int toIndex); 得到自fromIndex到toIndex位置的子集合

涉及基础知识点

  1. List中提供的subList的缺陷

      subList是基于原始List集合产生的,二者共同依赖于一套底层数组结构。如果对subList做了修改,那么修改内容会同步反映在原始List集合上,会原始List做的非结构化修改也会反映到subList上。

      此外,subList也具有快速失败的检查机制。如果在生成subList之后对原始List集合做了结构化修改,那么在访问subList时会抛出ConcurrentModificationException异常。

参考文献

  1. RUNOOB.COM. Java 集合框架 [E]
  2. J Steven Perry. 第 10 单元:Java 集合 [E]
  3. ORACLE. Collections Framework Overview [E]




------------- End of this article, thanks! -------------


  版权声明:本文由Nathan R. Lee创作和发表,采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可,转载请注明作者及出处。
  本文作者为 Nathan R. Lee
  本文标题为 Java Collection 01 - List
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-List.html