Java容器系列-LinkedList源码分析

LinkedList 作为 List 的另一种实现,也非常的经典。与 ArrayList 不同,LinkedList 底层使用的是双向链表来实现的,具体类图如下:

相比于 ArrayList,LinkedList 继承了 AbstractSequentialList 类,而且实现了 Deque 接口,RandomAccess 接口就被没有实现。

但在实际的使用当中,LinkedList 使用的并没有 ArrayList 多,LinkedList 可以被当做队列和栈来使用,但是 BlockingQueue 使用的比它更为广泛,因为一般使用队列的地方都会涉及到比较高的并发,在高并发的情况下,BlockingQueue 比 LinkedList 更好用,BlockingQueue 以后会写专门的文章来介绍。

本文基于 JDK1.8

成员变量

LinkedList 的结构比 ArrayList 更简单,核心的成员变量如下,size 记录当前元素的个数,first 指向头结点,last 指向尾节点。

1
2
3
transient int size = 0;
transient Node<E> first;
transient Node<E> last;

Node 的代码如下,通过泛型来存储具体的元素,每个节点都可以获取前一个或者后一个节点,所以 LinkedNode 底层数据结构是双向链表

1
2
3
4
5
6
7
8
9
10
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 的容量是没有限制的,自然也没有了扩容的过程。

实例化过程

LinkedList 的实例化过程也相对简单,只提供了两个构造函数。

一个不带任何参数,也不需要做任何的数据初始化,头结点和尾节点的初始化都放在添加第一个元素的时候。

1
2
public LinkedList() {
}

第二个构造函数接收一个 Collection 类型的对象,会把对象中的所有元素都添加到当前 LinkedList 对象中。

1
2
3
4
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

具体实现

与 ArrayList 相比,LinkedList 有如下特点:

  • 不能随机访问
  • 容量无限
  • 可以用作队列双向队列

因为 LinkedList 没有实现 RandomAccess 接口,再加上本身底层的数据结构是双向链表,所以对链表中的元素不能随机访问,只能按照顺序访问。

而且对于链表来说,元素时可以无限扩展(理论上)的,所以 LinkedList 的容量也没有上限。

从 JDK1.6 开始,LinkedList 实现了 Deque 接口,这就表明 LinkedList 可以用作队列或者双向队列

增删改查方法

List 中有的方法,LinkedList 中都实现了。

可以添加元素:

1
2
3
4
public boolean add(E e) {
linkLast(e);
return true;
}

可以看到,添加元素的操作实际上是用 linkLast() 方法来完成的,在添加元素的过程中,如果发现头结点为空,那说明是添加第一个元素,只需要把头结点指向刚添加的节点就可以,以下代码是在尾部添加一个节点:

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

上面是把元素添加到链表的尾部,因为 LinkedList 还可以被用作队列和栈,因此还提供了从头部添加元素的方法:

1
2
3
4
5
6
7
8
9
10
11
 private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}

既然有添加元素的操作,也有删除元素的操作,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private E unlinkLast(Node<E> l) {
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null;
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}

清空 LinkedList 就是把所有的元素置为 null:

1
2
3
4
5
6
7
8
9
10
11
12
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}

从以上代码可以发现,LinkedList 的操作都是对链表的操作。

用作队列和栈

做为普通队列时,可以在队列中进行入队和出队的操作。从队列头部获取一个元素,但是不删除元素 peek():

1
2
3
4
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

从队列头部获取一个元素并删除,poll():

1
2
3
4
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

在队列的尾部添加一个元素,offer():

1
2
3
public boolean offer(E e) {
return add(e);
}

普通队列只可以在一端入队,在另一端出队,但是对于双向队列,可以在两端执行入队和出队操作。

所以在在作为双向队列时,拿 peek 操作来说即可以 peekFirst() 也可以 peekLast()。其他的操作例如 offer、poll 同样类似。

LinkedList 中还有 push()pop() 操作。被当做栈使用时,只需要对头部节点进行操作就行。

入栈操作:

1
2
3
public void push(E e) {
addFirst(e);
}

出栈操作:

1
2
3
public E pop() {
return removeFirst();
}

其他功能

LinkedList 中也实现了 ListIterator 和 Spliterator 接口。

所以 LinkedList 也可以从两端进行遍历。在遍历的时候,同样也有 fail-fast 机制来检查遍历的过程当中,容器中的元素是否被修改。

在实现 Spliterator 接口之后,也可以对容器中的元素进行分段,然后同时让多个线程同时进行处理,提高处理效率。分割 LinkedList 的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
LinkedList<Integer> list = new LinkedList<>();

for (int i = 0; i < 20; i++) {
list.add(i);
}

Spliterator<Integer> splitor = list.spliterator();
Spliterator<Integer> s1 = splitor.trySplit();
Spliterator<Integer> s2 = s1.trySplit();

System.out.println(s1.estimateSize()); // 10
System.out.println(s2.estimateSize()); // 10

(完)

微信公众号

© 2020 ray