在 List 集合的实现类中,主要有三个实现类:ArayList、Vector和 LinkedList。其中 Vector还有一个 Stack 子类,这个 Stack 子类仅在 Vectot 父类的基础上增加了五个方法,这五个方法就将一个 Vector扩展成 Stack。本质上,Stack依然是一个 Vector,它只是比 Vector 多了五个方法。
从上面代码可以看出,Stack的本质依然是一个Vector,只是增加了五个方法而已。读者可能已经发现,Stack新增的五个方法中有三个使用了synchronized 修饰--那些需要操作集合元素的方法都添加了synchronized 修饰。也就是说,Stack是一个线程安全的类,这也是为了让 Stack 和 Vector 保持一致--Vector 也是一个线程安全的类。
实际上,即使程序中需要栈这种数据结构,Java也不再推荐使用Stack类,而是推荐使用Deque 实现类。从JDK1.6开始,Java提供了一个Deque接口,并为该接口提供了一个ArrayDeque实现类。在无须保证线程安全的情况下,程序完全可以使用AmayDueue 来代替 Stack类。
Degue接口代表双端队列这种数据结构。双端队列已经不再是简单的队列了,它既具有队列的性质(FIFO),也具有栈的性质(FILO),也就是说,双端队列既是队列,也是。Java为Deque 提供了一个常用的实现类ArrayDeque。
就像 List 集合拥有 AmayList 实现类一样,Deque集合则拥有 ArayDeque 实现类。ArrayList和 ArayDeque 底层都是基于Java数组来实现的,只是它们所提供的方法不同而已。
vector和arraylist的区别
ArrayList使用transient 修饰了clementData数组。这保证系统序列化 ArrayList对象时不会直接序列化 clemcntData数组,而是通过 ArrayList提供的 writeObject、readObject方法来实现定制序列化;但对于 Vector 而言,它没有使用 transient修饰 elementData数组,而且 Vector 只提供了一个writeObject方法,并未完全实现定制序列化。
从序列化机制的角度来看,ArrayList的实现比Vector的实现更安全。除此之外,Vector其实就是ArrayList的线程安全版本,ArayList和Vector 绝大部分方法的实现都是相同的,只是Vector的方法增加了synchronized修饰。
由于 Vector 包含的方法比 ArrayList更多,因此 Vector 类的源代码比 ArrayList 的源代码要多,而且ArrayList的序列化实现比Vector的序列化实现更安全,因此Vector 基本上已经被ArrayList所代替。Vector唯一的好处是它是线程安全的。
即使需要在多线程环境下使用 List 集合,而且需要保证List集合的线程安全,也依然可以避免使用 Vector,而是考虑将 Arraylist包装成线程安全的集合类。Java提供了一个 Collcctions 工具类,通过该工具类的 synchronizedList 方法即可将一个普通的 ArrayList包装成线程安全的 ArrayList。
ArrayList和LinkedList的差异
List 代表一种线性表的数据结构,ArrayList 则是一种顺序存储的线性表,ArrayList底层采用数组来保存每个集合元素,LinkedList 则是一种链式存储的线性表,其本质上就是一个双向链表,但它不仅实现了List接口,还实现了Deque接口。也就是说,LinkedList 既可以当成双向链表使用,也可以当成队列使用,还可以当成栈来使用(Deque代表双端队列,既具有队列的特征,也具有栈的特征)。
如果只是单纯地添加某个节点,那么LinkedList 的性能会非常好;但如果需要向指定索引处添加节点,LinkedList必须先找到指定索引处的节点--这个搜索过程的系统开销并不小,因此 LinkedList 的 add(int index,Eelement)方法的性能并不是特别好。
当单纯地把Linkedlist当成双向链表来使用,通过addFirst(Ee)、addList(Ee)、offerFirstEe)、oferLast(E e)、pollFirst()、pollLast(等方法来操作 LinkedList 集合元素时,LinkedList的性能非常好--因为此时可以避免搜索过程。
经过上面对 ArrayList和LinkedList 底层实现的详细介绍,读者应该对AnrayList 和LinkedList之间的优劣有了一个大致的印象。就笔者的经验来说,ArrayList 的性能总体上优于LinkedList.
当程序需要以 get(int indcx)方法获取 List集合指定索引处的元素时,ArayList 性能大大地优于 LimnkedList。因为 ArayList底层以数组来保存集合元素,所以调用 gct(intindex)方法获取指定索引处的元素时,底层实际上是调用 elementData[index]来返回该元素,因此性能非常好。而 LinkedList 则必须逐个地搜索。
当程序调用 add(int index,Object obj)向 List 集合中添加元素时,ArrayList 必须对底层数组元素进行“整体搬家”。如果添加元素导致集合长度超过底层数组长度,AmayList必须创建一个长度为原来长度15倍的数组,再由垃圾回收机制回收原有数组,因此系统开销比较大。对于 LinkedList 而言,它的主要开销集中在 entry(int index)方法上,该方法必须逐个地搜索,直到找到 index 处的元素,然后在该元素之前插入新元素。即使如此,执行该方法时 LinkedList方法的性能依然高于 ArrayList。
当程序调用remove(int index)方法删除index索引处的元素时,ArrayList 同样也需要对底层数组元素进行“整体搬家”。但调用remove(imt index)方法删除集合元素时,ArrayList 无须考虑创建新数组,因此执行 ArrayList的remove(int index)方法比执行 add(int index,Object obj)方法略快一点。当 LinkedList 调用 remove(int index)方法删除集合元素时,与调用 add(int index.Objcct obj)方法添加元素的系统开销几乎完全相同。
当程序调用 add(Objcct obj)方法向 List 集合尾端添加一个元素时,大部分时候 ArrayList无须对底层数组元素进行“整体搬家”,因此也可以获得很好的性能(甚至比LinkedList的add(Object obi)方法的性能更好);但如果添加这个元素导致集合长度超过底层数组长度,那么ArrayList 必须创建一个长度为原来长度1.5倍的数组,再由垃圾回收机制回收原有数组--这样系统开销就比较大了。但 LinkedList 调用 add(Objcct obi)方法添加元素时总可以获得较好的性能。
当程序把 LinkedList 当成双端队列、栈使用,调用 addFirst(Ec)、addLast(Ee)、getFirst(Ee)、getLast(E c)、oferE e)、offerFirst0)、oferLast0等方法来操作集合元素时,LinkedList 可以快速地定位需要操作的元素,因此LinkedList总是具有较好的性能表现。上面分析了 Array、LinkedList各自的适用场景。大部分情况下,ArayList 的性能总是优于 LinkedList,因此绝大部分都应该考虑使用 AmrayList 集合。但如果程序经常需要添加、删除元素,尤其是经常需要调用 addEe)方法向集合中添加元素,则应该考虑使用LinkedList 集合。