LinkedList 源码分析

1. 迭代器Iterator


在 Java 中，Iterator（迭代器）是一个用于遍历聚集元素的接口。它提供了一种同一的方式来访问聚集中的元素，而不必要相识聚集的内部实现细节。
一、告急方法

• hasNext()：判断是否尚有下一个元素可遍历。
  

• 
  
  
  
  • 示例：
    
  
  

1. Iterator<String> iterator = list.iterator();
2. while (iterator.hasNext()) {
3.     // 有下一个元素时执行这里的代码
4. }

复制代码

• next()：返回下一个元素。
  

• 
  
  
  
  • 示例：
    
  
  

1. while (iterator.hasNext()) {
2.     String element = iterator.next();
3.     System.out.println(element);
4. }

复制代码

• remove()：移除当前由next()方法返回的元素。这个方法只能在调用next()方法之后调用一次。
  

• 
  
  
  
  • 示例：
    
  
  

1. while (iterator.hasNext()) {
2.     String element = iterator.next();
3.     if (someCondition(element)) {
4.         iterator.remove();
5.     }
6. }

复制代码

二、利用场景

• 遍历聚集：
  

• 
  
  
  
  • 可以方便地遍历各种聚集范例，如ArrayList、LinkedList、HashSet等。
    
  • 使得遍历代码更加通用，不依赖于特定聚集的实现细节。
    
  
  

• 动态操纵聚集：
  

• 
  
  
  
  • 在遍历过程中可以利用remove()方法安全地删除元素，而不会导致ConcurrentModificationException非常。
    
  
  

三、与增强 for 循环的比力
增强 for 循环（也称为“foreach”循环）在语法上更加轻巧，但它不能像Iterator那样在遍历过程中删除元素。
增强 for 循环示例：

1. for (String element : list) {
2.     System.out.println(element);
3. }

复制代码

四、实现原理
差别的聚集类对Iterator的实现方式差别，但总体来说，Iterator通过维护一个指向聚集内部元素的指针来实现遍历。每次调用next()方法时，指针向前移动一位并返回当前位置的元素。hasNext()方法通过查抄指针是否到达聚集末端来判断是否尚有下一个元素。
比方，对于ArrayList，它的iterator()方法返回一个内部类Itr的实例，这个内部类实现了Iterator接口，并通过维护一个cursor变量来记载当前遍历的位置。
五、留意事项

• 在利用Iterator遍历集适时，不要在遍历过程中通过聚集自身的方法修改聚集的布局（如添加或删除元素），除非利用Iterator的remove()方法。否则大概会导致不可猜测的结果或抛出ConcurrentModificationException非常。
  
• 在调用remove()方法之前，必须先调用next()方法，否则会抛出IllegalStateException非常。
  

2. 源码分析


2.1. LinkedList 简介

LinkedList 是一个基于双向链表实现的聚集类，常常被拿来和 ArrayList 做比力。关于 LinkedList 和ArrayList的具体对比，我们 Java 聚集常晤口试题总结(上)有具体先容到。

双向链表
不外，我们在项目中一样平常是不会利用到 LinkedList 的，必要用到 LinkedList 的场景险些都可以利用 ArrayList 来代替，而且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）本身都说从来不会利用 LinkedList 。

别的，不要下意识地以为 LinkedList 作为链表就最得当元素增删的场景。我在上面也说了，LinkedList 仅仅在头尾插入大概删除元素的时间时间复杂度近似 O(1)，其他环境增删元素的均匀时间复杂度都是 O(n) 。
2.1.1. LinkedList 插入和删除元素的时间复杂度？

• 头部插入/删除：只必要修改头结点的指针即可完成插入/删除操纵，因此时间复杂度为 O(1)。
  
• 尾部插入/删除：只必要修改尾结点的指针即可完成插入/删除操纵，因此时间复杂度为 O(1)。
  
• 指定位置插入/删除：必要先移动到指定位置，再修改指定节点的指针完成插入/删除，不外由于有头尾指针，可以从较近的指针出发，因此必要遍历均匀 n/4 个元素，时间复杂度为 O(n)。
  

