【Java】JDK源码分析-LinkedList

JDK源码分析-LinkedList

WriteOnRead发布于 今天 15:18

1. 概述

相较于 ArrayList,LinkedList 在平时使用少一些。

LinkedList 内部是一个双向链表,并且实现了 List 接口和 Deque 接口,因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如下:

【Java】JDK源码分析-LinkedList

前文分析了 Queue 和 Deque 接口,正是因为 LinkedList 实现了 Deque 接口。LinkedList 的继承结构如下:

【Java】JDK源码分析-LinkedList

2. 代码分析

2.1 结点类 Node

查看 LinkedList 的源码可发现它内部有个嵌套类 Node,代码如下:

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;

}

}

LinkedList 是双向链表的实现,而该 Node 类则是链表的结点。

此外,LinkedList 还有几个成员变量如下:

// list 的长度

transient int size = 0;

// 链表头结点

transient Node<E> first;

// 链表尾结点

transient Node<E> last;

2.2 构造器

LinkedList 有两个构造器,如下:

public LinkedList() {

}

public LinkedList(Collection<? extends E> c) {

this();

addAll(c);

}

其中第一个为无参构造器;第二个为使用指定的集合构造,并调用 addAll(),继续跟进该方法,代码如下:

public boolean addAll(Collection<? extends E> c) {

return addAll(size, c);

}

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;

}

其中 node(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;

}

}

该方法通过遍历链表获取指定的元素。

值得注意的是,该方法并非直接从头到尾遍历整个链表,而是先判断下标的位置,若在前一半则从前往后遍历;否则就从后往前遍历。这样能减少遍历结点的个数。

与此同时,get(index) 方法内部也是这样实现的:

public E get(int index) {

checkElementIndex(index);

return node(index).item;

}

2.3 常用方法

之前分析 Queue 和 Deque 的时候提到:Queue 中的方法在 Deque 中都有对应的。下面简单分析 LinkedList 中一些常用的方法。

新增结点方法:add(), addLast(), offerLast()

public boolean offerLast(E e) {

addLast(e);

return true;

}

public void addLast(E e) {

linkLast(e);

}

public boolean add(E e) {

linkLast(e);

return true;

}

可以看到他们都是调用了同一个方法 linkLast(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++;

}

该操作就是将指定的结点添加到链表末尾。

删除结点方法:poll(), pollFirst(), removeFirst()

public E poll() {

final Node<E> f = first;

return (f == null) ? null : unlinkFirst(f);

}

public E pollFirst() {

final Node<E> f = first;

return (f == null) ? null : unlinkFirst(f);

}

public E removeFirst() {

final Node<E> f = first;

if (f == null)

throw new NoSuchElementException();

return unlinkFirst(f);

}

可以看到这三个方法都是调用 unlinkFirst() 方法实现的,其代码如下:

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;

}

该方法的操作就是从链表头部移除一个结点。

向单链表插入和删除结点的操作示意图如下(双链表比这里多了前驱结点):

【Java】JDK源码分析-LinkedList

栈的入栈(push)和出栈(pop)操作:

public void push(E e) {

addFirst(e);

}

public E pop() {

return removeFirst();

}

可以看到这两个方法直接调用了双端队列的实现方法。即,该栈是一个「链式栈」。

3. 线程安全性

线程安全的概念不再赘述。分析以下场景:

若有线程 T1 对 LinkedList 进行遍历,同时线程 T2 对其进行结构性修改。

对 LinkedList 的遍历是通过 listIterator(index) 方法实现的,如下:

public ListIterator<E> listIterator(int index) {

checkPositionIndex(index);

return new ListItr(index);

}

private class ListItr implements ListIterator<E> {

private Node<E> lastReturned;

private Node<E> next;

private int nextIndex;

// 初始化时二者是相等的

private int expectedModCount = modCount;

ListItr(int index) {

// assert isPositionIndex(index);

next = (index == size) ? null : node(index);

nextIndex = index;

}

public E next() {

checkForComodification();

if (!hasNext())

throw new NoSuchElementException();

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

public void remove() {

checkForComodification();

if (lastReturned == null)

throw new IllegalStateException();

Node<E> lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)

next = lastNext;

else

nextIndex--;

lastReturned = null;

expectedModCount++;

}

// ...

// 是否有其他线程对当前对象进行结构修改

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

}

该类的 next(), add(e) 等方法在执行时会检测 modCount 与创建时是否一致(checkForComodification() 方法),从而判断是否有其他线程对该对象进行了结构修改,若有则抛出 ConcurrentModificationException 异常。

因此,LinkedList 是线程不安全的。

4. 小结

  1. LinkedList 内部是「双向链表」,同时实现了 List 接口和 Deque 接口,因此也具备 List、双端队列和栈的性质;
  2. 线程不安全。

相关阅读:JDK源码-Queue, Deque

【Java】JDK源码分析-LinkedList

java后端

阅读 39发布于 今天 15:18

本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议

avatar

WriteOnRead

微信公众号:WriteOnRead。

1 声望

0 粉丝

