Java集合框架分析-LinkedList

本篇文章主要分析一下Java集合框架中的List部分,LinkedList,该源码分析基于JDK1.8,分析工具,AndroidStudio,文章分析不足之处,还请指正!

相关文章
1、Java 集合框架分析-概述
2、Java集合框架分析-HashMap
3、Java集合框架分析-LinkedHashMap
4、Java集合框架分析-ArrayList
5、Java集合框架分析-Iterator
6、Java集合框架分析-HashSet

一、LinkedList简介

首先来看下java集合框架的总图,在网上找了两张关于集合框架的架构图:

1.1 类结构

首先,我们来看下LinkedList的类继承结构

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

从上面我们可以看出来 LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 实现 List 接口,能对它进行队列操作。实现 Deque 接口,即能将LinkedList当作双端队列使用。实现了Cloneable接口,即覆盖了函数clone(),能克隆。实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。同时LinkedList 是非同步的。

1.2 数据结构

接下来我们来看看LinkedList的数据结构是什么样的。我们在分析LinkedHashMap的时候也会发现它的底层包含一个双向循环链表,而LinkedList也是的,LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:

图上便是LinkedList的底层结构图,基于双向循环链表结构设计的。它的每一个节点都包含数据信息,上一个节点位置信息和下一个节点位置信息。

二、源码分析

接下来我们分析LinkedList的源码,首先来看下它内部申明的属性。

2.1 属性申明

1
2
3
4
5
6
7
8
//链表节点的数量
transient int size = 0;
//头结点
transient Node<E> first;
//下一个节点
transient Node<E> last;

变量申明比较简单,接着我们分析构造函数。如果有不大理解的,我们可以先分析后面的代码,就能知道这些属性的意思了。

2.2 构造函数

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

构造函数也比较简单,没啥可说的,我们接着分析。一开始介绍的时候我们说明了底层是双向循环链表,所以肯定有节点信息,所以我们来看下它的节点数据结构。

2.3 节点信息

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

节点数据结构,很简单,一个是数据信息item,一个是前一个位置节点prev,另一个是后一个位置节点next,非常简单。接下来我们继续查看添加元素add方法

2.4 add(E e)

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

添加数据add方法比较简单,add函数用于向LinkedList中添加一个元素,并且添加到链表尾部。我们来看看linkLast方法怎么添加数据的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//尾部添加数据e
void linkLast(E e) {
//保存尾部节点
final Node<E> l = last;
//新生成结点的前驱为l,后继为null
final Node<E> newNode = new Node<>(l, e, null);
// 重新赋值尾结点
last = newNode;
// 尾节点为空,赋值头结点
if (l == null)
first = newNode;
else
// 尾结点的后继为新生成的结点
l.next = newNode;
//节点数量增加1
size++;
modCount++;
}

上面这段代码是什么意思呢?我们来通过demo来简单说明一下。

1
2
3
List<String> mLinkedList = new LinkedList();
mLinkedList.add("A");
mLinkedList.add("B");

首先我们先申明一个LinkedList类型的变量mLinkedList,然后依次添加进两个数据“A”和“B”,这个时候,它的内部结构是怎么操作的呢?看下面图解:

我们首先调用LinkedList的无参构造函数,进行初始化,这个时候里面的节点都是null,因为没有数据,其次,我们通过add添加进一条数据“A”,这个时候结合上面的源代码add方法,来解读一下,首先会调用linkLast方法,其次判断它的last节点是否为null,由于是刚初始化的,所以last=null,这样就会调用first = newNode;这个方法,也就是在开头节点处插入一条数据,其次再调用add(“B”),再次插入一条数据,我们循环上面那段代码,发现这个时候last!=null了,所以调用last.next=newNode代码,也就是在第一个节点的后面插入一条数据。上面便是add的执行流程的图解。

我们接着分析add其他的重载方法。

1
2
3
4
5
6
7
8
9
//在指定的位置上面插入一条数据
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}

这个方法也不是很复杂,我们依次分析,首先判断一下,需要插入的index是否越界。在插入之前我们需要先找到待插入位置的node,通过node(index)方法获得,我们看下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//判断index是在链表的中部之前还是后面,如果在1/2前的话,从头开始遍历,如果在1/2后的话,从后往前遍历
Node<E> node(int index) {
//从前往后遍历获取index出的node
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//从后往前遍历获取index出的node
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

上面很简单,为了提高搜索效率,先判断是在1/2处的前面还是后面,然后依次循环获得index处的node,我们接着分析

1
2
3
4
5
6
7
8
9
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//不在[0,size]范围内越界
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}

