Vector、ArrayList、LinkList集合框架的使用与理解

966 阅读10分钟

说起集合框架也是老生常谈的话题,也是面试过程中面试官高频率问到的基础知识,新人在学习集合框架的时候总是会经常混淆这些概念和各自特性,这里简单对常用的几种集合做个简单总结,如有疏漏请大家多多包涵。

首先我们来简单了解一下Java的集合框架,如图(图片来自网络):

Collection接口是我们集合框架根接口对象,Collection接口为我们定义了一系列数据集合操作,包括对集合元素的增加、删除、插入和修改以及迭代等,他的实现子类包括:

Known Indirect Subclasses


基本操作包括:

  • add(Object o):增加元素
  • addAll(Collection c):...
  • clear():...
  • contains(Object o):是否包含指定元素
  • containsAll(Collection c):是否包含集合c中的所有元素
  • iterator():返回Iterator对象,用于遍历集合中的元素
  • remove(Object o):移除元素
  • removeAll(Collection c):相当于减集合c
  • retainAll(Collection c):相当于求与c的交集
  • size():返回元素个数
  • toArray():把集合转换为一个数组

如上图介绍:Collection接口类主要有三种实现类,Set集合、Queue集合以及最常用的List集合,这里需要注意一下,Map不属于Collection集合的实现类,后续会对Map集合框架进行详解,这里暂时跳过Map的介绍,

因为我们今天主要讲解的是List集合,这里为了加深对集合框架的理解列出此图,那么相关Set集合和Queue以及Map集合大家可以暂时先查找相关资料,这里暂时跳过。

List接口的具体实现类包括LinkList、ArrayList、Vector以及Stack类,现在分别对他们的使用和特性做一个简单的介绍、

  1. Vector集合简单介绍

我们首先看看这张图(如下),Vector类的继承关系:

正如上图,Vector继承自AbstractList抽象集合类,并实现了Serializable(序列化接口)、Cloneable(对象克隆接口)、List<E>抽象接口,继续追查AbstractList类我们发现(下图):

AbstractList抽象类实现了List接口,并继承了AbstractCollection<E>类,

  • Known Direct Subclasses

如上Api介绍:AbstractList接口直接实现子类有ArrayList<E>和Vector<E>,间接实现子类包括LinkedList<E>和Stack<E>,我们今天要讲的这几个集合类都是AbstractList<E>的实现子类,那么回到正题,

Vector是List接口的实现类,支持所有的包括 adding, removing, and replacing elements在内的元素操作,底层基于数组Object[]的实现,Vector所有对元素的操作是同步的,通过加锁的方式保证数据写入的一致性,这是Vector与其他list子类最大的区别,既然底层数据结构是数组,那么我们应该知道Vector具备数组索引快,增删慢的特性,因为增删都需要移动数组元素位置,而数组支持通过下标可以快速索引元素,时间复杂度O(1),但是增删一个元素时间复杂度为O(n-1)n。

Vector支持4种构造方法:

第一种构造方法创建一个默认的向量,默认大小为10:

Vector()

第二种构造方法创建指定大小的向量。

Vector(int size)

第三种构造方法创建指定大小的向量,并且增量用incr指定. 增量表示向量每次增加的元素数目。

Vector(int size,int incr)

第四种构造方法创建一个包含集合c元素的向量:

Vector(Collection c)

除了Collection接口定义方法外,Vector也定义了一些方法,具体请参考Api,这里不详细例举。

   2.ArrayList集合介绍:

继承关系我就不贴出来了,前面已经做了详细的介绍,我们单刀直入粗暴了解一下ArrayList一下,ArrayList的官方描述这样说:ArrayList继承自List接口,支持包括 adding, removing, and replacing elements等基于动态数组实现的集合结构,所有元素都支持,包括null。

这一点跟Vector很像,既然ArrayList底层也是基于数组实现的,那岂不是增删查的性能开销与Vector一样咯,在某种程度上来说的确如此,他允许对元素进行快速访问,但是这里需要注意,ArrayList是线程不安全的,而Vector是线程安全的操作类,也就是说在单线程情况下ArrayList决定是你的不二选择,但是在多线程操作下我们需要谨慎使用ArrayList集合类,避免多线程同时写而引起的数据不一致性,但实现同步需要很高的花费,因此,访问Vector比访问ArrayList慢,Vector就是因为做了这层加锁操作在使用效率上低于ArrayList性能。

