Java集合框架详解(二) LinkedList

今天继续对集合框架源码的学习 JDK1.8 今天学习LinkedList

相关文章

LinkedList

类结构

首先观察一下LinkedList的类结构

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

LinkedList实现了List和Deque接口的。实现了所有可选列表操作,并且可以存储null值
顺序访问高效,随机访问低效,插入删除节点高效

相关代码

节点结构

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
4
5
6
7
8
9
10
11
12
13
14
15
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;

关于关键字 transient 在上一篇文章Java集合框架详解(一) ArrayList已经解释过了,这里不多做说明

first指向表头 last指向最后一个节点 size表示节点的个数

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Constructs an empty list.
*/
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();
addAll(c);
}

构造函数也很简单 我们现在看看LinkedList的类方法

类方法

add()

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 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;
}

add方法只有2行代码,方法调用了linkList()方法,我们看看linkList()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Links e as last element.
*/
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++;
}

观察这段代码,是什么意思呢?
我们来模拟一下,首先创建一张类型为Integer的空链表

1
Linkedlist<Integer> linkedlist = new LinkedList<>();

此时list first都是null值,紧接着我们添加数据

1
linkedlist.add(1);

此时调用linkLast(1);
在linkLast()方法中 l = last 为null,newNode前驱后继都为null,
后面 l == null 成立所以走 first=newNode语句,方法调用结束

紧接着我们继续添加数据

1
linkedlist.add(2);

此时调用linkLast(2);
在linkLast()方法中,此时last指向之前添加的1节点,所以此时l != null 走else 即l.next = newNode语句,语句调用结束。

add方法调用流程便是如此。

紧接着分析add的重载方法

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

/**
* Returns the (non-null) Node at the specified element 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;
}
}

checkPositionIndex(index);方法判断索引是否越界

如果index正好是size(即在表尾添加数据)则直接调用linkLast(element);

否则需要找到插入位置,通过node方法获取位置。在node方法为了提高速度,把链表分为前半段和后半段查找,找到节点后调用linkBefore方法插入在该节点之前。

下面我们看看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
47
48
49
50
51
52
53
/**
* 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.
*
* @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();
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;
}

addAll()方法挺长的,但是并不是很难理解,将集合c数组化,然后找到要插入的地方,循环插入即可。

get()

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

get方法不复杂,先判断是否越界,然后调用node方法找到该节点并且返回节点数据即可。

remove()

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 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));
}

首先依然是判断越界,下面我们看看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
/**
* 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;
}

通过方法名字能猜出这应该是将节点断链,这里判断了断链节点为首元结点、尾节点、中间节点的情况,代码也很简单。

set()

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);
E oldVal = x.item;
x.item = element;
return oldVal;
}

首先依然是判断越界问题,然后调用node找到要修改的节点,修改该数据值然后返回旧值。

clear()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
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++;
}

clear方法很简单,从表头开始循环遍历,全部回收即可。

关于LinkedList的主要方法已经分析完了,还有一些常用方法基本都是调用前面分析的方法。

总结

  • LinkedList同时实现了List接口和Deque接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)
  • LinkedList是基于链表的集合,它有着链表的性质 插入删除非常高效 随机访问低效 不存在扩容问题。
  • LinkedList是可以存储null值元素的
  • LinkedList是非同步的
  • 关于modCount 在每次数组操作的时候都会有modCount++;,依然是关于多线程问题 可以详细看知乎问题参考

更多文章可以登录我的博客