ArrayList 、 LinkedList、Vector的底层结构以及区别

发布时间:2022-03-01 12:13:46 作者:yexindonglai@163.com 阅读(72)

ArrayList、 LinkedList、Vector的区别如下:

数组结构是否线程安全效率初始容量扩容机制-倍数
ArrayList动态数组遍历查找快,插入删除慢10

倍数 :1.5 
比如初始值是10,

第一次扩容公式  10*1.5 = 15

第二次扩容公式  15*1.5 = 22

扩容计算时去掉结果的小数部分

LinkedList双向链表插入删除快,遍历查找慢双向链表没有初始容量双向链表也没有扩容机制,一直在后面或者前面添加元素就好
Vector动态数组遍历查找快,插入删除慢10

倍数  2 倍

比如初始值是10,

第一次扩容公式  10*2 = 20

第二次扩容公式  20*2 =40

ArrayList

    ArrayList 是动态数组,动态的意思是可以随时增加数组长度,众所周知,普通数组的长度是定死的,想要增加长度,就必须重新定义一个固定长度的数组,然后在把元素加进去,但是ArrayList可以随意增加或删除元素,这就让我们在操作的时候变得更灵活,动态数组每个元素都有一个下标,也就是标识这个元素的位置,通过这个下标,计算机就可以知道这个元素存放在内存的哪个位置,所以ArrayList 想要遍历查找某个元素的时候很快就能找到!而且,ArrayList也是线程不安全的, ArrayList的底层存储原理如下:

既然遍历查找很快,那为什么插入删除就很慢呢?
    因为ArrayList 是基于下标存储的,如果你在中间某个元素的前面插入一个元素,那么后面的元素的下标都要往后移一位,这无疑会影响效率,删除也是同样的道理,删除某个元素后,那么后面的元素下标就都要往前移一位;如图:

 

LinkedList

    LinkedList的底层结构是双向链表,那什么是双向链表呢?学过java的童鞋们肯定都知道Iterator 迭代器吧? 其实Iterator 就是单向链表,单向链表中,每个元素中除了数据之外还有一个指针,这个指针指向下一个元素,我们先来看看单向链表是什么样的,如图:

单向链表

双向链表

我们知道了单向链表,也就很容易猜出双向链表了,其实双向链表就是除了元素本身之外,还有两个指针,一个指针指向前一个元素的地址,另一个指针指向后一个元素的地址,如下图:

LinkedList的底层就是用双向链表实现的,因为链表本身是无序的,所以LinkedList 插入或者删除都很快,但是要查找或者遍历的时候就会很慢,因为双向链表每次查找某个元素的时候都会在内部遍历一遍,直到找到那个指定下标的元素为止,另外,LinkedList 的内存占用要比ArrayList大,因为LinkedList除了存储数据之外,还存储了2个指针,一个指向前一个元素,一个指向后一个元素。

补充知识:

  • 双向链表,因为存储了2个指针,一个指向前一个元素,一个指向后一个元素,所以,从双向链表的任意一个元素开始,都可以很方便快速地访问它的前一个节点和后一个节点。
  • LinkedList 也是一个 队列,因为它实现了 Deque<E> 接口,而 Deque<E> 又实现了Queue<E> 接口,所以LinkedList也间接实现了Queue接口,用add()进行入队,使用 poll() 方法进行出队操作,遵循先进先出原则!

Vector

    总体来说,Vector除了是线程安全的之外,Vector 和 ArrayList 的底层存储结构基本相似,但又不完全相同,不同点如下:

  • ArrayList的性能方面要优于Vector
  • Vector 和 ArrayList 都是动态数组,会根据实际需要动态调整容量,只不过Vector每次都会增加一倍,而ArrayList每次只会增加50%;
  • Vector 内每个方法都带有synchronized 同步代码块,所以Vector是线程安全的,而ArrayList 是线程不安全的

关键字Java