其次根据index判断是在链表中的哪个地方插入数据,是尾部还是在前面位置,如果是在尾部的话,我们已经分析过了,我们来看下在前面插入数据的情况。

1
2
3
4
5
6
7
8
9
10
11
12
void linkBefore(E e, Node<E> succ) {
//保存目标index处的前置节点
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++;

其实,这段代码也不难理解,我们用个图来解释一下插入过程。

我们逐一分析,首先我们获取到了index处的节点C,然后保存C的前置节点为pred(也就是B节点),然后我们用待插入的节点构建一个新的节点(newNode)(新节点的前置节点是pred,后继节点是C),然后我们将index处的节点C的前置节点设置为待插入的节点,然后判断这个index处的node是否是第一个节点,不是的话就将原先index处的node的前置节点的后继节点设置为待插入的节点。这里面主要涉及到链表的插入操作,如果对于这不熟悉的话,可以先去复习一下链表的相关操作。

分析完了add方法,我们再来分析一下addAll方法。

1
2
3
public boolean addAll(Collection<? extends E> c) {
return addAll(size, 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
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;
}

以上便是add的方法内容,思想其实也简单的,类似单个插入,主要就是判断在链表尾部还是中间或者头部插入,然后再依次插入即可。

####2.5 get(int index)
插入数据分析完之后,我们就开始分析获取数据get。

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

get方法也是只有简单的两行,我们依次分析,首先分析第一行,就是判断索引的位置是否越界,

1
2
3
4
5
6
7
8
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}

很简单,看代码就知道了,不用分析了,接着分析第二行,第二行上面也已经分析过了,所以这里就不用再多叙述了。get方法总体而言很简单。我们接着分析。

2.6 remove(int index)

我们接着来分析一下删除数据的代码。

1
2
3
4
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

代码也很简单,首先是检查索引是否越界,其次我们分析第二行,我们发现node(index) 的意思就是获取链表中指定位置上面的node,所以我们看看unlink方法内容。

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
E unlink(Node<E> x) {
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;
}
//gc
x.item = null;
size--;
modCount++;
return element;
}

上面主要是进行双向链表的删除操作。我们接着分析它的重载方法,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//删除指定元素,默认从first节点开始,删除第一次出现的那个元素
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;
}

相应代码已经分析过了,我们就不再说了。我们分析一下set方法

1
2
3
4
5
6
7
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

首先是判断是否越界,然后获取需要替换的位置上面的node,然后update一下,返回旧的数据。

我们来分析一下清空链表的方法clear

1
2
3
4
5
6
7
8
9
10
11
12
13
public void clear() {
//遍历链表,依次设置为null
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的方法分析完了,还有一些简单的方法,我们一并列出来,做个简单的注释。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//在首节点处添加一个数据
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++;
}
public void addFirst(E e) {
linkFirst(e);
}
//在尾节点插入一个节点
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++;
}
public void addLast(E e) {
linkLast(e);
}
//移除第一个节点
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;
}
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 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 boolean contains(Object o) {
return indexOf(o) != -1;
}
//遍历链表,存在则返回索引不存在则返回-1
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;
}
//从后往前遍历,第一次出现则返回索引,不存在返回-1
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
//返回链表第一个节点,但是不删除节点
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//返回并删除第一个节点
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//省略迭代部分的源码......

以上便是LinkedList的基本源码,我们基本都给出了注释,相关重要的功能都加以图解,接下来我们来总结一下关于LinkedList相关重要知识。

三、总结

  1. 从源码中可以看出,LinkedList的实现是基于双向循环链表的。却别与ArrayList的数组,以及HashMap的线性表和散列表以及LinkedHashMap的线性表和散列表以及双向循环链表。
  2. 我们在搜索链表中的数据时,都会进行判断是否为null的情况,所以LinkedList是允许元素为null的情况的。
  3. LinkedList是基于链表实现的,因此不存在容量不足的问题,所以这里没有扩容的方法。
  4. 源码中还实现了栈和队列的操作方法,因此也可以作为栈、队列和双端队列来使用。
  5. LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 实现 List 接口,能对它进行队列操作。实现 Deque 接口,即能将LinkedList当作双端队列使用。实现了Cloneable接口,即覆盖了函数clone(),能克隆。实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。同时LinkedList 是非同步的。

关于作者

github: https://github.com/crazyandcoder
博客: http://crazyandcoder.github.io
掘金:https://juejin.im/user/56b96af96240b8005865df59/share


参考链接

1、http://www.cnblogs.com/ITtangtang/p/3948610.html
2、http://blog.csdn.net/ns_code/article/details/35787253
3、http://www.cnblogs.com/hzmark/archive/2012/12/25/LinkedList.html