java 集合【12】——— ArrayList，LinkedList，Vector 的相同点与区别是什么？

秦怀杂货店

关注

发布于: 2021 年 03 月 26 日

[TOC]

要想回答这个问题，可以先把各种都讲特性，然后再从底层存储结构，线程安全，默认大小，扩容机制，迭代器，增删改查效率这几个方向入手。

特性列举

ArrayList：动态数组，使用的时候，只需要操作即可，内部已经实现扩容机制。

- 线程不安全

- 有顺序，会按照添加进去的顺序排好

- 基于数组实现，随机访问速度快，插入和删除较慢一点

- 可以插入null元素，且可以重复

Vector和前面说的ArrayList很是类似，这里说的也是 1.8 版本，它是一个队列，但是本质上底层也是数组实现的。同样继承AbstractList，实现了List,RandomAcess,Cloneable, java.io.Serializable接口。具有以下特点：

- 提供随机访问的功能：实现RandomAcess接口，这个接口主要是为List提供快速访问的功能，也就是通过元素的索引，可以快速访问到。

- 可克隆：实现了Cloneable接口

- 是一个支持新增，删除，修改，查询，遍历等功能。

- 可序列化和反序列化

- 容量不够，可以触发自动扩容

- *最大的特点是：线程安全的，相当于线程安全的ArrayList。

LinkedList：链表结构，继承了AbstractSequentialList，实现了List,Queue,Cloneable,Serializable，既可以当成列表使用，也可以当成队列，堆栈使用。主要特点有：

- 线程不安全，不同步，如果需要同步需要使用List list = Collections.synchronizedList(new LinkedList());

- 实现List接口，可以对它进行队列操作

- 实现Queue接口，可以当成堆栈或者双向队列使用

- 实现 Cloneable 接口，可以被克隆，浅拷贝

- 实现Serializable，可以被序列化和反序列化

底层存储结构不同

ArrayList和Vector底层都是数组结构,而LinkedList在底层是双向链表结构。

线程安全性不同

ArrayList 和 LinkedList 都不是线程安全的,但是 Vector 是线程安全的,其底层是用了大量的 synchronized 关键字,效率不是很高。

