Java容器源码分析之LinkedList

LinkedList简介

LinkedList是一个使用双向链表结构实现的容器,与ArrayList一样,它能动态扩充其长度,LinkedList相较于ArrayList,其任意位置插入速度比ArrayList要快,但是其查询速度要比ArrayList要慢;LinkedList继承自AbstractSequentialList,实现了List、Deque、Cloneable、Serializable接口。

LinkedList UML图如下:

LinkedList UML图

和ArrayList一样,LinkedList也不是一个线程安全的容器。

LinkedList源码分析

构造方法

LinkedList有两个构造方法:

1
2
3
4
5
6
7
8
public LinkedList() {
}

//从已有的一个容器创建一个LinkedList对象
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

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
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;
//获取第index位置的node元素和node的前一个元素
//succ:第index位置的node元素
//pred:index位置前一个node元素
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;
}

add方法

LinkedList也有两个add方法,如下:

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

public void add(int index, E element) {
//检查index是否溢出
checkPositionIndex(index);

if (index == size)
//index == size,直接添加到队尾
linkLast(element);
else
//index != size,添加元素到index位置
linkBefore(element, node(index));
}

linkLast方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void linkLast(E e) {
final Node<E> l = last;
//新建一个node,将其前一个元素指针指向原链表的最后一个元素
final Node<E> newNode = new Node<>(l, e, null);
//更新尾指针
last = newNode;
if (l == null)
//若原last==null说明此时链表就一个元素
first = newNode;
else
//更新原链表尾元素指针
l.next = newNode;
size++;
modCount++;
}

linkBefore方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//获取指定位node元素的前一个元素pred
final Node<E> pred = succ.prev;
//新建一个node,将其前指针指向pred元素
final Node<E> newNode = new Node<>(pred, e, succ);
//将指定位置的node元素的前指针指向新元素,完成插入
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

获取指定位置node指针方法node:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node<E> node(int index) {
// assert isElementIndex(index);
//index > size/2时,说明在链表前半段,从前往后搜索
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
//index < size/2时,从后往前搜索
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

get方法

1
2
3
4
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}

get方法也比较简单,首先检测index是否溢出,然后直接找到index位置的元素,并返回其item。

本文首发于我在万达摆地摊's blog,转载请注明来源