死磕Jdk源码之LinkedList:

本博客目前所有 死磕 Jdk 源码系列都是使用 jdk1.8版本。

简介

双向链表实现了列表和Deque接口。实现所有可选的列表操作,并允许所有元素(包括null)。
所有操作的执行都符合双向链表的预期。索引到列表中的操作将从头或尾遍历列表,以更接近指定索引的操作为准。

特性

  1. LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当做堆栈、队列或双端队列进行使用。
  2. LinkedList实现List接口,能让它进行队列操作。
  3. LinkedList实现Deque接口,即能将LinkedList当做双端队列使用。
  4. LinkedList实现Cloneable,即覆盖了函数clone(),能被克隆。
  5. LinkedList实现了java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
  6. LinkedList中的操作不是线程安全的。

数据结构

LinkedList内部维护一个双向列表

线程安全性

这个实现不是同步的。如果多个线程同时访问一个链表,并且至少有一个线程从结构上修改了链表,那么它必须在外部同步。(结构修改是指增加或删除一个或多个元素的任何操作;仅仅设置元素的值并不是一种结构修改。)这通常是通过对一些自然封装列表的对象进行同步来实现的。如果不存在这样的对象,则应该使用集合对列表进行“包装”。synchronizedList方法。这最好在创建时完成,以防止意外的不同步访问列表:

1
List list = Collections.synchronizedList(new LinkedList());

成员变量

LinkedList有三个个关键的成员变量

还有一个记录集合修改次数的变量,由iteratorlistIterator,如果在迭代过程中,modCount的值变更,就会抛出ConcurrentModificationException异常。

  • size

表示LinkedList中的元素个数

  • first

LinkedList的第一个节点

满足要么第一个节点和最后一个节点都为null,要么第一个节点不为null,第一个的前驱节点为空

  • last

LinkedList的最后一个节点

满足要么第一个节点和最后一个节点都为null,要么最后一个节点不为null,第一个的后继节点为空

死磕源码

添加元素

add(E e)

将指定的元素追加到此列表的末尾。

1
2
3
4
5
public boolean add(E e) {
// 将元素 e 追加到链表末尾
linkLast(e);
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Links e as last element.
*/
void linkLast(E e) {
// 获取当前 last 节点
final Node<E> l = last;
// 创建一个新节点,节点的前驱节点为原 last 节点,节点的后继节点为 null
final Node<E> newNode = new Node<>(l, e, null);
// 将当前节点置为末尾绩点
last = newNode;
// 如果原 last 节点为 null,就说明链表为空,将 first 设置为新节点
if (l == null)
first = newNode;
// 如果原末尾节点不为 null,将原 last 节点的后继节点指向新节点
else
l.next = newNode;
// 链表大小 +1
size++;
// 修改次数 + 1
modCount++;
}

add(int index, E element)

将指定元素插入到列表中的指定位置。通过改变后续元素的指向。

1
2
3
4
5
6
7
8
9
10
11
public void add(int index, E element) {
// 检查给定的索引是否合法
checkPositionIndex(index);

// 如果索引值等于链表大小,就相当于在尾部追加节点
if (index == size)
linkLast(element);
// 调用 linkBefore ,在指定节点前插入元素 element
else
linkBefore(element, node(index));
}

node方法根据索引返回指定位置的节点,其实就是遍历链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 等同于 index < size/2,如果索引在链表的前半部分就从 first 节点往后遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
// 如果 索引在链表的后半部分就从 last 节点往前遍历
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

在指定节点 succ 前插入 元素 e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 获取被插入节点的前驱节点
final Node<E> pred = succ.prev;
// 创建一个新的节点,前驱节点为 succ 节点的前驱节点,后继节点为 succ 节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 将 succ 节点的前驱节点置为新节点
succ.prev = newNode;
// 如果 succ 节点的 前驱节点为null,也就是说原链表为空,新节点就是第一个元素,新节点同时也是 first 节点
if (pred == null)
first = newNode;
// 否则就将原 succ 节点的前驱节点的后继节点置为新节点
else
pred.next = newNode;
// 链表大小 +1
size++;
// 修改次数 + 1
modCount++;
}

