浅析Arraylist和LinkedList

妖狐艹你老母 2021-11-08 20:46 290阅读 0赞

ArrayList和LinkedList已经是老生常谈的问题了，由于太久之前看的源码，觉得最近有点不清晰了，就再次看了一遍源码，现在来记录一下区别与联系，以及一点底层实现。

#### 简述 ####

首先ArrayList底层是通过数组实现的，而LinkedList则是通过双向链表实现的，他们都是线程不安全的

都实现了List接口，规定了几个必须实现的方法add,contains,indexof,remove

### 一.ArrayList ###

#### ArrayList 成员变量 ####

*  Object\[\] elementsData;
 *  int size;

#### 底层实现 ####

*  get() 首先需要检查传入的index rangeCheck(index) 再返回数组在该index的值
 *  add() 首先保证空间足够用，然后加入新的对象在数组的尾部 ensureCapacityInternal(size+1);
 *  remove() 先检查index，然后计算出需要移动的数量，例如size=10，要删除index=5的元素，则需要移动后面的四个元素，然后调用`System.arraycopy()`方法，将数组的后面4个依次向前移动一位，然后将数组最后一位置为null。

### 二.LinkedList ###

#### LinkedList成员变量 ####

*  size
 *  Node first 记录第一 节点
 *  Node last 记录最后一个节点

#### 底层实现 ####

*  get() 类似ArrayList 先检查index的合法性然后调用node(index) 方法
 *  node() 方法![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3ODY2NDg2_size_16_color_FFFFFF_t_70]
    
     *  首先判断index是否小于size的一半，如果小于从前向后遍历，大于则从后向前遍历
 *  add()方法,直接调用linklast() 方法![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3ODY2NDg2_size_16_color_FFFFFF_t_70 1]
 *  remove()从头开始遍历链表，当找到要删除的节点，将他删除。删除的方法呢？将该节点的前后节点链接起来，

### 对比 ###

由上面的常用方法可以发现

1.ArrayList使用数组存储元素，因此在查询时速度较快，直接返回该位置的元素即可，时间复杂度为O(1);而LinkedList使用双向链表存储元素，在查询时需要从头或者尾遍历至查询元素，时间复杂度为O(n/2);

2.还是因为存储方式的问题，ArrayList在插入或者删除时，需要移动插入位置之后的所有元素，因此速度较慢，时间复杂度为O(n)。而LinkedList只需要找到该位置，移动”指针”即可,时间复杂度为O(1)。

**当你对列表更多的进行查询，即获取某个位置的元素时，应当优先使用ArrayList；当你对列表需要进行频繁的删除和增加，而很少使用查询时，优先使用LinkedList；**

### 注意事项！ ###

1.上述结论适用于普遍的情景，有些极端情况不一定符合。比如频繁的在数组结尾附近插入数据，ArrayList也快于LinkedList。

2.LinkedList使用的空间大于ArrayList，因为本质上，ArrayList在每个位置存储了元素，而LinkedList存储了元素+前面节点+后面节点。

### 扩容 ###

ArrayList 每次扩容后的大小为之前的1.5倍。`int newCapacity = oldCapacity + (oldCapacity >> 1);`

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3ODY2NDg2_size_16_color_FFFFFF_t_70]: /images/20211108/357afd01b42549f5bc28c2936b168bc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3ODY2NDg2_size_16_color_FFFFFF_t_70 1]: /images/20211108/c81f70746965413499c2d211a8d96775.png