LinkedList源码分析

前言

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

和ArrayList相比,LinkedList多了AbstractSequentialList类和Deque接口。

其中Deque又是继承自Queue,所以LinkedList可以当做队列或者双端队列。

其中AbstractSequentialList的作用可以当做是RandomAccess的对照来看。

关于RandomAccess,可以看看ArrayList源码。

底层结构

LinkedList每个节点都是一个Node类,Node中有next和prev。可以看到实现的是双端队列。

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
transient Node<E> first;
transient Node<E> last;
transient int size = 0;

基本操作

get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}

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

get方法调用了node方法,node方法是找到index位的元素。
这个方法还是很有意思的,他先判断index是在前半段还是后半段,前半段就从first节点开始找,后半段就从last节点开始找。

remove方法

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

因为LinkedList支持存null,所以在remove的时候要分两种情况讨论。

迭代

Iterator

Iterator方法是在AbstractSequentialList中

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

LinkedList中重写了listIterator方法。

1
2
3
4
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}

ListLtr是LinkedList中的一个类

1
private class ListItr implements ListIterator<E>

ListIterator

1
2
3
4
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}

可以看到,其实和Iterator方法的实现是一样的。