ArrayList、LinkedList和Vector的区别(深度解析)

前言

ArrayList、LinkedList、Vector是我们在平时开发中,面试中最频繁接触的集合类,所以了解它的实现有助于我们去在不同的需求中进行合适的选择,并且说出一些实现细节更能在面试中能够脱颖而出。可以说他是Java、Android程序员必须掌握的基础知识点。

类结构

简单的说明一下,圆圈是接口,方块是类,从类的结构中可以看到他们有哪些特点:

  • ArrayListLinkedListVector都直接或者间接的继承了AbstractList
  • 他们同时实现了List接口。
  • 对于Object的操作都在Collection接口当中
  • index的操作都在List接口当中

看到这里,我们发现除了两个接口外,最先的抽象类是AbstractList,那么我们是不是主要先研究研究AbstractList里面有什么呢?走你

AbstractList

1
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
  • Itr : 内部类,一个迭代器,可以通过iterator()返回,继承了Iterator接口,有三个方法next() hasnext() remove()
  • ListItr :内部类,一个迭代器,可以通过ListIterator()返回,继承了Itr接口,里面实现了向前查找等方法,并且支持在当迭代时候的位置增加一个值。
  • modCount参数,在调用一系列的操作的时候,都会执行++操作,来确保进行了修改
  • SubList平行类,实现了当前list的copy
  • RandomAccessSubList平行类,继承于SubList,主要用于算数

其实查看AbstractList主要的目的就是分析List的迭代器,因为其他的方法基本上都在子类被覆盖掉了。那么迭代器中,最常出现的错误就是以下异常:

ConcurrentModificationException

这个异常实际是JAVA Collection的Fast-Faile框架,如果在迭代的时候出现问题,则会抛出这个异常。

我们平时在迭代时候进行修改的操作会造成这个错误ConcurrentModificationException其实就是和AbstractList息息相关

如代码:

1
2
3
4
5
6
7
8
ArrayList<Integer> list = new ArrayList<Integer>();
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer aa = iterator.next();
if (aa == 2) {
list.remove(aa);
}
}

会抛出异常,ConcurrentModificationException这是为什么呢?

那么出现问题的地方,只是循环做了两个操作:

  • iterator.hasNext()
  • iterator.next()
  • list.remove(0)

那么我们就要观察ArrayList和其迭代器的源码了,首先看迭代器的代码:

首先通过前面我们的对参数的介绍知道,list.iterator()返回的是Itr,它是AbstractList的一个内部类

1
2
3
public Iterator<E> iterator() {
return new Itr();
}

Itr有三个成员变量

1
2
3
int cursor = 0;//指向下一个位置的标记
int lastRet = -1;//指向上一次的标记
int expectedModCount = modCount;//将AbstractList的当前修改标记附加到Itr的当前修改标记上

另外两个主要的方法

1
2
3
public boolean hasNext() {
return cursor != size();//没干嘛就是看看有没有下一个
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);//获取当前的元素
lastRet = i;//附加给一个下标,表示上一个元素
cursor = i + 1;//相应的,cursor指向下一个元素
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

相信大家对hasNext()的理解没有什么问题,那么next()主要是干什么了?

前面有一行代码checkForComodification(),先判断了modCountexpectedModCount是否相等,如果相等的话就向下执行,然后根据当前的cursor拿到当前的元素,然后cursor指向下个位置,返回得到的元素。

我们发现迭代的时候modCountexpectedModCount都没有改变,但是抛出异常了,就肯定有一个变了

还剩最后一个嫌疑犯,就是List.remove()

看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
public E remove(int index) {
rangeCheck(index);
modCount++;//自增操作
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;

return oldValue;
}

看注释的哪一行就理解了

因为removemodCount自增了,在迭代器中的next检查时由于expectedModCount没有改变,因此会抛出异常。

这样设计的目的在《Java并发编程》一书中介绍过,是为了防止多线程下,多个线程修改List从而造成的数据错乱,从而得到不正确的结果。

其实很好理解,在修改的列表时候自增,在迭代列表的时候检查modCount,就可以判断出这个列表在迭代的时候有没有被其他线程修改。

如何避免ConcurrentModificationException

细心的朋友可以发现在迭代器中有一个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}

他在移除了元素后,还会更新expectedModCount,就不会造成异常了。

这是Java为了避免并发线程的情况下对其修改,舍弃了原有迭代中的移除,但是为了让单线程也能够移除而增加的方法。

那么我们改造一下原来的代码

