JDK源代码之LinkedList

LinkedList特性

底层数据结构

LinkedList不同于ArrayList的数组,它基于链表。

效率

LinkedList的插入删除快,遍历慢(ArrayList正好相反)

实现的接口

1
2
3
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList实现了List接口、Deque双向队列接口(既可以当作FILO队列也可以当作FIFO栈)、Cloneable接口、序列化接口。
值得注意的是,LinkedList继承自AbstractSequentialList(AbstractSequentialList和ArrayList一样继承自AbstractList),也就是说,LinkedList比ArrayList更细化了一层。

细化的那层AbstractSequentialList实现了“链表”版的get/set/add/remove方法,这使得LinkedList和ArrayList有了质的差别(毕竟彼此的基因遗传都不同)

同步机制

与ArrayList一样,LinkedList也是不同步的,可以用包装器来创造一个支持同步的List:

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


LinkedList字段

1
2
3
4
5
transient int size = 0;

transient Node<E> first;

transient Node<E> last;

很明显,LinkedList用了first节点和last节点来保存整个链表(ArrayList用的是数组)。
注:transient关键字的作用是防止该字段被序列化(一些敏感的信息不能序列化然后在网络上传输)。


LinkedList方法分析

linkFirst(E e) (将一个元素插入链表头部)

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

先建立一个以first为后继的新节点,令first为该新节点;然后再修改第二个节点的prev变量使其指向新头部(如果没有第二个节点就修改last

linkLast(E e)(将一个元素插入链表尾部)

机制与linkFirst(E e)相似,只需将first替换为last

linkBefore(E e, Node succ) (将一个元素插到一个节点之前)

1
2
3
4
5
6
7
8
9
10
11
12
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

该方法会判断另一个节点之前是否有节点存在,没有就修改first

unlinkFirst(Node f)(将链表头部节点剔除)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}

该方法中有条垃圾回收优化的语句:

1
f.next = null; // help GC

强行令变量为null,不再引用该对象,该对象便会在下一轮的GC中被回收。
此外,该方法会判断第二个元素是否存在,没有就修改last

unlinkLast(Node l)(将链表尾部节点剔除)

unlinkFirst(Node<E> 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
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;
}

该方法需要判断前面的元素和后面的元素是否存在。

getFirst/getLast/removeFirst/removeLast/addFirst/addLast(会抛异常的获取增加与删除)

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
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}

public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}

public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}

public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}

public void addFirst(E e) {
linkFirst(e);
}

public void addLast(E e) {
linkLast(e);
}

以上方法调用了之前的linkFirstlinkLastunlinkFirstunlinkLast等方法。

remove(Object o)(删除某个特定对象)

根据该对象是否为空分2种情况处理:

  1. 为空,从头扫到尾,利用==null来判断
  2. 不为空,从头扫到尾,利用equals来判断
    注:删除的时候,最终都是要找到要删除的节点,利用链表的解绑来删除。

addAll(int index, Collection<? extends E> c)(插入一个集合到特定的位置)

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
public boolean addAll(int index, Collection<? extends E> c) {
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) {
@SuppressWarnings("unchecked") 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 {
pred.next = succ;
succ.prev = pred;
}

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

使用node(index)找到插入时的后继节点和前继节点(如果是插到尾部则后继节点为空而前继节点为last),中一一插入元素(根据前继节点来做关联),最后加入后继节点。

get(int index)(获取某个位置的数据)

该方法表现得很像数组有没有,可以获取特定位置的元素!
该方法调用了node(index)来获取该位置的节点,再获取该节点的数据,那么node(index)的原理是什么呢?

node(index)(获取某个位置的节点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node<E> node(int 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;
}
}

这个方法很巧妙,先判断下标大小,超过一半就从后面开始遍历,否则从前面开始遍历!

add(int index, E element)(往某个位置插入一个数据)

1
先判断是否是尾部,是就调用linkLast(element),不是就调用linkBefore(element, node(index))

isPositionIndex(int index) (判断一个位置是否能合法地插入数据)

1
2
3
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}

indexOf(Object o)(查找某个对象的下标)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}

从头往后遍历,复杂度较高。

peek()(获取头部数据,不会抛出异常只会返回null)

poll()(获取并移除头部数据,不会抛出异常只会返回null)

offer(E e)(将数据插入尾部)

针对双向队列实现的方法

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 boolean offerFirst(E e) {
addFirst(e);
return true;
}

public boolean offerLast(E e) {
addLast(e);
return true;
}

public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}

public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}

以上方法均不会抛出异常,offer是添加,peek是获取,poll是获取并移除。

针对栈实现的方法

1
2
3
4
5
6
7
public void push(E e) {
addFirst(e);
}

public E pop() {
return removeFirst();
}

Iterator详解

java中的Iterator是神奇的东西,主要有hasNext()next()方法供使用,前者判断是否还有元素可以遍历,后者将返回下一个元素。

Iterarot字段

1
2
3
4
private Node<E> lastReturned = null;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;

lastReturned是上一个返回的节点,next则是下一个将返回的节点。

Iterator方法

next()(返回下一个节点)
1
2
3
4
5
6
7
8
9
10
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();

lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}

从这里可以看出,每次调用next()方法时,next字段相当于current,我们将返回这个current节点,令lastReturned指向current节点,最后,让next指向下一个准备返回的节点。
所以总结地说:该方法返回当前next指向的节点,并让next指向下一个节点

previous()

1
2
3
4
5
6
7
8
9
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}

该方法和next()类似,让next指向上一个节点,返回当前next指向的节点
在该方法执行后,lastReturnednext指向同一个节点。

似乎next()方法和previous()方法的实现不太一致,原理不一样?
previous()方法并不会返回next指向的节点,而是返回next前面的节点。似乎把下标定义在previous和next之间会比较好一点
比如有队列:

0 1 2 3 4 5 6

再定义一个iterator:

1
ListIterator<Integer> iterator = list.listIterator(3);

该iterator其实并不是指向第四个元素(因为从0开始计,所以参数是3而实际上是第四个元素),也就是3,而是指向2和3之间的空隙。
下标指向的位置如下:

0 1 2 ‘下标在这里(距离右边的3更近一点)’ 3 4 5 6

此时我们若调用next()者则返回右边的3,并将下标往右移动;若调用previous()则返回左边的2,并将下标往左移动。

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();

Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}

删除之前被返回的节点,if (next == lastReturned)处理调用previous()方法后的情况。

内部类DescendingIterator(反向的iterator)

调用next()实际上会调用previous(),所以它实际上是个单向的,从后向前的iterator(虽然语法上它一直在调用next())

toArray(T[] a)(将内容放到特定的数组中去)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;

if (a.length > size)
a[size] = null;

return a;
}

该方法中,如果目标数码长度不够,就利用反射的方法重新创建一个足够大的数组。

writeObject(java.io.ObjectOutputStream s)

将LinkedList内容写入到流中去。

readObject(java.io.ObjectInputStream s)

从流中读出一个LinkedList。

静态内部类LLSpliterator

该类有待继续深入研究。