ArrayList 、 LinkedList、Vector的区别如下:
ArrayList | LinkedList | Vector | |
结构 | 动态数组 | 双向链表 | 动态数组 |
是否线程安全 | 否 | 否 | 是 |
效率 | 遍历查找快,插入删除慢 | 插入删除快,遍历查找慢 | 遍历查找快,插入删除慢 |
初始容量 | 10 | 双向链表没有初始容量 | 10 |
扩容机制-倍数 | 倍数 :1.5 +1 第一次扩容公式 10*1.5+1 = 16 第二次扩容公式 16*1.5+1 = 25 | 双向链表也没有扩容机制,一直在后面或者前面添加元素就好 | 倍数 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 是线程不安全的