List接口源码分析

java
java

了解基本数据结构在java中很是重要，今天在这里我们来常用的List接口，以及不同的实现。

ArrayList

LinkedList

Vector

CopyOnWriteArrayList

etc…

环境：JDK1.8

接口定义

List接口定义分为：查询，修改，批量修改，比较和hash，位置访问，搜索，迭代，视图。

查询操作方法

1
2
3
4
5
6
int size(); // 返回此列表元素数量
boolean isEmpty(); // 返回此列表是否为空
boolean contains(Object o); // 返回此列表是否包含o元素
Iterator<E> iterator(); // 返回此列表迭代器
Object[] toArray(); // 返回此列表转换后的数组
<T> T[] toArray(T[] a); // 返回此列表转换后的数组范型

修改操作方法

1
2
boolean add(E e); // 添加元素到此列表中
boolean remove(Object o); // 从此列表中移除指定元素

批量修改操作方法

1
2
3
4
5
6
7
8
boolean containsAll(Collection<?> c); // 是否包含指定列表所有元素
boolean addAll(Collection<? extends E> c); // 添加指定集合所有元素到此列表中
boolean addAll(int index, Collection<? extends E> c); // 从此列表指定index插入指定集合所有元素
boolean removeAll(Collection<?> c); // 从此列表中删除指定集合中包含的所有元素
boolean retainAll(Collection<?> c); // 仅保留此列表中包含在指定集合中的元素，相当于两个集合的交集
default void replaceAll(UnaryOperator<E> operator){...} // 按照指定一元操作替换此列表中所有元素, jdk8
default void sort(Comparator<? super E> c) {...} // 按照指定比较器对此列表元素进行排序
void clear(); // 清除此列表所有元素

比较和hash

1
2
boolean equals(Object o); // 比较两个列表是否相等
int hashCode(); // 计算此列表的hash值

位置访问操作

1
2
3
E get(int index); // 从此列表中获取指定index元素
E set(int index, E element); // 从此列表指定index插入指定元素
E remove(int index); // 从此列表移除指定index元素

搜索操作

1
2
int indexOf(Object o); // 从前往后搜索指定元素的位置
int lastIndexOf(Object o); // 从后往前搜索指定元素位置

列表迭代器

1
2
ListIterator<E> listIterator(); // 返回此列表中元素的列表迭代器
ListIterator<E> listIterator(int index); // 从指定index返回此列表中元素的列表迭代器

视图

1
2
List<E> subList(int fromIndex, int toIndex); // 返回子列表视图
default Spliterator<E> spliterator() {...} // 返回可分割迭代器 splitable iterator

ArrayList实现

首先ArrayList的默认容量为10

1
private static final int DEFAULT_CAPACITY = 10;

其次定义了存储数据的数组以及数组中元素个数

1
2
transient Object[] elementData;
private int size;

从这里可以看出，我们的ArrayList底层是一个数组实现的。

我们再看看构造方法

1
2
3
public ArrayList(int initialCapacity) {...} // 指定容量大小的构造器
public ArrayList() {...} // 无参构造器
public ArrayList(Collection<? extends E> c) {...} // 指定集合构造器

构造器干了些啥呢？

其实很简单，就是一些数据初始化

  1. 初始化elementData
  2. 计算size大小，如果elementData为空，则size为默认值0

再来看看我们上面列的那些操作都干了啥？

主要看add，remove，set

1
2
3
4
5
6
7
8
9
boolean add(E e);

public boolean add(E e) {
    // 容量检查
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 设置元素
    elementData[size++] = e;
    return true;
}
  1. 计算elementData与最小容量size+1的大小
  2. 判断size+1与elementData.length大小，如果size+1 - elementData.length < 0 则不扩容，否则扩容
  3. 存放对象到elementData数组中，size并增加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
E remove(int index);