除了性能开销上二者有差别,当然在其他方面也有,例如扩容,默认的扩容因子不同,Vector默认扩展容量是原来的一倍,而ArrayList是原来的50%,具体实现请看Api.

当然ArrayList也有自己的方法,大家也可以通过看看源码ArrayList有那些实现方法以及构造函数之间的差别。

3. LinkedList集合介绍 :

同样继承关系也不贴出来,简单粗暴的了解LinkedList集合,官方这样描述的:LinkedList是List接口的实现类,支持包括增加、删除、修改、查询等操作在内的基于双链表的实现类,允许操作所有元素对象包括null。

那么LindedList集合与ArrayList、Vector集合有哪些不同?

我们知道后两者是基于数组实现存储的线性表结构,而LinedList底层是通过双链表实现数据存储相关操作,如果大家对链表不是很熟悉建议深入学习一下,我们知道链表对元素操作特性是遍历慢,增删快,不像数组基于下标的特性可以快速访问,只能从链表头指针或尾指针进行遍历操作,性能开销比较大,但是基于链表这种指针特性,可以快速进行元素增删操作,并不需要内存中元素进行复制和移动,链表结构中元素是散列储存的,而数组是线性排列的,故LinkedList很适合数据的动态插入和删除,随机访问和遍历速度则比较慢。

除了这些特性之外,另外,他还提供了List接口中没有定义的方法,专门用于操作表头和表尾元素,可以当作堆栈、队列和双向队列使用。具体方法和构造大家自己去查看Api。

4.Stack堆栈集合类:

Stack属于Vector的子类,属于堆栈集合类,属于新增的集合类,官方描述是:Stack是一种后进先出(LIFO)数据结构,它代表了一组对象。它允许用户从堆栈中弹出和推送,包括null对象。堆栈的大小没有限制。

那么既然知道它是堆栈结构,我相信大家应该对堆栈结构都了如指掌,这是我们面向对象课程里面很重要也是很基础的知识,学过java的盆友都不会遗忘吧,如果真的记不清了要记得去补哦,

既然是堆栈结构,那么它的方法肯定包括pop()和 peek()吧,入栈和出战是栈操作的最基本元素操作,当然除了这两个大家熟知的方法还有其他方法,具体也不例举大家动手查一下。


那么看到这儿今天的内容基本就结束了,最后做个小常规快速总结:

  1. ArrayList是最常用的List实现类,内部是通过数组实现的,它允许对元素进行快速随机访问。当数组大小不满足时需要增加存储能力,就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此,它适合随机查找和遍历,不适合插入和删除。
  2. Vector与ArrayList一样,也是通过数组实现的,不同的是它支持线程的同步,即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,访问它比访问ArrayList慢。
  3. LinkedList是用链表结构存储数据的,很适合数据的动态插入和删除,随机访问和遍历速度比较慢。另外,他还提供了List接口中没有定义的方法,专门用于操作表头和表尾元素,可以当作堆栈、队列和双向队列使用。
  4. vector是线程(Thread)同步(Synchronized)的,所以它也是线程安全的,而Arraylist是线程异步(ASynchronized)的,是不安全的。如果不考虑到线程的安全因素,一般用Arraylist效率比较高。
  5. 如果集合中的元素的数目大于目前集合数组的长度时,vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据,用vector有一定的优势。

  6. 如果查找一个指定位置的数据,vector和arraylist使用的时间是相同的,都是0(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为0(n-i)n为总长度,这个时候就应该考虑到使用Linkedlist,因为它移动一个指定位置的数据
    所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。
    ArrayList 和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,都允许直接序号索引元素,但是插入数据要设计到数组元素移动 等内存操作,所以索引数据快插入数据慢,
    Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差
    ,LinkedList使用双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项的前后项即可,所以插入数度较快!


最后:List集合元素是有序可重复的集合,这与后面我们讲到的set集合和map会有所不同,另外List接口也提供iterator()方法,我们前面贴出来过,我们可以对集合元素进行迭代输出,属于非常使用高效的遍历操作,当然你也可以通过集合for循环或者数组遍历等操作,集合与数组之间支持互相转换,那么内容到此结束,谢谢大家! 

期盼与大家一起在技术的道路不断成长,谢谢支持!