Java基础底层-ArrayList和LinkedList的区别

- 日理万妓 2022-12-25 00:50 132阅读 0赞

## 一、简介 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70]  
**Collection** 接口的接口 对象的集合（单列集合）  
**—List** 接口：元素按进入先后有序保存，可重复，通过索引操作元素  
**------LinkedList** 接口实现类， 链表， 插入删除， 没有同步， 线程不安全  
**------ArrayList** 接口实现类， 数组， 随机访问， 没有同步， 线程不安全  
**------Vector** 接口实现类 数组， 同步， 线程安全  
**—Set** 接口：元素唯一，不可重复，并做内部排序即存取顺序不一致；不能根据索引操作元素

## 二、区别 ##

### 总结 ###

**ArrayList**：底层数据结构是数组，查询快，增删慢，线程不安全，效率高，可以存储重复元素  
**LinkedList** ：底层数据结构是链表，查询慢，增删快，线程不安全，效率高，可以存储重复元素  
**Vector**：底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素

#### 1. 数据结构不同 ####

> ArrayList是Array(动态数组)的数据结构，LinkedList是Link(链表)的数据结构。  
> ArrayList和LinkedList都实现了List接口，即可以根据索引来随机访问集合中的元素（关于LinkedList可以随机访问集合中的元素；一开始我是不信的，自己看了下源码发现是真的，之前比较少用没注意到这点）；

// 先检查索引下标是否越界 (linkedList随机访问某个值的实现方式)
    public E get(int index) { 
        checkElementIndex(index);
        return node(index).item;
    }
    // 实际上从第一个开始遍历到指定下标后返回
    Node<E> node(int index) { 
        // assert isElementIndex(index);
    
        if (index < (size >> 1)) { 
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else { 
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

// 先检查索引是否越界 (ArrayList随机访问某个值的实现方式)
    public E get(int index) { 
    	rangeCheck(index);
    	return elementData(index);
    }
    // 底层是数组，直接放回该数组对应下标的值
    E elementData(int index) { 
        return (E) elementData[index];
    }

除此之外，LinkedList还实现了Deque接口，Deque接口是Queue接口的子接口，它代表一个双向队列，因此LinkedList可以作为双向队列 ，栈和List集合使用，功能强大

#### 2. 效率不同 ####

> 对于随机访问的get和set方法，ArrayList要优于LinkedList，因为LinkedList要移动指针。

> 对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

#### 3. 扩容方式不同 ####

> ArrayList底层是一个数组，在没有指定大小的情况下，数组默认的初始容量是10，当超过容量会触发1.5倍的扩容，旧的数组会被拷贝到新的数组中，新数组大小为原来的1.5倍。这样一定程度会造成空间的浪费。

> LinkedList底层是双向链表，大小是动态变化的，没有增容问题，插入一个开辟一个空间。可以看做是无限大。

#### 4. 空间开销不同 ####

> ArrayList主要控件开销在于需要在lList列表预留一定空间；而LinkList主要控件开销在于需要存储结点信息以及结点指针信息。

> LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置

#### 5. 时间复杂度不同 ####

>  *  ArrayList  
>     get() 直接读取第几个下标，复杂度 O(1)  
>     add(E) 添加元素，直接在后面添加，复杂度O（1）  
>     add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O（n）  
>     remove（）删除元素，遍历后寻找到下标位置，后面的元素需要逐个移动，复杂度O(n)

>  *  LinkedList  
>     get() 获取第几个元素，依次遍历，复杂度O(n)  
>     add(E) 添加到末尾，复杂度O(1)  
>     add(index, E) 添加第几个元素之后，需要先查找到第几个元素，再进行前后绑定，复杂度O(n)  
>     remove（）删除元素，不考虑寻找位置的过程，复杂度O(1)

#### 6. 线程安全性相同 ####

> 两者都是线程不安全的；若想在多线程下使用，应该使用Colletions类中的静态方法synchronizedList()对ArrayList进行调用即可

## 三、适用场景 ##

如果应用程序对数据有较多的随机访问，ArrayList对象要优于LinkedList对象；  
如果应用程序有更多的插入或者删除操作，较少的数据读取，LinkedList对象要优于ArrayList对象；  
不过ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移动较少的数据，而LinkedList则需要一直查找到列表尾部，反而耗费较多时间，这时ArrayList就比LinkedList要快。

## 拓展 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70]: /images/20221120/c01a04c09bcc49d0b734758f9d77d170.png