2.1.2. LinkedList 为什么不能实现 RandomAccess 接口？

RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据布局是链表，内存所在不连续，只能通过指针来定位，不支持随机快速访问，以是不能实现 RandomAccess 接口。
2.2. LinkedList 源码分析

这里以 JDK1.8 为例，分析一下 LinkedList 的底层焦点源码。
LinkedList 的类界说如下：

1. public class LinkedList<E>
2.     extends AbstractSequentialList<E>
3.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable
4. {
5.   //...
6. }

复制代码

LinkedList 继承了 AbstractSequentialList ，而 AbstractSequentialList 又继承于 AbstractList 。
阅读过 ArrayList 的源码我们就知道，ArrayList 同样继承了 AbstractList ， 以是 LinkedList 会有大部分方法和 ArrayList 相似。
LinkedList 实现了以下接口：

• List : 表明它是一个列表，支持添加、删除、查找等操纵，而且可以通过下标举行访问。
  
• Deque ：继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据布局。必要留意，Deque 的发音为 "deck" [dɛk]，这个大部分人都会读错。
  
• Cloneable ：表明它具有拷贝本领，可以举行深拷贝或浅拷贝操纵。
  
• Serializable : 表明它可以举行序列化操纵，也就是可以将对象转换为字节省举行长期化存储或网络传输，非常方便。
  

LinkedList 类图
LinkedList 中的元素是通过 Node 界说的：

1. private static class Node<E> {
2.     E item;// 节点值
3.     Node<E> next; // 指向的下一个节点（后继节点）
4.     Node<E> prev; // 指向的前一个节点（前驱结点）
6.     // 初始化参数顺序分别是：前驱结点、本身节点值、后继节点
7.     Node(Node<E> prev, E element, Node<E> next) {
8.         this.item = element;
9.         this.next = next;
10.         this.prev = prev;
11.     }
12. }

复制代码

2.2.1. 初始化

LinkedList 中有一个无参构造函数和一个有参构造函数。

1. // 创建一个空的链表对象
2. public LinkedList() {
3. }
5. // 接收一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
6. public LinkedList(Collection<? extends E> c) {
7.     this();
8.     addAll(c);
9. }

复制代码

2.2.2. 插入元素

LinkedList 除了实现了 List 接口相干方法，还实现了 Deque 接口的许多方法，以是我们有许多种方式插入元素。
我们这里以 List 接口中相干的插入方法为例举行源码讲授，对应的是add() 方法。
add() 方法有两个版本：

• add(E e)：用于在 LinkedList 的尾部插入元素，即将新元素作为链表的末了一个元素，时间复杂度为 O(1)。
  
• add(int index, E element):用于在指定位置插入元素。这种插入方式必要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此必要移动均匀 n/2 个元素，时间复杂度为 O(n)。
  

1. // 在链表尾部插入元素
2. public boolean add(E e) {
3.     linkLast(e);
4.     return true;
5. }
7. // 在链表指定位置插入元素
8. public void add(int index, E element) {
9.     // 下标越界检查
10.     checkPositionIndex(index);
12.     // 判断 index 是不是链表尾部位置
13.     if (index == size)
14.         // 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可
15.         linkLast(element);
16.     else
17.         // 如果不是则调用 linkBefore 方法将其插入指定元素之前
18.         linkBefore(element, node(index));
19. }
21. // 将元素节点插入到链表尾部
22. void linkLast(E e) {
23.     // 将最后一个元素赋值（引用传递）给节点 l
24.     final Node<E> l = last;
25.     // 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空
26.     final Node<E> newNode = new Node<>(l, e, null);
27.     // 将 last 引用指向新节点
28.     last = newNode;
29.     // 判断尾节点是否为空
30.     // 如果 l 是null 意味着这是第一次添加元素
31.     if (l == null)
32.         // 如果是第一次添加，将first赋值为新节点，此时链表只有一个元素
33.         first = newNode;
34.     else
35.         // 如果不是第一次添加，将新节点赋值给l（添加前的最后一个元素）的next
36.         l.next = newNode;
37.     size++;
38.     modCount++;
39. }
41. // 在指定元素之前插入元素
42. void linkBefore(E e, Node<E> succ) {
43.     // assert succ != null;断言 succ不为 null
44.     // 定义一个节点元素保存 succ 的 prev 引用，也就是它的前一节点信息
45.     final Node<E> pred = succ.prev;
46.     // 初始化节点，并指明前驱和后继节点
47.     final Node<E> newNode = new Node<>(pred, e, succ);
48.     // 将 succ 节点前驱引用 prev 指向新节点
49.     succ.prev = newNode;
50.     // 判断前驱节点是否为空，为空表示 succ 是第一个节点
51.     if (pred == null)
52.         // 新节点成为第一个节点
53.         first = newNode;
54.     else
55.         // succ 节点前驱的后继引用指向新节点
56.         pred.next = newNode;
57.     size++;
58.     modCount++;
59. }

