Sunxin'Blog

LinkedList (JDK8) 源码解析

LinkedList 源码解析

概述

LinkedList的底层数据结构是链表,所以它的优势是进行插入删除操作效率很高,但是访问随机元素的效率比较低。它是线程不安全的,允许元素为null的双向链表,它可以被当作堆栈,队列或双端队列进行操作。

定义

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

  • 继承了 AbstractSequentialList<E>
  • 实现了List<E> 接口,可以进行队列操作
  • 实现了Deque<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
30
31
32
33
34
35
36
37
// 集合元素的数量
transient int size = 0;
/**
* Pointer to first node. 链表的头节点
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node. 链表的尾节点
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
/**
* Constructs an empty list. 空构造,初始化的时候size为0,first和last的节点都是空
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* 将集合中的所有元素都插入到链表中
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
// 先调用this 执行无参构造
this();
// 把集合对象传递进去
addAll(c);
}

Node

具有前驱和后继,可以看出是个双向链表

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

addAll(Collection<? extends E> c)

增加一个元素肯定会修改 modCount

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
/**
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
// 传递当前节点的Size,目前为0,然后把collection对象传递进去
return addAll(size, c);
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
* 以index为下标,插入集合c中的所有元素
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);// 检查下标是否越界
Object[] a = c.toArray(); // 把Collection转换成对象数组
int numNew = a.length;// 集合的长度,也就是新增元素的数量
if (numNew == 0) // 如果数量为0,则不增加,返回false
return false;
Node<E> pred, succ; //定义index节点的前驱节点和后置节点
if (index == size) {// 表示在链表尾部增加
succ = null;//后继节点为空
pred = last;// 前驱节点变成队尾
} else {
succ = node(index);// 取出 index 位置的节点作为后置节点
pred = succ.prev; // index 节点的前一个节点是前置节点
}
// 遍历数组,链表批量增加,通过遍历数组而依次插入。ArrayList是通过执行System.arrayCopy()进行批量复制插入
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); // 使用前置节点pred,和元素e构建一个新的节点
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; // 修改数量size
modCount++; // 更新修改次数
return true;
}
/**
* Returns the (non-null) Node at the specified element index.
* 通过index 获取一个节点,会进行折半查找,提高效率
*/
Node<E> node(int index) {
// assert isElementIndex(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(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
/**
* Appends the specified element to the end of this list.
* 在尾部插入单个节点元素
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last; // 记录原来尾部节点
final Node<E> newNode = new Node<>(l, e, null); // 通过尾部节点和元素e构造一个新节点
last = newNode; // 更新尾部节点
if (l == null) // 如果尾部节点为空,说明链表是空,需要一个头结点
first = newNode;
else //否则更新原来的尾部节点的后置节点为现在的尾节点
l.next = newNode;
size++; // 数量
modCount++; //修改次数
}

add(int index, E element)

插入单个元素到指定位置

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
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index); //下标检查
if (index == size) // 在尾节点插入
linkLast(element);
else
linkBefore(element, node(index)); //在中间插入
}
/**
* Inserts element e before non-null Node succ. 折半查找
*/
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++;
}

E remove(int index)

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
/**
* Removes the element at the specified position in this list. Shifts any
* subsequent elements to the left (subtracts one from their indices).
* Returns the element that was removed from the list.
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
checkElementIndex(index);// 检查下标越界
return unlink(node(index));// 从链表上删除某个节点
}
/**
* Unlinks non-null node x.
*/
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; // 返回取出的元素值
}

boolean remove(Object o)

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
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* 删除指定的元素
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
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;
}

E set(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
checkElementIndex(index); //检查下标
Node<E> x = node(index); // 利用折半查找找到index对应的节点
E oldVal = x.item; // 拿到这个节点对应的元素
x.item = element; //修改元素值
return oldVal;
}

E get(int index)

1
2
3
4
5
6
7
8
9
10
11
/**
* Returns the element at the specified position in this list.
* 根绝下标查询
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);// 判断是否越界
return node(index).item;
}

int indexOf(Object o)

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
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* 根据节点对象查找节点的下标
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) { // 如果目标对象为null,链表允许存入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;
}

Object[] toArray()

1
2
3
4
5
6
7
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}

– Over –

-------------本文结束感谢您的阅读-------------

本文标题:LinkedList (JDK8) 源码解析

文章作者:Sun xin

发布时间:2018年04月09日 - 20:04

最后更新:2018年04月09日 - 20:04

原始链接:http://sunxin.tech/2018/04/09/LinkedList (JDK8) 源码解析/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。