如果需要 ArrayList 和 LinkedList 是线程安全的，可以使用 Collections 类中的静态方法 synchronizedList(），获取线程安全的容器。

默认的大小不同

ArrayList 如果我们创建的时候不指定大小，那么就会初始化一个默认大小为 10,DEFAULT_CAPACITY就是默认大小。

private static final int DEFAULT_CAPACITY = 10;

复制代码

Vector 也一样,如果我们初始化,不传递容量大小,什么都不指定，默认给的容量是 10：

    public Vector() {        this(10);    }

复制代码

而 LinkedList 底层是链表结构,是不连续的存储空间,没有默认的大小的说法。

扩容机制

ArrayList 和 Vector 底层都是使用数组Object[]来存储，当向集合中添加元素的时候，容量不够了，会触发扩容机制，ArrayList 扩容后的容量是按照 1.5 倍扩容，而 Vector 默认是扩容 2 倍。两种扩容都是申请新的数组空间，然后调用数组复制的 native 函数，将数组复制过去。

Vector 可以设置每次扩容的增加容量，但是 ArrayList 不可以。Vector 有一个参数 capacityIncrement，如果 capacityIncrement 大于 0，那么扩容后的容量，是以前的容量加上扩展系数，如果扩展系数小于等于 0，那么，就是以前的容量的两倍。

迭代器

LinkedList源码中一共定义了三个迭代器：

Itr:实现了Iterator接口，是AbstractList.Itr的优化版本。
ListItr:继承了Itr,实现了ListIterator，是AbstractList.ListItr优化版本。
ArrayListSpliterator:继承于Spliterator,Java 8 新增的迭代器，基于索引，二分的，懒加载器。

Vector和ArrayList基本差不多，都是定义了三个迭代器：

Itr:实现接口Iterator，有简单的功能：判断是否有下一个元素，获取下一个元素，删除，遍历剩下的元素
ListItr:继承Itr，实现ListIterator，在Itr的基础上有了更加丰富的功能。
VectorSpliterator:可以分割的迭代器，主要是为了分割以适应并行处理。和ArrayList里面的ArrayListSpliterator类似。

LinkedList里面定义了三种迭代器，都是以内部类的方式实现，分别是：

ListItr：列表的经典迭代器
DescendingIterator：倒序迭代器
LLSpliterator：可分割迭代器

增删改查的效率

理论上，ArrayList和Vector检索元素，由于是数组，时间复杂度是O(1)，在集合的尾部插入或者删除是O(1)，但是其他的地方增加，删除，都是O(n)，因为涉及到了数组元素的移动。但是LinkedList不一样，LinkedList不管在任何位置，插入，删除都是O(1)的时间复杂度，但是LinkedList在查找的时候，是O(n)的复杂度，即使底层做了优化，可以从头部/尾部开始索引（根据下标在前一半还是后面一半）。

如果插入删除比较多，那么建议使用LinkedList，但是它并不是线程安全的，如果查找比较多，那么建议使用ArrayList，如果需要线程安全，先考虑使用Collections的api获取线程安全的容器，再考虑使用Vector。

测试三种结构在头部不断添加元素的结果：


import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Vector;
public class Test {    public static void main(String[] args) {        addArrayList();        addLinkedList();        addVector();    }    public static void addArrayList(){        List list = new ArrayList();        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.add(0,i);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }
    public static void addLinkedList(){        List list = new LinkedList();        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.add(0,i);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }    public static void addVector(){        List list = new Vector();        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.add(0,i);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }}

复制代码

测出来的结果，LinkedList 最小，Vector 费时最多，基本验证了结果：

ArrayList:7715LinkedList:111Vector:8106

复制代码

测试 get 的时间性能，往每一个里面初始化 10w 个数据，然后每次 get 出来：


import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Vector;
public class Test {    public static void main(String[] args) {        getArrayList();        getLinkedList();        getVector();    }    public static void getArrayList(){        List list = new ArrayList();        for(int i=0;i<100000;i++){            list.add(0,i);        }        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.get(i);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }
    public static void getLinkedList(){        List list = new LinkedList();        for(int i=0;i<100000;i++){            list.add(0,i);        }        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.get(i);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }    public static void getVector(){        List list = new Vector();        for(int i=0;i<100000;i++){            list.add(0,i);        }        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.get(i);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }}

复制代码

测出来的时间如下，LinkedList 执行get操作确实耗时巨大，Vector和ArrayList在单线程环境其实差不多，多线程环境会比较明显，这里就不测试了：

ArrayList ： 18LinkedList ： 61480Vector ： 21

复制代码

测试删除操作的代码如下，删除的时候我们是不断删除第 0 个元素：

import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Vector;
public class Test {    public static void main(String[] args) {        removeArrayList();        removeLinkedList();        removeVector();    }    public static void removeArrayList(){        List list = new ArrayList();        for(int i=0;i<100000;i++){            list.add(0,i);        }        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.remove(0);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }
    public static void removeLinkedList(){        List list = new LinkedList();        for(int i=0;i<100000;i++){            list.add(0,i);        }        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.remove(0);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }    public static void removeVector(){        List list = new Vector();        for(int i=0;i<100000;i++){            list.add(i);        }        long startTime = System.nanoTime();        for(int i=0;i<100000;i++){            list.remove(0);        }        long endTime = System.nanoTime();        System.out.println((endTime-startTime)/1000/60);    }}

复制代码

测试结果，LinkedList 确实效率最高，但是Vector比ArrayList效率还要高。因为是单线程的环境，没有触发竞争的关系。

ArrayList: 7177LinkedList: 34Vector: 6713

复制代码

下面来测试一下，vector 多线程的环境，首先两个线程，每个删除 5w 元素：

package com.aphysia.offer;
import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Vector;
public class Test {    public static void main(String[] args) {        removeVector();    }
    public static void removeVector() {        List list = new Vector();        for (int i = 0; i < 100000; i++) {            list.add(i);        }        Thread thread1 = new Thread(new Runnable() {            @Override            public void run() {                for (int i = 0; i < 50000; i++) {                    list.remove(0);                }            }        });        Thread thread2 = new Thread(new Runnable() {            @Override            public void run() {                for (int i = 0; i < 50000; i++) {                    list.remove(0);                }            }        });        long startTime = System.nanoTime();        thread1.start();        thread2.start();        while (!list.isEmpty()) {
        }        long endTime = System.nanoTime();        System.out.println((endTime - startTime) / 1000 / 60);    }}

复制代码

测试时间为：12668

如果只使用一个线程，测试的时间是：8216，这也从结果说明了确实Vector在多线程的环境下，会竞争锁，导致执行时间变长。

总结一下

ArrayList

- 底层是数组，扩容就是申请新的数组空间，复制

- 线程不安全

- 默认初始化容量是 10，扩容是变成之前的 1.5 倍

- 查询比较快

LinkedList

- 底层是双向链表，可以往前或者往后遍历

- 没有扩容的说法，可以当成双向队列使用

- 增删比较快

- 查找做了优化，index 如果在前面一半，从前面开始遍历，index 在后面一半，从后往前遍历。

Vector

- 底层是数组，几乎所有方法都加了 Synchronize

- 线程安全

- 有个扩容增长系数，如果不设置，默认是增加原来长度的一倍，设置则增长的大小为增长系数的大小。

【刷题笔记】
Github 仓库地址：https://github.com/Damaer/codeSolution
笔记地址：https://damaer.github.io/codeSolution/

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指 Offer，LeetCode 等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

2020年我写了什么？

开源刷题笔记

平日时间宝贵，只能使用晚上以及周末时间学习写作，关注我，我们一起成长吧~

发布于: 2021 年 03 月 26 日阅读数: 11

原文链接:【http://xie.infoq.cn/article/1c7923448c1c903815ab3162e】。文章转载请联系作者。

秦怀杂货店

关注

纵使缓慢，驰而不息。 2018.05.17 加入

慢慢走，比较快。公众号：秦怀杂货店

发布

暂无评论

创作场景

java 集合【12】——— ArrayList，LinkedList，Vector 的相同点与区别是什么？

特性列举

底层存储结构不同

线程安全性不同

默认的大小不同

扩容机制

迭代器

增删改查的效率

总结一下

秦怀杂货店

评论