复制代码

2.2.3. 获取元素

LinkedList获取元素相干的方法一共有 3 个：

• getFirst()：获取链表的第一个元素。
  
• getLast()：获取链表的末了一个元素。
  
• get(int index)：获取链表指定位置的元素。
  

1. // 获取链表的第一个元素
2. public E getFirst() {
3.     final Node<E> f = first;
4.     if (f == null)
5.         throw new NoSuchElementException();
6.     return f.item;
7. }
9. // 获取链表的最后一个元素
10. public E getLast() {
11.     final Node<E> l = last;
12.     if (l == null)
13.         throw new NoSuchElementException();
14.     return l.item;
15. }
17. // 获取链表指定位置的元素
18. public E get(int index) {
19.   // 下标越界检查，如果越界就抛异常
20.   checkElementIndex(index);
21.   // 返回链表中对应下标的元素
22.   return node(index).item;
23. }

复制代码

这里的焦点在于 node(int index) 这个方法：

1. // 返回指定下标的非空节点
2. Node<E> node(int index) {
3.     // 断言下标未越界
4.     // assert isElementIndex(index);
5.     // 如果index小于size的二分之一  从前开始查找（向后查找）  反之向前查找
6.     if (index < (size >> 1)) {
7.         Node<E> x = first;
8.         // 遍历，循环向后查找，直至 i == index
9.         for (int i = 0; i < index; i++)
10.             x = x.next;
11.         return x;
12.     } else {
13.         Node<E> x = last;
14.         for (int i = size - 1; i > index; i--)
15.             x = x.prev;
16.         return x;
17.     }
18. }

复制代码

get(int index) 或 remove(int index) 等方法内部都调用了该方法来获取对应的节点。
从这个方法的源码可以看出，该方法通过比力索引值与链表 size 的一半巨细来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半，就从链表头开始遍历，反之从链表尾开始遍历。如许可以在较短的时间内找到目的节点，充实利用了双向链表的特性来进步服从。
2.2.4. 删除元素

LinkedList删除元素相干的方法一共有 5 个：

• removeFirst()：删除并返回链表的第一个元素。
  
• removeLast()：删除并返回链表的末了一个元素。
  
• remove(E e)：删除链表中初次出现的指定元素，如果不存在该元素则返回 false。
  
• remove(int index)：删除指定索引处的元素，并返回该元素的值。
  
• void clear()：移除此链表中的全部元素。
  

1. // 删除并返回链表的第一个元素
2. public E removeFirst() {
3.     final Node<E> f = first;
4.     if (f == null)
5.         throw new NoSuchElementException();
6.     return unlinkFirst(f);
7. }
9. // 删除并返回链表的最后一个元素
10. public E removeLast() {
11.     final Node<E> l = last;
12.     if (l == null)
13.         throw new NoSuchElementException();
14.     return unlinkLast(l);
15. }
17. // 删除链表中首次出现的指定元素，如果不存在该元素则返回 false
18. public boolean remove(Object o) {
19.     // 如果指定元素为 null，遍历链表找到第一个为 null 的元素进行删除
20.     if (o == null) {
21.         for (Node<E> x = first; x != null; x = x.next) {
22.             if (x.item == null) {
23.                 unlink(x);
24.                 return true;
25.             }
26.         }
27.     } else {
28.         // 如果不为 null ,遍历链表找到要删除的节点
29.         for (Node<E> x = first; x != null; x = x.next) {
30.             if (o.equals(x.item)) {
31.                 unlink(x);
32.                 return true;
33.             }
34.         }
35.     }
36.     return false;
37. }
39. // 删除链表指定位置的元素
40. public E remove(int index) {
41.     // 下标越界检查，如果越界就抛异常
42.     checkElementIndex(index);
43.     return unlink(node(index));
44. }

