关于java:java集合12-ArrayListLinkedListVector的相同点与区别是什么

[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:7715
LinkedList:111
Vector: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：18
LinkedList：61480
Vector：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: 7177
LinkedList: 34
Vector: 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/cod…
笔记地址：https://damaer.github.io/code…

【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指 Offer，LeetCode 等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。

2020 年我写了什么？

开源刷题笔记

素日工夫贵重，只能应用早晨以及周末工夫学习写作，关注我，咱们一起成长吧~