public E remove(int index) {
    // index范围检查
    rangeCheck(index);

    modCount++;
    // 获取index索引对应的元素
    E oldValue = elementData(index);

    // 计算元素位置是否移动了，并调整元素位置
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将最后一个元素设置为null
    elementData[--size] = null; // clear to let GC do its work

    // 返回index对应的元素
    return oldValue;
}
  1. index范围检查
  2. 获取elementData中index位置的元素
  3. 计算index是否小于elementData.length-1，如果是则进行一次元素位置调整。并将最后一个元素设置为null.
1
2
3
4
5
6
7
8
9
10
11
12
13
E set(int index, E element);

public E set(int index, E element) {
	// index范围检查
	rangeCheck(index);

    // 获取指定index的元素
	E oldValue = elementData(index);
    // 覆盖index的元素为新元素
	elementData[index] = element;
    // 返回旧值
	return oldValue;
}
  1. index范围检查
  2. 获取指定index的元素，并覆盖旧元素为新元素
  3. 返回旧元素

LinkedList实现

我们看看LinkedList属性

1
2
3
transient int size = 0; // 元素个数
transient Node<E> first; // 头节点
transient Node<E> last; // 尾节点

我们再来看看Node是什么？

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;
	}
}

这里我们可以看到LinkedList是使用Node节点实现，Node类似铁链的环一样，一个接着一个

再来看看构造器

1
2
public LinkedList() {}
public LinkedList(Collection<? extends E> c) {...}

指定集合构造器实际上是调用了addAll方法，这里我们直接从addAll说起

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
43
44
45
46
47
48
49
50
51
52
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    // 检查index范围
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    // 找出当前节点，与前一个节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    // 追加节点
    for (Object o : a) {
        E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        // 更新最后一个节点
        last = pred;
    } else {
        // 中间插入时，更新index节点的prev
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

解释一下public boolean addAll(int index, Collection<? extends E> c) {…}

第一种情况：

当index == size大小时，从尾部添加。

第二种情况：

当index < size大小时， 从中间插入。

我们依旧看看add，remove，set

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

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;
}
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;
}

这里还有一个Node node(int index); 这个主要是用来查询指定index的元素，时间复杂度为O(logn)

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

从这里我们可以得出以下结论

  1. ArrayList访问指定index的元素要比LinkedList快，看下面代码
1
2
3
4
ArrayList访问指定index的元素
elementData[index]
LinkedList访问指定index的元素
node(index)

Vector实现

Vector则是在ArrayList的基础上所有方法增加了synchronized关键字，是线程安全的集合。

CopyOnWriteArrayList实现

从名字可以看出CopyOnWriteArrayList的底层实现采用的数组，因为也是ArrayList。这个集合类也是线程安全的，那么我们来看看它是如何实现线程安全的。

首先在该类中增加了可重入锁

1
2
3
final transient ReentrantLock lock = new ReentrantLock();

private transient volatile Object[] array; // 数据存储

依旧，我们看看构造器

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 CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

final void setArray(Object[] a) {
    array = a;
}

上述构造器完成的就是array的初始化。

我们来看看是如何做到添加和获取做到线程安全的。

首先我们看看add方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

这里可以看到，在添加新元素的时候会采用lock锁住当前方法。然后进行copy元素到新的数组中。

包括set，remove都进行了lock操作。

我们再看看get方法

1
2
3
4
5
6
7
public E get(int index) {
    return get(getArray(), index);
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

看到没有，这里可没有加锁哦。我们再Vector中可以使用了synchronized关键字的。我们看看Vector的get。

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

    return elementData(index);
}

在CopyOnWriteArrayList的get没有加锁是因为set的原因，在set的时候。每次都会生成一个新的数组，所以get时不用加锁。

这里可以看出CopyOnWriteArrayList的写性能应该不会太高。因为每次都要生成新的数组。

最后看看有哪些List是线程安全的

1
2
3
1. 使用CopyOnWriteArrayList
2. Collections.synchronizedList(new ArrayList())
3. 使用Vector

好了，今天的分享就到这里啦。谢谢你的阅读，喜欢的话，可以打赏一下哦。

本文由 xxzkid | 我叫王也道长创作，采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用，但需署名作者且注明文章出处。
本文标题：List接口源码分析
本文链接：https://xxzkid.github.io/2019/list-source/