复制代码

这里的焦点在于 unlink(Node<E> x) 这个方法：

1. E unlink(Node<E> x) {
2.     // 断言 x 不为 null
3.     // assert x != null;
4.     // 获取当前节点（也就是待删除节点）的元素
5.     final E element = x.item;
6.     // 获取当前节点的下一个节点
7.     final Node<E> next = x.next;
8.     // 获取当前节点的前一个节点
9.     final Node<E> prev = x.prev;
11.     // 如果前一个节点为空，则说明当前节点是头节点
12.     if (prev == null) {
13.         // 直接让链表头指向当前节点的下一个节点
14.         first = next;
15.     } else { // 如果前一个节点不为空
16.         // 将前一个节点的 next 指针指向当前节点的下一个节点
17.         prev.next = next;
18.         // 将当前节点的 prev 指针置为 null，，方便 GC 回收
19.         x.prev = null;
20.     }
22.     // 如果下一个节点为空，则说明当前节点是尾节点
23.     if (next == null) {
24.         // 直接让链表尾指向当前节点的前一个节点
25.         last = prev;
26.     } else { // 如果下一个节点不为空
27.         // 将下一个节点的 prev 指针指向当前节点的前一个节点
28.         next.prev = prev;
29.         // 将当前节点的 next 指针置为 null，方便 GC 回收
30.         x.next = null;
31.     }
33.     // 将当前节点元素置为 null，方便 GC 回收
34.     x.item = null;
35.     size--;
36.     modCount++;
37.     return element;
38. }

复制代码

unlink() 方法的逻辑如下：

• 起首获取待删除节点 x 的前驱和后继节点；
  
• 判断待删除节点是否为头节点或尾节点：
  

• 
  
  
  
  • 如果 x 是头节点，则将 first 指向 x 的后继节点 next
    
  • 如果 x 是尾节点，则将 last 指向 x 的前驱节点 prev
    
  • 如果 x 不是头节点也不是尾节点，实行下一步操纵
    
  
  

• 将待删除节点 x 的前驱的后继指向待删除节点的后继 next，断开 x 和 x.prev 之间的链接；
  
• 将待删除节点 x 的后继的前驱指向待删除节点的前驱 prev，断开 x 和 x.next 之间的链接；
  
• 将待删除节点 x 的元素置空，修改链表长度。
  

可以参考下图明白（图源：LinkedList 源码分析(JDK 1.8)）：

unlink 方法逻辑
2.2.5. 遍历链表

保举利用for-each 循环来遍历 LinkedList 中的元素， for-each 循环终极会转换成迭代器情势。

1. LinkedList<String> list = new LinkedList<>();
2. list.add("apple");
3. list.add("banana");
4. list.add("pear");
6. for (String fruit : list) {
7.     System.out.println(fruit);
8. }

复制代码

LinkedList 的遍历的焦点就是它的迭代器的实现。

1. // 双向迭代器
2. private class ListItr implements ListIterator<E> {
3.     // 表示上一次调用 next() 或 previous() 方法时经过的节点；
4.     private Node<E> lastReturned;
5.     // 表示下一个要遍历的节点；
6.     private Node<E> next;
7.     // 表示下一个要遍历的节点的下标，也就是当前节点的后继节点的下标；
8.     private int nextIndex;
9.     // 表示当前遍历期望的修改计数值，用于和 LinkedList 的 modCount 比较，判断链表是否被其他线程修改过。
10.     private int expectedModCount = modCount;
11.     …………
12. }

复制代码

