我们来比较一下ArrayList， LinkedLIst和Vector它们之间的区别。BZ的JDK版本是1.7.0_80 经常在面试的时候，或者在大家做project的时候，都会被它们的区别产生疑惑。或者对它们的用法并不是很了解。那么我们今天就来看看他们的区别和用法。 以下是本文的大纲： 一.ArrayList，LinkedList和Vector的区别 二.详解ArrayList 三.详解Vector 四.详解LinkedList 五.在并发情况下，怎样使用它们 若有不正之处，还请多多谅解，并希望批评指正。 请尊重作者劳动成果，转发请标明blog地址 https://www.cnblogs.com/hongten/p/hongten_arraylist_linkedlist_vector.html 一.ArrayList，LinkedList和Vector的区别 ArrayList, LinkedList和Vector都实现了List接口，所使用的方法也很相似，主要区别在于实现方法的不同，所有对不同的操作具有不同的效率。 1.ArrayList ArrayList是一个可以改变大小的，线程不同步（不支持并发）的数组，内部值可以为null。 当更多的元素加入到ArrayList中时，其大小会自动增加，内部元素可以直接通过get/set方法进行访问，因为ArrayList本质上即使一个数组。 因为ArrayList是不支持并发的数组，但是如果我们在使用的过程中需要ArrayList也有同步功能，可以使用Collections.synchronziedList(new ArrayList())方法实现（在后面我们会讲到）。 2.Vector 之所以把Vector放在这里的原因是因为Vector和ArrayList是否类似，但是它是属于线程同步（支持并发）的数组，并且内部值也可以为null。如果你的程序本身是线程安全的（没有多个线程之间共享同一个集合/对象），那么请使用ArrayList吧。 3.LinkedList LinkedList底层是基于双链表实现的，在添加和删除元素时具有比ArrayList更好的性能。但是在get/set方面要弱于ArrayList（前提是这些对比是在数据量很大或者操作很繁琐的情况下）。LinkedList内部值可以为null，但是当我们调用值为null的元素的时候会出现NullPointerException。 LinkedList更适合于以下场景： I.没有大量的随机访问操作。 II.有大量的add/remove操作。 概括起来大概是这个样子： ArrayList和Vector它们底层实现为数组，值可为null， ArrayList不支持并发，Vector支持并发； LinkedList底层基于双链表，因此在add/remove元素时比ArrayList要快（注意前提）。 二.详解ArrayList 先来看看ArrayList的源码 ArrayList源码，中文注释 我们可以看到ArrayList继承了AbstractList，并且实现了List, RandomAccess, Cloneable, Serializable接口，ArrayList是一个可变大小的数组。它提供了很多方法：size, isEmpty, get, set, listIterator，add，addAll等等。 我们来分析一下下面的代码： 复制代码 1 List arrList = new ArrayList(); 2 System.out.println(arrList.size());//输出：0 3 arrList.add("hongten"); 4 System.out.println(arrList.size());//输出：1 复制代码 当我们创建一个ArrayList的时候，其数组大小（size）是为0，即一个空数组。当我们往数组里面添加一个元素‘hongten’后，其数组大小变为1. 这和我们之前的JDK1.5有一点区别（默认情况下，数组大小为10）。 我们new ArrayList()的时候，调用的是ArrayList的无参构造函数： ArrayList无参构造函数 JDK1.7里面ArrayList无参构造函数，默认情况下，数组为一个空数组。 复制代码 1 //无参构造函数 2 public ArrayList() { 3 super();//因为继承了AbstractList，所以调用AbstractList的构造函数 4 //这里是把数组设置为空数组对象 5 this.elementData = EMPTY_ELEMENTDATA; 6 } 复制代码 JDK1.5里面ArrayList无参构造函数，默认情况下，数组大小为10.（由于本文针对JDK1.7.0_80，所以以JDK1.7为准） 复制代码 1 //无参构造函数 2 public ArrayList() { 3 this(10); 4 } 复制代码 到这里ArrayList数据时一个空数组。其size为0. add()方法 调用add()方法，我们看一下add方法源码： 复制代码 1 //向ArrayList中添加一个元素 2 public boolean add(E e) { 3 ensureCapacityInternal(size + 1); // Increments modCount!! 4 elementData[size++] = e; 5 return true; 6 } 复制代码 首先我们把参数‘hongten’传递给add()方法，该方法做了两件事情：1.检查数组大小，看看是否需要扩容。2.把对象加入到数组里面，然后返回。 这里的size我们知道是为1的。那么size+1=0+1=1作为参数传递给ensureCapacityInternal()方法。 ensureCapacityInternal()方法 我们来看看ensureCapacityInternal()方法： 复制代码 1 　　//默认数组大小为10 2 private static final int DEFAULT_CAPACITY = 10; 3 4 private void ensureCapacityInternal(int minCapacity) { 5 //初始化时候，elementData是为空数组对象EMPTY_ELEMENTDATA，所以会去设置minCapacity的值 6 if (elementData == EMPTY_ELEMENTDATA) { 7 //设置minCapacity值，比较minCapacity和默认容量（DEFAULT_CAPACITY=10） 8 //把最大值赋值给minCapacity 9 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 10 } 11 //确定明确的容量大小 12 ensureExplicitCapacity(minCapacity); 13 } 复制代码 原来在这个方法里面用到了DEFAULT_CAPACITY=10，所以，最后的minCapacity=10，并且作为参数传递给了ensureExplicitCapacity()方法。 ensureExplicitCapacity()方法 我们接着来看看ensureExplicitCapacity()方法： 复制代码 1 //确定明确的容量大小 2 private void ensureExplicitCapacity(int minCapacity) { 3 modCount++; 4 5 // overflow-conscious code 6 if (minCapacity - elementData.length > 0) 7 grow(minCapacity); 8 } 复制代码 modCount是继承自AbstractList的，主要用于Iterator()和listIterator()方法。接下来是判断minCapacity和elementData.length的大小，由于minCapacity=10，elementData现在还是空数组，所以elementData.length=0，所以是if(true)的情况。需要执行grow()方法。 grow()方法 那么grow()方法是什么样的呢？ 复制代码 1 //最大数组大小=Integer.MAX_VALUE - 8 2 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 3 4 //扩容方法 5 private void grow(int minCapacity) { 6 //此时因为elementData为空数组，那么oldCapacity=0 7 int oldCapacity = elementData.length; 8 //newCapacity = 0 + (0 >> 1) = 0 + 0 = 0 9 int newCapacity = oldCapacity + (oldCapacity >> 1); 10 //0-10=-10<0 --> true 11 if (newCapacity - minCapacity < 0) 12 //newCapacity=10 13 newCapacity = minCapacity; 14 //10-MAX_ARRAY_SIZE = -Integer.MAX_VALUE+18<0 --> false 15 if (newCapacity - MAX_ARRAY_SIZE > 0) 16 newCapacity = hugeCapacity(minCapacity); 17 //现在才初始化数组 18 elementData = Arrays.copyOf(elementData, newCapacity); 19 } 复制代码 我们发现JDK1.7.0_80和JDK1.5的区别在于此。他们初始化数组的时间不同。 JDK1.5在创建ArrayList的时候就初始化了数组，然而，JDK1.7是在这里开始初始化数组。 Arrays.copyOf()方法 那么接下来的Arrays.copyOf()方法就值得我们去研究了： 复制代码 1 　　public static T[] copyOf(T[] original, int newLength) { 2 //elementData此时还是空数组，newLength=10，original.getClass()-->为elementData数组类对象Object[] 3 return (T[]) copyOf(original, newLength, original.getClass()); 4 } 5 6 public static T[] copyOf(U[] original, int newLength, Class newType) { 7 //因为newType = Object[].class -->true 8 //所以copy= new Object[10]; 9 T[] copy = ((Object)newType == (Object)Object[].class) 10 ? (T[]) new Object[newLength] 11 : (T[]) Array.newInstance(newType.getComponentType(), newLength); 12 //original为空数组， copy是长度为10的数组 13 //将指定源数组中的数组从指定位置复制到目标数组的指定位置 14 System.arraycopy(original, 0, copy, 0, 15 Math.min(original.length, newLength)); 16 return copy; 17 } 复制代码 copyOf()方法返回一个长度为10的数组，然后赋值给elementData，完成ArrayList里面数组的初始化工作。 这就完成了add()方法里面的第一步操作。 第二步操作是： 数组size++，然后把参数加入到数组里面，然后返回，完成往ArrayList里面添加元素的操作。 那么这个时候的size也就是我们看到的输出结果1. remove()方法 再来看看ArrayList里面的remove()删除操作 复制代码 1 //删除指定索引值所在的对象，并返回所删除的对象 2 public E remove(int index) { 3 //先检查传入的索引是否合法 4 rangeCheck(index); 5 6 modCount++; 7 //获取到指引所在对应的数组对象 8 E oldValue = elementData(index); 9 10 int numMoved = size - index - 1; 11 if (numMoved > 0) 12 //所有对象向前移动 13 System.arraycopy(elementData, index + 1, elementData, index, numMoved); 14 //把数组最后一个元素置空，以便java虚拟机回收 15 elementData[--size] = null; // clear to let GC do its work 16 17 return oldValue; 18 } 复制代码 在进行删除操作的时候，需要把指引所指向的对象删除掉，并且把该对象以后的元素向前移动，最后返回被删除的元素。 三.详解Vector 先来看看Vector的源码 Vector源码，中文注释 我们可以看到Vector和ArrayList是否类似，Vector是一个可变大小的数组。它提供了很多方法：size,isEmpty, get, set, listIterator，add，addAll等等。 和ArrayList相比，不同之处在于Vector的很多方法都加了关键字synchronized，使得Vector具有了同步功能，支持并发。 我们来分析一下下面的代码： 当我们创建一个Vector的时候，其数组长度为10的数组，但是因为里面没有任何元素，所以我们看到第一次输出为0。当我们往数组里面添加一个元素‘hongten’后，其数组含有的元素个数变为1. 复制代码 1 　　 List myVactor = new Vector(); 2 System.out.println(myVactor.size());//输出：0 3 myVactor.add("hongten"); 4 System.out.println(myVactor.size());//输出：1 复制代码 Vector构造函数 来看看Vector的构造函数： 复制代码 1 //Vector和ArrayList一样，底层基于该数组实现 2 protected Object[] elementData; 3 //这个相当于ArrayList里面的size 4 protected int elementCount; 5 //当Vector的大小大于其容量时，Vector的容量自动增加的量。 6 protected int capacityIncrement; 7 8 //带容量和容量自动增加量的参数的构造函数 9 public Vector(int initialCapacity, int capacityIncrement) { 10 super(); 11 if (initialCapacity < 0) 12 throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); 13 //初始化数组 14 this.elementData = new Object[initialCapacity]; 15 this.capacityIncrement = capacityIncrement; 16 } 17 18 //给定容量的构造函数 19 public Vector(int initialCapacity) { 20 this(initialCapacity, 0); 21 } 22 23 //无参构造函数 24 public Vector() { 25 //初始化数组，大小为10 26 this(10); 27 } 复制代码 我们可以看到，当我们new Vector()的时候，vector里面的数组就已经被初始化了，并且数组的长度为10. add()方法 接下来调用add()方法： 复制代码 1 //向Vector中添加一个元素 2 public synchronized boolean add(E e) { 3 modCount++;//继承自AbstactList 4 //维护数组大小 5 ensureCapacityHelper(elementCount + 1); 6 //把元素加入到数组中，数组大小加1. 7 elementData[elementCount++] = e; 8 return true; 9 } 复制代码 add方法是向Vector里面添加一个元素，并且使用了关键字synchronized，支持并发。和ArrayList类似，1.维护数组大小。2.把元素添加到数组中，然后返回 ensureCapacityHelper()方法 调用ensureCapacityHelper()方法： 复制代码 1 //维护数组大小 2 private void ensureCapacityHelper(int minCapacity) { 3 //minCapacity - elementData.length = 1 - 10 = -9 < 0 --> false 4 if (minCapacity - elementData.length > 0) 5 //数组扩容 6 grow(minCapacity); 7 } 复制代码 可以看到这里，在默认情况下，添加一条记录进入到vector的时候，数组并不需要扩容。到这里，add方法的第一步完成。 接下来第二步：把元素添加到数组中，数组大小加1.并返回，完成添加元素操作。 grow()方法 当我们往vector数组里面一直加入数据，把默认的第10个数据都加满的时候，那么这个时候就需要调用grow()方法了 复制代码 1 //数组最大size 2 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 3 4 //数组扩容 5 private void grow(int minCapacity) { 6 //此时的minCapacity值为11 7 //oldCapacity= 10 8 int oldCapacity = elementData.length; 9 //因为此时capacityIncrement是为0的 10 //所以(capacityIncrement > 0) ? capacityIncrement : oldCapacity = (0>0)?0:10=0 11 //newCapacity=10+(0)=10 12 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); 13 //10-11=-1<0 --> true 14 if (newCapacity - minCapacity < 0) 15 //newCapacity = 11 16 newCapacity = minCapacity; 17 if (newCapacity - MAX_ARRAY_SIZE > 0) 18 newCapacity = hugeCapacity(minCapacity); 19 elementData = Arrays.copyOf(elementData, newCapacity); 20 } 21 22 private static int hugeCapacity(int minCapacity) { 23 if (minCapacity < 0) // overflow 24 throw new OutOfMemoryError(); 25 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; 26 } 复制代码 remove()方法 remove()方法和Arraylist里面的方法差不多，区别在于多了关键字synchronized。 复制代码 1 //删除指定索引值所在的对象，并返回所删除的对象 2 public synchronized E remove(int index) { 3 modCount++; 4 if (index >= elementCount) 5 throw new ArrayIndexOutOfBoundsException(index); 6 E oldValue = elementData(index); 7 8 int numMoved = elementCount - index - 1; 9 if (numMoved > 0) 10 //所有对象向前移动 11 System.arraycopy(elementData, index + 1, elementData, index, numMoved); 12 //把数组最后一个元素置空，以便java虚拟机回收 13 elementData[--elementCount] = null; // Let gc do its work 14 15 return oldValue; 16 } 复制代码 四.详解LinkedList 先来看看LinkedList的源码 LinkedList源码，中文注解 我们可以看到LinkedList继承了AbstractSequentialList，并且实现了List, Deque, Cloneable, Serializable接口，LinkedList底层是基于链表实现的。 所以我们必须去了解一下链表的数据结构。 在LinkedList里面定义了一个私有静态内部类Node，可以看到Node有三个成员变量，item, next, prev.从字面上理解为本身， 下一个元素，前一个元素。 复制代码 1 private static class Node { 2 //本身 3 E item; 4 //下一个元素 5 Node next; 6 //前一个元素 7 Node prev; 8 9 Node(Node prev, E element, Node next) { 10 this.item = element; 11 this.next = next; 12 this.prev = prev; 13 } 14 } 复制代码 add()方法 来看看add()方法，该方法是直接把元素放到链表尾部，然后返回。 复制代码 1 //添加元素 2 public boolean add(E e) { 3 //把该元素放到链表最后面 4 linkLast(e); 5 return true; 6 } 复制代码 linkLast()方法 把对象加入到链表的尾部，然后链表大小+1 复制代码 1 // 第一个元素的引用 2 transient Node first; 3 4 // 最后一个元素的引用 5 transient Node last; 6 7 //在链表尾部创建链接 8 void linkLast(E e) { 9 //获取最后一个元素 10 final Node l = last; 11 //创建一个一个Node对象，参数（前，本，后） 12 //前：指向链表最后一个元素，即新加入的元素的上一个元素 13 //本：指的就是新加入元素本身 14 //后：因为新加入的元素本身就是在链表最后面加入，所以，后面没有元素，则为null 15 final Node newNode = new Node<>(l, e, null); 16 //把last引用指向新创建的对象上面 17 last = newNode; 18 //如果在链表为空的情况下，first=last=null 19 if (l == null) 20 //那么第一个就是最新创建的元素 21 first = newNode; 22 else 23 //把链表最后元素的next指向创建的新元素的引用 24 l.next = newNode; 25 //链表大小+1 26 size++; 27 modCount++; 28 } 复制代码 remove()方法 根据索引移除对象，首先要判断索引是否合法，如果合法，则移除索引所指对象。 复制代码 1 //根据索引移除元素 2 public E remove(int index) { 3 checkElementIndex(index); 4 return unlink(node(index)); 5 } 复制代码 unlink()方法 unlink()方法的目的就是把即将被删除的元素从链表里面拿出来，并且维护好链表状态。 复制代码 1 //删除链表给定的元素链接 2 E unlink(Node x) { 3 //该元素本身 4 final E element = x.item; 5 //该元素下一个元素 6 final Node next = x.next; 7 //该元素上一个元素 8 final Node prev = x.prev; 9 10 //如果该元素本身就是第一个元素，即链表头部 11 if (prev == null) { 12 //那么就把first指向下一个元素引用 13 first = next; 14 } else { 15 //把前一个元素的next指向该元素的下一个元素，即跳过该元素 16 //因为该元素马上要被删除掉了 17 prev.next = next; 18 //把该元素前一个元素引用置空 19 x.prev = null; 20 } 21 22 //如果该元素本身就是最后一个元素，即链表尾部 23 if (next == null) { 24 //那么把last指向前一个元素引用 25 last = prev; 26 } else { 27 //把下一个元素的prev指向该元素的上一个元素，也是跳过该元素(