Arraylist、LinkedList和Vector三者区别

Arraylist、LinkedList和Vector三者关系与区别

一、简介

ArrayList 简介

  1. 是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。
  2. 继承于AbstractList，
  3. 实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。
  4. ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
  5. ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。
  6. ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
  7. ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

LinkedList 简介

  1. 继承于AbstractSequentialList的双向链表。它也可以被当做堆栈、队列或双端队列进行使用。
  2. 实现List接口，能让它进行队列操作。
  3. 实现Deque接口，即能将LinkedList当做双端队列使用。
  4. 实现Cloneable，即覆盖了函数clone()，能被克隆。
  5. 实现了java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
  6. 操作不是线程安全的。

Vector 简介

  1. Vector 是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口。
  2. Vector 继承了AbstractList，实现了List；所以，它是一个队列，支持相关的添加、删除、修改、遍历等功能。
  3. Vector 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在Vector中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。
  4. Vector 实现了Cloneable接口，即实现clone()函数。它能被克隆。
  5. 和ArrayList不同，Vector中的操作是线程安全的

二、区别

ArrayList 与 LinkedList 区别

其实ArrayList和LinkedList之间的区别就是数组和双向链表之间的区别,主要分为以下几点：

  1. 是否保证线程安全 ：
    • ArrayList 和 LinkedList 都是不同步的, 也就是他们都不保证线程安全
  2. 底层数据结构：
    • Arraylist 底层使用的是 Object 数组
    • LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环，下文有简单介绍）
  3. 插入和删除是否受元素位置影响：
    • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响
      例如：add(E e)方法的时候，ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话 add(int index, E element )时间复杂度就为 O(n-i)。
      因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作
    • LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入
  4. 是否支持随机访问：
    • ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)
    • LinkedList 不支持高效的随机元素访问
  5. 内存空间占用：
    • ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间
    • LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）

双向链表和双向循环链表：

双向链表 和 双向循环链表

双向链表： 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
在这里插入图片描述

双向循环链表： 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。
在这里插入图片描述

ArrayList 和 Vector 的区别

ArrayList 和 Vector 都是用数组实现的，主要有这么四个区别：

  1. Vector 是多线程安全的，线程安全就是说多线程访问同一代码，不会产生不确定的结果。而 ArrayList 不是，这个可以从源码中看出，Vector 类中的方法很多有 synchronized 进行修饰，这样就导致了 Vector 在效率上无法与 ArrayList 相比；
  2. 两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式不同。
  3. Vector 可以设置增长因子，而 ArrayList 不可以。
  4. Vector 是一种老的动态数组，是线程同步的，效率很低，一般不赞成使用。

适用场景分析：

  1. Vector 是线程同步的，所以它也是线程安全的，而 ArrayList 是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用 ArrayList 效率比较高。
  2. 如果集合中的元素的数目大于目前集合数组的长度时，在集合中使用数据量比较大的数据，用 Vector 有一定的优势

总结

总结一下：

  1. ArrayList和Vector结构一样都是动态数组，区别是ArrayList是线程不安全的，Vector是线程安全的，ArrayList性能好于Vector,ArrayList是应用最多的集合。

  2. ArrayList和LinkedList的区别是他们的数据结构不同，ArrayList是动态数组，LinkedList是双向链表，在查询操作较多，在特定位置插入数据和删除数据较少的情况下一般选用ArrayList，在特定位置插入数据，删除数据操作较多，查询较少的情况下一般选用LinkedList，但是在大多数应用中都是对查询效率要求较高，所以ArrayList集合应用更广泛一些。