Java基础知识之ArrayList和LinkedList的比较

客官°小女子只卖身不卖艺 2023-07-20 12:27 18阅读 0赞

**一.基本概念:**  
首先看这两类都实现List接口，而List接口一共有三个实现类，分别是ArrayList、Vector和LinkedList。List用于存放多个元素，能够维护元素的次序，并且允许元素的重复。3个具体实现类的相关区别如下：

***(1)存储结构***  
ArrayList和Vector:是按照顺序将元素存储，删除元素时，删除操作完成后，需要使部分元素移位，默认的初始容量都是10.

ArrayList和Vector是基于数组实现的，LinkedList是基于双向链表实现的（含有头结点）。

***(2)线程安全性***  
**ArrayList\*\*\*\*不具有有线程安全性**，在单线程的环境中，**LinkedList也是线程不安全**的，如果在并发环境下使用它们，可以用C**ollections类中的静态方法synchronizedList(）对ArrayList和LinkedList进行调用即可。**  
API中的解释:

synchronizedList
    public static <T> List<T> synchronizedList(List<T> list)返回指定列表支持的同步（线程安全的）列表。为了保证按顺序访问，必须通过返回的列表完成所有对底层实现列表的访问。
    在返回的列表上进行迭代时，用户必须手工在返回的列表上进行同步： 
    
      List list = Collections.synchronizedList(new ArrayList());
          ...
      synchronized(list) { 
          Iterator i = list.iterator(); // Must be in synchronized block
          while (i.hasNext())
              foo(i.next());
      }
     不遵从此建议将导致无法确定的行为。 
    如果指定列表是可序列化的，则返回的列表也将是可序列化的。 
    参数：
    list - 被“包装”在同步列表中的列表。 
    返回：
    指定列表的同步视图。

**Vector实现线程安全的**，即它大部分的方法都包含关键字synchronized,但是Vector的效率没有ArraykList和LinkedList高。

***(3)扩容机制***  
从内部实现机制来讲，**ArrayList和Vector都是使用Object的数组形式来存储的**，当向这两种类型中增加元素的时候，若容量不够，需要进行扩容。**ArrayList**扩容后的容量是之前的**1.5倍**，然后把之前的数据拷贝到新建的数组中去。而**Vector**默认情况下扩容后的容量是之前的2**倍**。

**Vector可以设置容量增量，而ArrayList不可以**。在Vector中，有capacityIncrement：当大小大于其容量时，容量自动增加的量。如果在创建Vector时，指定了capacityIncrement的大小，则Vector中动态数组容量需要增加时，如果容量的增量大于0，则增加的是大小是capacityIncrement，如果增量小于0，则增大为之前的2倍。

**在这里需要说一下可变长度数组的原理：当元素个数超过数组的长度时，会产生一个新的数组，将原数组的数据复制到新数组，再将新的元素添加到新数组中。**

***(4)增删改查的效率***  
ArrayList和Vector中，从指定的位置检索一个对象，或在集合的末尾插入、删除一个元素的时间是一样的，时间复杂度都是O（1）。但是如果在其他位置增加或者删除元素花费的时间是O（n）,LinkedList中，在插入、删除任何位置的元素所花费的时间都是一样的，时间复杂度都为O（1），但是他在检索一个元素的时间复杂度为O（n）.

**所以如果只是查找特定位置的元素或只在集合的末端增加移动元素，那么使用ArrayList或Vector都是一样的。如果是在指定位置的插入、删除元素，最好选择LinkedList**

二.总结区别:  
(1)关于ArrayList和Vector区别如下：  
①:ArrayList在内存不够时默认是扩展50% + 1个，Vector是默认扩展1倍。  
②:Vector提供indexOf(obj, start)接口，ArrayList没有。  
③:Vector属于线程安全级别的，但是大多数情况下不使用Vector，因为线程安全需要更大的系统开销。

(2)ArrayList和LinkedList的区别如下：  
1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是 统一的，分配一个内部Entry对象。  
2．在ArrayList的 中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。  
3．LinkedList不支持高效的随机元素访问。  
4．ArrayList的空 间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在每一个元素都需要消耗相当的空间

当操作是在一列 数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中 间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。

所以，如果只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是对其它指定位置的插入、删除操作，最好选择LinkedList。