0 条评论

得票时间

avatar

WriteOnRead

微信公众号:WriteOnRead。

1 声望

0 粉丝

宣传栏

1. 概述

相较于 ArrayList,LinkedList 在平时使用少一些。

LinkedList 内部是一个双向链表,并且实现了 List 接口和 Deque 接口,因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如下:

【Java】JDK源码分析-LinkedList

前文分析了 Queue 和 Deque 接口,正是因为 LinkedList 实现了 Deque 接口。LinkedList 的继承结构如下:

【Java】JDK源码分析-LinkedList

2. 代码分析

2.1 结点类 Node

查看 LinkedList 的源码可发现它内部有个嵌套类 Node,代码如下:

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;

}

}

LinkedList 是双向链表的实现,而该 Node 类则是链表的结点。

此外,LinkedList 还有几个成员变量如下:

// list 的长度

transient int size = 0;

// 链表头结点

transient Node<E> first;

// 链表尾结点

transient Node<E> last;

2.2 构造器

LinkedList 有两个构造器,如下:

public LinkedList() {

}

public LinkedList(Collection<? extends E> c) {

this();

addAll(c);

}

其中第一个为无参构造器;第二个为使用指定的集合构造,并调用 addAll(),继续跟进该方法,代码如下:

public boolean addAll(Collection<? extends E> c) {

return addAll(size, c);

}

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;

}

其中 node(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;

}

}

该方法通过遍历链表获取指定的元素。

值得注意的是,该方法并非直接从头到尾遍历整个链表,而是先判断下标的位置,若在前一半则从前往后遍历;否则就从后往前遍历。这样能减少遍历结点的个数。

与此同时,get(index) 方法内部也是这样实现的:

public E get(int index) {

checkElementIndex(index);

return node(index).item;

}

2.3 常用方法

之前分析 Queue 和 Deque 的时候提到:Queue 中的方法在 Deque 中都有对应的。下面简单分析 LinkedList 中一些常用的方法。

新增结点方法:add(), addLast(), offerLast()

public boolean offerLast(E e) {

addLast(e);

return true;

}

public void addLast(E e) {

linkLast(e);

}

public boolean add(E e) {

linkLast(e);

return true;

}

可以看到他们都是调用了同一个方法 linkLast(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++;

}

该操作就是将指定的结点添加到链表末尾。

删除结点方法:poll(), pollFirst(), removeFirst()

public E poll() {

final Node<E> f = first;

return (f == null) ? null : unlinkFirst(f);

}

public E pollFirst() {

final Node<E> f = first;

return (f == null) ? null : unlinkFirst(f);

}

public E removeFirst() {

final Node<E> f = first;

if (f == null)

throw new NoSuchElementException();

return unlinkFirst(f);

}

可以看到这三个方法都是调用 unlinkFirst() 方法实现的,其代码如下:

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;

}

该方法的操作就是从链表头部移除一个结点。

向单链表插入和删除结点的操作示意图如下(双链表比这里多了前驱结点):

【Java】JDK源码分析-LinkedList

栈的入栈(push)和出栈(pop)操作:

public void push(E e) {

addFirst(e);

}

public E pop() {

return removeFirst();

}

可以看到这两个方法直接调用了双端队列的实现方法。即,该栈是一个「链式栈」。

3. 线程安全性

线程安全的概念不再赘述。分析以下场景:

若有线程 T1 对 LinkedList 进行遍历,同时线程 T2 对其进行结构性修改。

对 LinkedList 的遍历是通过 listIterator(index) 方法实现的,如下:

public ListIterator<E> listIterator(int index) {

checkPositionIndex(index);

return new ListItr(index);

}

private class ListItr implements ListIterator<E> {

private Node<E> lastReturned;

private Node<E> next;

private int nextIndex;

// 初始化时二者是相等的

private int expectedModCount = modCount;

ListItr(int index) {

// assert isPositionIndex(index);

next = (index == size) ? null : node(index);

nextIndex = index;

}

public E next() {

checkForComodification();

if (!hasNext())

throw new NoSuchElementException();

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

public void remove() {

checkForComodification();

if (lastReturned == null)

throw new IllegalStateException();

Node<E> lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)

next = lastNext;

else

nextIndex--;

lastReturned = null;

expectedModCount++;

}

// ...

// 是否有其他线程对当前对象进行结构修改

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

}

该类的 next(), add(e) 等方法在执行时会检测 modCount 与创建时是否一致(checkForComodification() 方法),从而判断是否有其他线程对该对象进行了结构修改,若有则抛出 ConcurrentModificationException 异常。

因此,LinkedList 是线程不安全的。

4. 小结

  1. LinkedList 内部是「双向链表」,同时实现了 List 接口和 Deque 接口,因此也具备 List、双端队列和栈的性质;
  2. 线程不安全。

相关阅读:JDK源码-Queue, Deque

【Java】JDK源码分析-LinkedList

以上是 【Java】JDK源码分析-LinkedList 的全部内容, 来源链接: www.h5w3.com/113643.html

回到顶部