ArrayList 、 LinkedList、Vector的区别

liuian 2025-01-14 15:19 40 浏览

ArrayList 、 LinkedList、Vector的区别如下：

	ArrayList	LinkedList	Vector
结构	动态数组	双向链表	动态数组
是否线程安全	否	否	是
效率	遍历查找快，插入删除慢	插入删除快，遍历查找慢	遍历查找快，插入删除慢
初始容量	10	双向链表没有初始容量	10
扩容机制-倍数	倍数：1.5 +1 比如初始值是10，第一次扩容公式 101.5+1 = 16 第二次扩容公式 161.5+1 = 25	双向链表也没有扩容机制，一直在后面或者前面添加元素就好	倍数 2 倍比如初始值是10，第一次扩容公式 102 = 20 第二次扩容公式 202 =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() 方法进行出队操作，遵循先进先出原则！