1
2
3
4
5
6
7
8
ArrayList<Integer> list = new ArrayList<Integer>();
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer aa = iterator.next();
if (aa == 22) {
iterator.remove();
}
}

ArrayList

从这里开始我们介绍各个列表集合类的实现,主要研究他们的六个方面

  1. 数据结构
  2. 线程安全性:什么情况下可以在多线程下使用
  3. 时间复杂度:对什么类型的操作用什么样的列表集合
  4. 空间复杂度:对什么类型的操作用什么样的列表集合
  5. 扩容:占用内存的大小
  6. 是否允许添加空对象:空指针异常

我们从介绍方法,逐渐引入说明其各种特性:

get

1
2
3
4
5
6
7
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}

get方法很简单,就是从当前的数组中拿到对应的值,在计算的过程中没有产生额外的空间,并且一次性获取。

时间复杂度为O(1),空间复杂度为O(1)

但是,由于在获取的过程中没有进行加锁,多线程下,如果有数据修改,可能获取的数据不一样,因此线程安全性为不安全

set

1
2
3
4
5
6
7
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

简单的不想说话,时间复杂度O(1),空间复杂度O(1),线程不安全。

add

add有两个方法一个是增加一个节点,一个是在指定位置上增加一个节点

1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

不考虑扩容,其时间复杂度为O(1),空间复杂度为O(1),线程不安全

1
2
3
4
5
6
7
8
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

考虑 System.arraycopy,其时间复杂度为O(n),空间复杂度为O(n),线程不安全

深复制和浅复制

  • 深复制:如果复制的是基本类型,那么修改其值不会改变原有的值。
  • 浅复制:如果复制的是引用类型,那么修改其值会改变原有值(二维数组的维度里面也是引用类型)。

System.arraycopy

关于System.arraycopy为 JVM 内部固有方法,它通过手工编写汇编或其他优化方法来进行 Java 数组拷贝,这种方式比起直接在 Java 上进行 for 循环或 clone 是更加高效的。数组越大体现地越明显。

它的五个参数分别是

  • src:源数组
  • srcPos:源数组起始位置,复制源数组的(srcPos+length-1)
  • dest:目标数组
  • destPos:目标数组起始位置,复制目标数组的(destPos+length-1)
  • length:复制的长度
1
2
3
 System.arraycopy(elementData, index, elementData, index + 1,size - index);
//复制本数组起始位置index位置之后的数据,到本数组的index+1以及以后的数据,复制大小为从index到数组的最后
//结果:空出来index的位置。

首先我们不考虑native层的和扩容,我们直接在数组里面加一个,直接执行在数组的一个位置上进行赋值操作

时间复杂度O(1),空间复杂度O(1),线程安全性不安全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};

//判断大小方法
private void ensureCapacityInternal(int minCapacity) {
//如果是一个空数组,就用默认的数组大小和需要增加的数组大小中取一个最大的-扩容能力。
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容?
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果计算出来的扩容能力比当前的数组长度大的话,就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
// 扩容大小为计算出来的扩容大小的一半。
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//将旧数组扩容到新的大小中
elementData = Arrays.copyOf(elementData, newCapacity);
}

这里就是ArrayList的扩容机制。原始大小为10,扩容长度为(原始长度+需要扩容的大小)/2,如果需要扩容最终会执行Arrays.copyOf(elementData, newCapacity);它的实现其实也是System.arraycopy()

回头看add方法,如果考虑扩容和复制的话System.arraycopy()不管是复制基本类型还是引用类型,在native层会遍历整个数组来进行赋值,时间复杂度为O(n),扩容的时间复杂度为O(n),总体就是O(2n)。

remove

这里我们介绍两个方法

  • remove(int index)
  • remove(Object o)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

从开始的UML图我们知道remove实现了List的一个方法。其和add类似,这里不做多的分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}

注意:我们之前没有注意传入空值,但是这里发现其判断了空值的传入,并且是允许的,因此,ArrayList允许传入空值。

不考虑System.arraycopy的情况下,时间复杂度O(n),空间复杂度为O(1),线程安全。

考虑System.arraycopy的话,时间复杂度为O(n的平方),空间复杂度为O(n)

SubList

Arraylist的子类,可以获取ArrayList其中的一段,并且它的改动会影响ArrayList

LinkedList

我们首先看分析下它的数据结构

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;

Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

可以看出来他是一个双向链表,指向前后节点

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
transient int size = 0;