下面我们对迭代器 ListItr 中的焦点方法举行具体先容。
我们先来看下重新到尾方向的迭代：

1. // 判断还有没有下一个节点
2. public boolean hasNext() {
3.     // 判断下一个节点的下标是否小于链表的大小，如果是则表示还有下一个元素可以遍历
4.     return nextIndex < size;
5. }
6. // 获取下一个节点
7. public E next() {
8.     // 检查在迭代过程中链表是否被修改过
9.     checkForComodification();
10.     // 判断是否还有下一个节点可以遍历，如果没有则抛出 NoSuchElementException 异常
11.     if (!hasNext())
12.         throw new NoSuchElementException();
13.     // 将 lastReturned 指向当前节点
14.     lastReturned = next;
15.     // 将 next 指向下一个节点
16.     next = next.next;
17.     nextIndex++;
18.     return lastReturned.item;
19. }

复制代码

再来看一下从尾到头方向的迭代：

1. // 判断是否还有前一个节点
2. public boolean hasPrevious() {
3.     return nextIndex > 0;
4. }
6. // 获取前一个节点
7. public E previous() {
8.     // 检查是否在迭代过程中链表被修改
9.     checkForComodification();
10.     // 如果没有前一个节点，则抛出异常
11.     if (!hasPrevious())
12.         throw new NoSuchElementException();
13.     // 将 lastReturned 和 next 指针指向上一个节点
14.     lastReturned = next = (next == null) ? last : next.prev;
15.     nextIndex--;
16.     return lastReturned.item;
17. }

复制代码

如果必要删除或插入元素，也可以利用迭代器举行操纵。

1. LinkedList<String> list = new LinkedList<>();
2. list.add("apple");
3. list.add(null);
4. list.add("banana");
6. //  Collection 接口的 removeIf 方法底层依然是基于迭代器
7. list.removeIf(Objects::isNull);
9. for (String fruit : list) {
10.     System.out.println(fruit);
11. }

复制代码

迭代器对应的移除元素的方法如下：

1. // 从列表中删除上次被返回的元素
2. public void remove() {
3.     // 检查是否在迭代过程中链表被修改
4.     checkForComodification();
5.     // 如果上次返回的节点为空，则抛出异常
6.     if (lastReturned == null)
7.         throw new IllegalStateException();
9.     // 获取当前节点的下一个节点
10.     Node<E> lastNext = lastReturned.next;
11.     // 从链表中删除上次返回的节点
12.     unlink(lastReturned);
13.     // 修改指针
14.     if (next == lastReturned)
15.         next = lastNext;
16.     else
17.         nextIndex--;
18.     // 将上次返回的节点引用置为 null，方便 GC 回收
19.     lastReturned = null;
20.     expectedModCount++;
21. }

复制代码

2.3. LinkedList 常用方法测试

代码：

1. // 创建 LinkedList 对象
2. LinkedList<String> list = new LinkedList<>();
4. // 添加元素到链表末尾
5. list.add("apple");
6. list.add("banana");
7. list.add("pear");
8. System.out.println("链表内容：" + list);
10. // 在指定位置插入元素
11. list.add(1, "orange");
12. System.out.println("链表内容：" + list);
14. // 获取指定位置的元素
15. String fruit = list.get(2);
16. System.out.println("索引为 2 的元素：" + fruit);
18. // 修改指定位置的元素
19. list.set(3, "grape");
20. System.out.println("链表内容：" + list);
22. // 删除指定位置的元素
23. list.remove(0);
24. System.out.println("链表内容：" + list);
26. // 删除第一个出现的指定元素
27. list.remove("banana");
28. System.out.println("链表内容：" + list);
30. // 获取链表的长度
31. int size = list.size();
32. System.out.println("链表长度：" + size);
34. // 清空链表
35. list.clear();
36. System.out.println("清空后的链表：" + list);

复制代码

输出：

1. 索引为 2 的元素：banana
2. 链表内容：[apple, orange, banana, grape]
3. 链表内容：[orange, banana, grape]
4. 链表内容：[orange, grape]
5. 链表长度：2
6. 清空后的链表：[]

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金