ArrayList, LinkedList, Vector - dudu：史上最详解

发布时间：2020-12-14 06:32:17 所属栏目：Java 来源：网络整理

导读：p style="text-align: center;"ArrayList,LinkedList,Vector - dudu：史上最详解我们来比较一下ArrayList， LinkedLIst和Vector它们之间的区别。BZ的JDK版本是1.7.0_80 经常在面试的时候，或者在大家做project的时候，都会被它们的区别产生疑惑。或者对它们

<p style="text-align: center;">ArrayList,LinkedList,Vector - dudu：史上最详解

我们来比较一下ArrayList， LinkedLIst和Vector它们之间的区别。BZ的JDK版本是1.7.0_80

经常在面试的时候，或者在大家做project的时候，都会被它们的区别产生疑惑。或者对它们的用法并不是很了解。那么我们今天就来看看他们的区别和用法。

以下是本文的大纲：

一.ArrayList，LinkedList和Vector的区别

二.详解ArrayList

三.详解Vector

四.详解LinkedList

五.在并发情况下，怎样使用它们

若有不正之处，还请多多谅解，并希望批评指正。

请尊重作者劳动成果，转发请标明blog地址

一.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 AbstractList List serialVersionUID = 8683452581122892189L DEFAULT_CAPACITY = 10 Object[] EMPTY_ELEMENTDATA = ArrayList( (initialCapacity < 0 IllegalArgumentException("Illegal Capacity: " + .elementData = .elementData = ArrayList(Collection E> elementData = size = (elementData.getClass() != Object[]. elementData = Arrays.copyOf(elementData,size,Object[]. modCount++ (size < elementData = ensureCapacity( minExpand = (elementData != ? 0 (minCapacity > ensureCapacityInternal( (elementData == minCapacity = ensureExplicitCapacity( modCount++ (minCapacity - elementData.length > 0 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 grow( oldCapacity = newCapacity = oldCapacity + (oldCapacity >> 1 (newCapacity - minCapacity < 0 newCapacity = (newCapacity - MAX_ARRAY_SIZE > 0 newCapacity = elementData = hugeCapacity( (minCapacity < 0) (minCapacity > MAX_ARRAY_SIZE) ? size == 0 indexOf(o) >= 0 (o == ( i = 0; i < size; i++ (elementData[i] == } ( i = 0; i < size; i++ -1 (o == ( i = size - 1; i >= 0; i-- (elementData[i] == } ( i = size - 1; i >= 0; i--

我们可以看到ArrayList继承了AbstractList，并且实现了List,Serializable接口，ArrayList是一个可变大小的数组。它提供了很多方法：size,isEmpty,get,set,listIterator，add，addAll等等。

我们来分析一下下面的代码：

List arrList = ArrayList System.out.println(arrList.size()); arrList.add("hongten" System.out.println(arrList.size());

当我们创建一个ArrayList的时候，其数组大小（size）是为0，即一个空数组。当我们往数组里面添加一个元素‘hongten’后，其数组大小变为1.

这和我们之前的JDK1.5有一点区别（默认情况下，数组大小为10）。

我们new ArrayList()的时候，调用的是ArrayList的无参构造函数：

ArrayList无参构造函数

JDK1.7里面ArrayList无参构造函数，默认情况下，数组为一个空数组。

(); .elementData = }

JDK1.5里面ArrayList无参构造函数，默认情况下，数组大小为10.（由于本文针对JDK1.7.0_80，所以以JDK1.7为准）

(10 }

到这里ArrayList数据时一个空数组。其size为0.

add()方法

调用add()方法，我们看一下add方法源码：

ensureCapacityInternal(size + 1); elementData[size++] = }

首先我们把参数‘hongten’传递给add()方法，该方法做了两件事情：1.检查数组大小，看看是否需要扩容。2.把对象加入到数组里面，然后返回。

这里的size我们知道是为1的。那么size+1=0+1=1作为参数传递给ensureCapacityInternal()方法。

ensureCapacityInternal()方法

我们来看看ensureCapacityInternal()方法：

　　 DEFAULT_CAPACITY = 10 ensureCapacityInternal( (elementData == minCapacity = }

?原来在这个方法里面用到了DEFAULT_CAPACITY=10，所以，最后的minCapacity=10，并且作为参数传递给了ensureExplicitCapacity()方法。

ensureExplicitCapacity()方法

我们接着来看看ensureExplicitCapacity()方法：

ensureExplicitCapacity( modCount++ (minCapacity - elementData.length > 0 }

modCount是继承自AbstractList的，主要用于Iterator()和listIterator()方法。接下来是判断minCapacity和elementData.length的大小，由于minCapacity=10，elementData现在还是空数组，所以elementData.length=0，所以是if(true)的情况。需要执行grow()方法。

grow()方法

那么grow()方法是什么样的呢？

MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 grow( oldCapacity = > 1) = 0 + 0 = 0 newCapacity = oldCapacity + (oldCapacity >> 1 true (newCapacity - minCapacity < 0 newCapacity = false (newCapacity - MAX_ARRAY_SIZE > 0 newCapacity = elementData = }

我们发现JDK1.7.0_80和JDK1.5的区别在于此。他们初始化数组的时间不同。

JDK1.5在创建ArrayList的时候就初始化了数组，然而，JDK1.7是在这里开始初始化数组。

Arrays.copyOf()方法

那么接下来的Arrays.copyOf()方法就值得我们去研究了：

　　 T[] copyOf(T[] original, 为elementData数组类对象Object[] T[] copyOf(U[] original, newLength,Class T[]> true T[] copy = ((Object)newType == (Object)Object[]. ? (T[]) System.arraycopy(original,copy, }

copyOf()方法返回一个长度为10的数组，然后赋值给elementData，完成ArrayList里面数组的初始化工作。

这就完成了add()方法里面的第一步操作。

第二步操作是：

数组size++，然后把参数加入到数组里面，然后返回，完成往ArrayList里面添加元素的操作。

?那么这个时候的size也就是我们看到的输出结果1.

remove()方法

再来看看ArrayList里面的remove()删除操作??

E remove( modCount++ E oldValue = numMoved = size - index - 1 (numMoved > 0 System.arraycopy(elementData,numMoved); elementData[--size] = ; }

在进行删除操作的时候，需要把指引所指向的对象删除掉，并且把该对象以后的元素向前移动，最后返回被删除的元素。

三.详解Vector

?先来看看Vector的源码

Vector AbstractList List Vector( initialCapacity, (initialCapacity < 0 IllegalArgumentException("Illegal Capacity: " + .elementData = .capacityIncrement = Vector( (initialCapacity,0 (10 Vector(Collection E> elementData = elementCount = (elementData.getClass() != Object[]. elementData = Arrays.copyOf(elementData,elementCount,Object[]. modCount++ oldCapacity = (elementCount < elementData = ensureCapacity( (minCapacity > 0 modCount++ ensureCapacityHelper( (minCapacity - elementData.length > 0 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 grow( oldCapacity = newCapacity = oldCapacity + ((capacityIncrement > 0) ? (newCapacity - minCapacity < 0 newCapacity = (newCapacity - MAX_ARRAY_SIZE > 0 newCapacity = elementData = hugeCapacity( (minCapacity < 0) (minCapacity > MAX_ARRAY_SIZE) ? setSize( modCount++ (newSize > } ( i = newSize; i < elementCount; i++ elementData[i] = elementCount = elementCount == 0 indexOf(o,0) >= 0 indexOf(o,0 indexOf(Object o, (o == ( i = index; i < elementCount; i++ (elementData[i] == } ( i = index; i < elementCount; i++ -1

我们可以看到Vector和ArrayList是否类似，Vector是一个可变大小的数组。它提供了很多方法：size,listIterator，add，addAll等等。

和ArrayList相比，不同之处在于Vector的很多方法都加了关键字synchronized，使得Vector具有了同步功能，支持并发。

我们来分析一下下面的代码：

当我们创建一个Vector的时候，其数组长度为10的数组，但是因为里面没有任何元素，所以我们看到第一次输出为0。当我们往数组里面添加一个元素‘hongten’后，其数组含有的元素个数变为1.

　　 List myVactor = Vector System.out.println(myVactor.size()); myVactor.add("hongten" System.out.println(myVactor.size());

Vector构造函数

来看看Vector的构造函数：

Vector( initialCapacity, (initialCapacity < 0 IllegalArgumentException("Illegal Capacity: " + .elementData = .capacityIncrement = Vector( (initialCapacity,0 (10 }

我们可以看到，当我们new Vector()的时候，vector里面的数组就已经被初始化了，并且数组的长度为10.

add()方法

接下来调用add()方法：

modCount++; ensureCapacityHelper(elementCount + 1 elementData[elementCount++] = }

add方法是向Vector里面添加一个元素，并且使用了关键字synchronized，支持并发。和ArrayList类似，1.维护数组大小。2.把元素添加到数组中，然后返回

ensureCapacityHelper()方法

调用ensureCapacityHelper()方法：

ensureCapacityHelper( false (minCapacity - elementData.length > 0 }

可以看到这里，在默认情况下，添加一条记录进入到vector的时候，数组并不需要扩容。到这里，add方法的第一步完成。

接下来第二步：把元素添加到数组中，数组大小加1.并返回，完成添加元素操作。

grow()方法

当我们往vector数组里面一直加入数据，把默认的第10个数据都加满的时候，那么这个时候就需要调用grow()方法了

MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 grow( oldCapacity = 0) ? capacityIncrement : oldCapacity = (0>0)?0:10=0 newCapacity = oldCapacity + ((capacityIncrement > 0) ? true (newCapacity - minCapacity < 0 newCapacity = (newCapacity - MAX_ARRAY_SIZE > 0 newCapacity = elementData = hugeCapacity( (minCapacity < 0) (minCapacity > MAX_ARRAY_SIZE) ? }

?remove()方法

remove()方法和Arraylist里面的方法差不多，区别在于多了关键字synchronized。

E remove( modCount++ (index >= E oldValue = numMoved = elementCount - index - 1 (numMoved > 0 System.arraycopy(elementData,numMoved); elementData[--elementCount] = ; }

四.详解LinkedList

?先来看看LinkedList的源码

LinkedList AbstractSequentialList List,Deque size = 0 Node Node LinkedList(Collection E> Node f = Node newNode = Node<>( first = (f == last = f.prev = size++ modCount++ Node l = Node newNode = Node<>(l, last = (l == first = l.next = size++ modCount++ linkBefore(E e,Node Node pred = Node newNode = Node<> succ.prev = (pred == first = pred.next = size++ modCount++ E unlinkFirst(Node E element = Node next = f.item = f.next = ; first = (next == last = next.prev = size-- modCount++ E unlinkLast(Node E element = Node prev = l.item = l.prev = ; last = (prev == first = prev.next = size-- modCount++ E unlink(Node E element = Node next = Node prev = (prev == first = } prev.next = x.prev = (next == last = } next.prev = x.next = x.item = size-- modCount++ Node f = (f == Node l = (l == Node f = (f ==

我们可以看到LinkedList继承了AbstractSequentialList，并且实现了List,Deque,Serializable接口，LinkedList底层是基于链表实现的。

所以我们必须去了解一下链表的数据结构。

在LinkedList里面定义了一个私有静态内部类Node，可以看到Node有三个成员变量，item,next,prev.从字面上理解为本身，下一个元素，前一个元素。

Node Node Node Node(Node prev,Node .item = .next = .prev = }

add()方法

来看看add()方法，该方法是直接把元素放到链表尾部，然后返回。

}

linkLast()方法

把对象加入到链表的尾部，然后链表大小+1

Node Node Node l = Node newNode = Node<>(l, last = (l == first = l.next = size++ modCount++ }

remove()方法

根据索引移除对象，首先要判断索引是否合法，如果合法，则移除索引所指对象。

E remove( }

unlink()方法

unlink()方法的目的就是把即将被删除的元素从链表里面拿出来，并且维护好链表状态。

E unlink(Node E element = Node next = Node prev = (prev == first = } prev.next = x.prev = (next == last = } next.prev = x.next = x.item = size-- modCount++ }

五.在并发情况下，怎样使用它们

?类部类MyThread继承了Thread类，并且重写了run()方法。在MyThread里面定义了4个static变量，这些变量是为了存放线程在运行过程中向里面添加元素的值。

main(String[] args) ExecutorService exec = exec.execute( exec.execute( exec.execute( exec.execute( exec.execute( exec.execute( exec.execute( exec.execute( exec.execute( System.out.println("begin..." TimeUnit.SECONDS.sleep(2 List myArrayList = List myLinkedList = List myVector = List mySynchronziedArrayList = (myArrayList != && myArrayList.size() > 0 System.out.println("ArrayList: " + (myVector != && myVector.size() > 0 System.out.println("vector: " + (mySynchronziedArrayList != && mySynchronziedArrayList.size() > 0 System.out.println("SynchronziedArrayList: " + (myLinkedList != && myLinkedList.size() > 0 System.out.println("linkedList: " + System.out.println("end..." MyThread List myArrayList = ArrayList List myLinkedList = LinkedList List myVector = Vector List mySynchronziedArrayList = Collections.synchronizedList( ArrayList ( i = 0; i < 10; i++ TimeUnit.MILLISECONDS.sleep(2 System.out.println(Thread.currentThread().getName() + " add value " + }

之后我们从结果可以看到：

ArrayList：值可以为null，线程不安全，但是我们可以使用Collections.synchronzedList()方法使得一个ArrayList支持并发。

Vector：本身支持并发。

LinkedList：值可以为null，但是当我们调用时会抛出NullPointerException异常。

========================================================