/**
* 指向头结点
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* 指向尾节点
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}
}

获取的时候,首先会判断index在节点的位置,如果是前半段,则从前往后挨个查找,如果是在后半段,则从后往前查找。

时间复杂度为O(n/2),空间复杂为O(n/2),线程安全性为不安全。

set

1
2
3
4
5
6
7
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

与get一样,还是先拿到了index上的位置的Node,并且将其位置上的值

因此时间复杂度和空间复杂度与add一样

时间复杂度为O(n/2),空间复杂为O(n/2),线程安全性为不安全。

add

add也分析两个方法第一个直接增加节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

由于加到了尾节点,时间复杂度O(1),空间复杂度O(1),线程安全性不安全,并且可以看出,其使用了和ArrayList同样的并发错误防护措施modCount++

并且这里没有判断空,因此如果泛型是引用类型,可以设置为空

第二个在指定的位置add

1
2
3
4
5
6
7
8
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}

不考虑尾巴节点,用到了node(index)方法时间复杂度为O(n/2),空间复杂为O(1),线程安全性为不安全。

remove

和ArrayList一样我们分析两个remove,首先从remove(index)开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

这里也用到了node,因此时间复杂度和空间复杂度和getset一样

时间复杂度为O(n/2),空间复杂为O(n/2),线程安全性为不安全。

我们来看另一个remove(object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

有没有很眼熟?对,和ArrayList的是一样的

时间复杂度为O(n),空间复杂度为O(1),线程不安全

Other

只剩下一个需要分析的情况了,那就是扩容,但是它是一个双向链表,因此不需要扩容

前面我们有说到,modCount++这一变量的出现,那么在其内部类中,一定也有类似于Arraylist的迭代功能,果然在类的最后发现了ItrListItr两个私有的内部类,关于他们的实现,在AbstractList中有提到

Vector

成员变量

  • elementData:Object[]
  • elementCount:int
  • capacityIncrement:int

很明显它的实现也是数组加链表的结构,那么它和ArrayList有什么区别呢?

在成员变量中,我们没有发现数组初始大小的信息,但是我们从它的构造中,找到了默认的数组大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Vector() {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}

默认情况下,它会构造一个大小为10的数组,并且指定它的扩容能力为0,这个0就说明不扩容了吗?我想应该在add里面可以找到答案,但是我们还是根据之前的顺序来解析它的各个方法。

get

1
2
3
4
5
6
7
8
9
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);

return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}

我们终于看到了synchronized关键字,由此可见,其是线程安全的,但是如果使用不当它也不是线程安全的,关于为什么我会在Vector的最后解释。

ArrayListget一样时间复杂度O(1),空间复杂度O(1),线程安全。

set

1
2
3
4
5
6
7
8
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

时间复杂度O(1),空间复杂度O(1),线程安全。

add

首先来看直接增加节点:

1
2
3
4
5
6
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}

如果不考虑扩容的话,时间复杂度为O(1),空间复杂度O(1),线程安全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private void ensureCapacityHelper(int minCapacity) {
//超出原来大小进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
//原数组的大小
int oldCapacity = elementData.length;
//新数组大小
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//然后进行了arraycopy
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

看下扩容,果然capacityIncrement会在扩容的时候出现,

  • 那么其大小如果指定的话,扩容大小为扩容能力的大小
  • 如果没有指定,扩容为原数组的一倍。

并且,如果我们考虑Array.copy的话,时间复杂度为O(n),空间复杂度为O(1),线程安全

再来看另一个add方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void add(int index, E element) {
insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}

时间复杂度的分析和ArrayList一样,时间复杂度O(n),空间复杂度O(n),线程安全性为安全。

remove

两个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);

int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work

return oldValue;
}

不考虑数组拷贝的情况下,时间复杂度O(n),空间复杂度O(n),线程安全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}

public synchronized int indexOf(Object o, int index) {
if (o == null) {
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}

不考虑System.arraycopy的情况下,时间复杂度O(n),空间复杂度为O(1),线程安全。

考虑System.arraycopy的情况下,时间复杂度O(n的平方),空间复杂度为O(n),线程安全。

线程安全性

这里主要讨论之前遗留的一个问题。

加了Synchoriezd一定是线程安全吗?如果使用不当,还是会出现线程安全性问题。

Synchoriezd不一定安全

比如:

提供这样两个方法

1
2
3
4
5
6
7
8
9
public Object getLast(Vector v){
int last = v.size()-1;
return v.get(last);
}

public Object removeLast(Vector v){
int last = v.size()-1;
return v.remove(last);
}

如果对一个对象操作,一个线程调用getLast另一个线程调用removelast,有可能出现一种情况:

  • a线程 ,last = 10;
  • b线程 ,last =10;
  • b线程,remove成功;
  • a线程,get(10)失败。

我们再来回顾一下get方法

1
2
3
4
5
6
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);

return elementData(index);
}

这里很明显,是会抛出异常的。

因此,Synchoriezd并不能保证其线程安全性,那么我们可以有两种方式来解决这个问题:

  1. 在进行一些复合操作的时候,加锁—就是给getlastremovelast两个方法加锁。
  2. 使用并发集合类,有这类的复合操作,就不需要自己定义了同步方法或者同步块了。

总结

我们之前想了用六个维度来区分他们的区别分别是:

  1. 数据结构
  2. 线程安全性:什么情况下可以在多线程下使用
  3. 时间复杂度:对什么类型的操作用什么样的列表集合
  4. 空间复杂度:对什么类型的操作用什么样的列表集合
  5. 扩容:占用内存的大小
  6. 是否允许添加空对象:空指针异常

我们对他们逐一分析

数据结构

ArrayList LinkedList Vector
数组 双向链表 数组

线程安全性

ArrayList LinkedList Vector
线程不安全 线程不安全 线程相对安全(使用得当)
  • ArrayListLinkdList都没有使用锁,线程不安全。

  • Vector使用了对象锁,可以保证每个Vector实例都能够顺序的执行。

  • 他们都有modCount这一参数,用来保证他们迭代的时候不会被篡改。(可以使用迭代器来执行add,remove操作,这些操作是作用在本身对象上的,如:ArrayList本身)

时间复杂度

方法\集合类 ArrayList LinkedList Vector
get(int index) O(1) O(n/2) O(1)
set(int index, E element) O(1) O(n/2) O(1)
add(E element) O(1) O(1) O(1)
add(int index, E element) O(n) O(n/2) O(n)
remove(int index) O(n) O(n/2) O(n)
remove(E element) O(n的平方) O(n) O(n的平方)

刚开始我还在想计算时间复杂度需要不需要考虑扩容和,但是业内一般不讲这一点考虑进来,如果大家为了标准化,可以考虑这点,在之前都有介绍。

ArrayList和Vector的时间复杂度评判算上了System.arraycopy()

  • LinkedList至于为什么为O(n/2),是因为LinkedList里面的node方法会判断是前半段还是后半段,其实是遍历了一半。
  • 他们remove(E element)的时间复杂度都是O(n),是因为他们都遍历了所有的元素。但是考虑System.arraycopy的话ArrayListVector的移动大小为O(n的平方)
  • 网上有很多人说LinkedListremove(int index)的时间复杂度是O(1),我想他们没有注意到里面的node方法吧。
  • 凡是LinkedList的方法涉及到index 参树,时间复杂度都是O(n/2),也是因为用了node方法。

空间复杂度

方法\集合类 ArrayList LinkedList Vector
get(int index) O(1) O(1) O(1)
set(int index, E element) O(1) O(1) O(1)
add(E element) O(1) O(1) O(1)
add(int index, E element) O(1) O(1) O(1)
remove(int index) O(1) O(1) O(1)
remove(E element) O(n) O(n) O(n)

空间复杂度还需要大家注意,本人对这一概念的理解力可能不够,如有问题,希望大家指正。

扩容机制

  • ArrayList:
    • 默认的数组大小为10,默认扩容阈值为0.75 (3/4)
    • 每一次扩容为:(原有数组大小+扩容增的数组大小)/2
    • 可以通过构造函数传递默认大小和扩容阈值
  • LinkedList:
    • 默认大小为0
    • 由于使用双向链表的数据结构,不需要扩容能力,直接向后面添加。
  • Vector:
    • 参数中没有数组的默认大小和阈值,只有在默认的构造中,有一个数组的初始化大小为10
    • 如果没有指定每一次扩容的大小,扩容大小为原来的一倍

是否允许加入空对象

ArrayList LinkedList Vector
允许对象为空 允许对象为空 允许对象为空

这一点从他们的remove(Objec o)中可以看出来,他们都允许对象为空,因为都有这一步操作:

如果对象为空,就遍历第一个出现的空对象,返回其位置

最后

以上就是对他们三者的分析,希望大家能够满意,以后今后在实际运用中和面试中,不管涉及到什么集合类,都可以从这六个角度去进行分析,这是我总结出来的一些对比角度,如果大家有其他对比的角度,欢迎联系我来一起完善。谢谢大家。

写作不易,还请鼓励。

参考

System.arraycopy为什么快

谢谢您的鼓励~