移除元素

remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean remove(Object o) {
// 如果 o 为 null,就移除第一个元素为 null 的节点
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
// 否则移除第一个 equals o 的元素节点
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

从链表中移除对应的节点

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
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
// 获取当前节点的元素 element
final E element = x.item;
// 获取当前节点的后继节点 next
final Node<E> next = x.next;
// 获取当前节点的前驱节点 prev
final Node<E> prev = x.prev;

// 如果 prev 节点为 null,说明是 first 节点,就将 next 节点指向 first
if (prev == null) {
first = next;
}
// 否则
else {
// 将 prev 节点的后继节点指向 next 节点
prev.next = next;
// 当前节点的前驱节点置为 null
x.prev = null;
}
// 如果 next 节点为 null,说明是 last 节点,就将 prev 节点指向 last
if (next == null) {
last = prev;
}
// 否则
else {
/// 将 next 节点的前驱节点指向 prev 节点
// 当前节点的后继节点置为 null
next.prev = prev;
x.next = null;
}
// 当前节点元素置为 null
x.item = null;
// 链表大小 -1
size--;
// 修改次数 + 1
modCount++;
// 返回被移除的元素
return element;
}

removeFirst()

移除链表的 first 节点并返回被移除的元素

1
2
3
4
5
6
7
8
9
public E removeFirst() {
// 获取当前 first 节点
final Node<E> f = first;
// 如果 first 节点为 null,也就是链表为空,就抛出 NoSuchElementException 异常
if (f == null)
throw new NoSuchElementException();
// 移除 first 节点
return unlinkFirst(f);
}
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

/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 获取 f 节点的元素
final E element = f.item;
// 获取 f (原 first)节点的后继节点 next
final Node<E> next = f.next;
// 将 f 节点 元素置为 null
f.item = null;
// 将 f 节点 后继节点置为 null
f.next = null; // help GC
// 将 first 节点指向 f (原 first) 节点的 next 节点
first = next;
// 如果 next 节点为 null,说明此时链表为空,last 节点也应该为 null
if (next == null)
last = null;
// 否则,将 next (当前 first)节点的前驱节点置为 null
else
next.prev = null;
// 链表大小 -1
size--;
// 修改次数 + 1
modCount++;
// 返回被移除的元素
return element;
}

removeLast()

移除链表的 last 节点并返回被移除的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
// 获取当前 last 节点
final Node<E> l = last;
// 如果 last 节点为 null,也就是链表为空,就抛出 NoSuchElementException 异常
if (l == null)
throw new NoSuchElementException();
// 移除 last 节点
return unlinkLast(l);
}
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
/**
* Unlinks non-null last node l.
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
// 获取 l 节点的元素
final E element = l.item;
// 获取 l (原 last)节点的前驱节点 prev
final Node<E> prev = l.prev;
// 将 l 节点 元素置为 null
l.item = null;
// 将 l 节点 前驱节点置为 null
l.prev = null; // help GC
// 将 last 节点指向 原 last 节点的前驱节点 prev
last = prev;
// 如果 prev 为 null,说明链表为空,将 first置为 null
if (prev == null)
first = null;
// 否则,将 prev (当前 last)节点的后继节点置为 null
else
prev.next = null;
// 链表大小 -1
size--;
// 修改次数 + 1
modCount++;
// 返回被移除的元素
return element;
}

总结

LinkedList插入效率很高,通过索引插入效率较低需要遍历链表,根据索引值选择从 lastfirst 节点开始遍历。最坏结果为需要遍历 size/2 个元素。
LinkedList移除元素效率很高,通过索引移除元素同通过索引插入元素,需要遍历节点。