- 1会话劫持 攻击：了解 和预防_会话数攻击
- 2vscode用git进行pull操作时提示:在签出前请清理存储库工作树_please clean your respository
- 3ShardingSphere系列01：Shardingjdbc实现分表（含项目实践）_shardingsphere分表
- 4时空预测 | 基于深度学习的碳排放时空预测模型_深度学习 发动机积碳预测
- 5互联网大厂职场各职级P6/P7和核心能力_大厂p7
- 6post formdata传值
- 72024年分布式场景下的并发安全问题，互联网行业“中年”危机_java并发安全问题案例分享
- 82022，银行数据能力怎么建？_如何构建商业银行的数据分析能力
- 9one-api离线安装解决failed to get gpt-3.5-turbo token encoder_failed to get gpt-3.5-turbo token encoder:
- 10全面理解Python中的迭代器_python 迭代器
LinkedList详解(含数据结构动画演示)_linkedlist 结构
赞
踩
目录
LinkedList详解
LinkedList用的不多，但是其内部的双向链表实现还是值得去探讨学习的。
1、LinkedList的继承体系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- 1
- 2
- 3
可以看到和ArrayList还是有不少区别的
需要注意的两个点：
-
①、LinkedList没有实现RandomAccess接口，意味着LinkedList不支持快速随机访问。这是由LinkedList的数据结构决定的。由于LinkedList 底层数据结构是链表，内存地址是不连续的，只能通过指针来定位，不像ArrayList底层是数组结构内存地址是连续的，可以通过数组的下标快速定位元素。所以LinkedList没有实现RandomAccess接口。
-
②、LinkedList实现了Deque接口，说明LinkedList支持双向链表的操作，比如addFirst，addLast等方法。
2、LinkedList的构造函数
①、无参构造
public LinkedList() {
}
- 1
- 2
②、有参构造
public LinkedList(Collection<? extends E> c) {
// 调用无参构造函数，初始化LinkedList实例
this();
// 将传入的集合c中的所有元素添加到当前LinkedList实例中
addAll(c);
}
- 1
- 2
- 3
- 4
- 5
- 6
3、LinkedList的add(E e)方法
add(E e)方法
public boolean add(E e) {
// 调用linkLast方法将元素e添加到链表的末尾
linkLast(e);
// 返回true，表示元素添加成功
return true;
}
- 1
- 2
- 3
- 4
- 5
- 6
linkLast(E e)方法
// 用于跟踪修改次数的计数器，主要用于迭代器的快速失败（fail-fast）机制 protected transient int modCount = 0; // 链表中元素的数量 transient int size = 0; // 链表的第一个节点引用 transient Node<E> first; // 链表的最后一个节点引用 transient Node<E> last; void linkLast(E e) { // 将当前链表的最后一个节点引用保存到局部变量l中 // 这样可以方便后续对链表末尾进行操作 final Node<E> l = last; // 创建一个新的节点，节点的前驱是l（即当前的最后一个节点）， // 节点包含的元素是e，后继节点为null（因为新节点将成为最后一个节点） final Node<E> newNode = new Node<>(l, e, null); // 更新链表的最后一个节点引用为新创建的节点 last = newNode; // 检查链表是否为空（即当前没有任何节点） // 如果链表为空（即last为null），那么新节点也是第一个节点 if (l == null) // 将链表的第一个节点引用也更新为新创建的节点 first = newNode; else // 如果链表不为空（即已有节点）， // 那么将当前最后一个节点的next指向新创建的节点 l.next = newNode; // 链表的元素数量增加1 size++; // 修改计数器增加1 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
上面的modCount在ArrayList详解的文章中已经介绍过来，这里就不再赘述。
我们需要关注LinkedList的核心 Node，可以叫节点。
4、LinkedList的Node节点
可以把每个Node节点理解为一个带有前后钩子的盒子，这个盒子里装着一个元素（item），通过前后两个钩子（prev和next）连接到前后的盒子（节点），形成一个双向链表的数据结构。
Node类是LinkedList的一个静态内部类，用于表示链表中的每个节点。
每个节点包含一个元素（item），指向前一个节点的引用（prev）和指向后一个节点的引用（next）。
private static class Node<E> { // 节点中存储的元素 E item; // 指向下一个节点的引用 Node<E> next; // 指向前一个节点的引用 Node<E> prev; // Node类的构造函数，用于创建一个新节点 // 参数prev是指向前一个节点的引用，element是当前节点中存储的元素，next是指向下一个节点的引用 Node(Node<E> prev, E element, Node<E> next) { // 将传入的元素赋值给item，表示节点中存储的元素 this.item = element; // 将传入的下一个节点引用赋值给next this.next = next; // 将传入的前一个节点引用赋值给prev this.prev = prev; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
5、双向链表的概念和Node节点的详细解释
双向链表（Doubly Linked List）是一种链表数据结构。
其中每个节点包含三个主要部分：
存储的元素（数据）;
指向前一个节点的引用（前驱）;
指向后一个节点的引用（后继）;
这种结构允许从任意节点向前或向后遍历链表，提供了比单向链表更灵活的操作。
在双向链表中，Node节点是链表的基本组成部分。每个节点都包含存储的元素以及指向前一个节点和后一个节点的引用。
Node节点的结构如下：
- 元素（item）：节点中存储的数据，这可以是任意类型的对象。
- 前驱节点引用（prev）：指向链表中前一个节点的引用。如果当前节点是链表的第一个节点，则这个引用为null。
- 后继节点引用（next）：指向链表中下一个节点的引用。如果当前节点是链表的最后一个节点，则这个引用为null。
单向链表和双向链表的图示：
6、LinkedList的add(E e)方法梳理
通过空参构造新建LinkedList实例
下面分析添加 “秀逗” 、“四眼” 两个元素的过程
LinkedList<String> list = new LinkedList<>();
list.add("秀逗");
list.add("四眼");
- 1
- 2
- 3
执行无参构造创建 LinkedList实例
// 用于跟踪修改次数的计数器，主要用于迭代器的快速失败（fail-fast）机制
protected transient int modCount = 0;
// 链表中元素的数量
transient int size = 0;
// 链表的第一个节点引用
transient Node<E> first;
// 链表的最后一个节点引用
transient Node<E> last;
public LinkedList() {
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
执行add方法 添加"秀逗"
public boolean add(E e) {
// 调用linkLast方法将元素e添加到链表的末尾
linkLast(e);
// 始终返回true，表示元素添加成功
return true;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 调用linkLast(E e)方法：这是将"秀逗"添加到链表末尾的具体实现方法。
void linkLast(E e) { // 将当前链表的最后一个节点引用保存到局部变量l中 final Node<E> l = last; // 创建一个新的节点，节点的前驱是l（即当前的最后一个节点）， // 节点包含的元素是e，后继节点为null（因为新节点将成为最后一个节点） final Node<E> newNode = new Node<>(l, e, null); // 更新链表的最后一个节点引用为新创建的节点 last = newNode; // 检查链表是否为空（即当前没有任何节点） // 如果链表为空（即last为null），那么新节点也是第一个节点 if (l == null) // 将链表的第一个节点引用也更新为新创建的节点 first = newNode; else // 如果链表不为空（即已有节点）， // 那么将当前最后一个节点的next指向新创建的节点 l.next = newNode; // 链表的元素数量增加1 size++; // 修改计数器增加1 // 这个计数器在结构发生变化（例如添加或删除元素）时增加， // 用于实现迭代器的快速失败机制，检测并发修改 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
下面把添加过程串起来
-
1.保存当前最后一个节点的引用到局部变量 l：
final Node<E> l = last;// 由于last在空参构造的初始化为null ，所以 l为null -
2.创建一个新的节点newNode：
final Node<E> newNode = new Node<>(l, e, null);
newNode的前驱节点为l（当前的最后一个节点） 值为null。
newNode包含的元素为 “秀逗” 。
newNode的后继节点为null（因为它将成为新的最后一个节点）。 -
3.更新链表的最后一个节点引用为newNode：
last = newNode;// 将last更新为newNode。 -
4.检查链表是否为空：
if (l == null) first = newNode;
l 现在为空 ，说明这是链表中的第一个节点。
将链表的第一个节点引用first也更新为newNode。 -
5.增加链表的元素数量：
将链表的大小size增加1。 -
6.增加修改计数器modCount：
用于实现迭代器的快速失败机制，检测并发修改。 -
- 再添加 “四眼” 这个元素
保存当前最后一个节点的引用到局部变量 l：
final Node<E> l = last;// 由于last在添加"秀逗"的时候已经赋值了
所以这里 l 是有值的
- 再添加 “四眼” 这个元素
-
8.再创建一个新的节点newNode：
final Node<E> newNode = new Node<>(l, e, null);
newNode的前驱节点为l（当前的最后一个节点） 值为 “秀逗” 。
newNode包含的元素为 “四眼” 。
newNode的后继节点为null（因为它将成为新的最后一个节点）。 -
9.再更新链表的最后一个节点引用为newNode：
last = newNode;// 将last更新为newNode。 此时"四眼"就成了最后一个元素 -
10.再检查链表是否为空：
if (l == null) first = newNode; else l.next = newNode;
l 现在为 “秀逗” ，不为空，讲 l 的下一个节点引用 next 指向 newNode 也就是 “四眼”。
这就完成了 “秀逗” ， “四眼” 两个元素的 添加。
最终图示：
7、LinkedList的getXXX方法
LinkedList获取元素的方法有下面几个:
getFirst()：获取链表的第一个元素。
getLast()：获取链表的最后一个元素。
get(int index)：获取链表指定位置的元素。
我在ArrayList详解里面并没有去讲解get方法，因为ArrayList中的get并没有什么好讲的。
// ArrayList中的get方法
public E get(int index) {
// 先检查数组下标有没有越界
rangeCheck(index);
// 返回对应位置的元素
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
但是LinkedList的getXXX方法是值得深入学一学的：
先看下最简单的两个 getFirst和getLast
public E getFirst() { // 获取链表的第一个节点引用，并将其保存在局部变量f中 final Node<E> f = first; // 如果第一个节点为null，表示链表为空 if (f == null) // 抛出NoSuchElementException异常，表示没有元素可以返回 throw new NoSuchElementException(); // 返回第一个节点中的元素 return f.item; } public E getLast() { // 获取链表的最后一个节点引用，并将其保存在局部变量l中 final Node<E> l = last; // 如果最后一个节点为null，表示链表为空 if (l == null) // 抛出NoSuchElementException异常，表示没有元素可以返回 throw new NoSuchElementException(); // 返回最后一个节点中的元素 return l.item; }
- 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
最值得去探究的是 get(int index)：获取链表指定位置的元素。
我们知道LinkedList是链表结构，无法像ArrayList那样快速随机访问。那么LinkedList想根据下标去找到某个元素就只能靠遍历了。
看下具体是怎么实现的：
public E get(int index) { // 检查元素索引是否合法，如果不合法会抛出 IndexOutOfBoundsException checkElementIndex(index); // 获取指定索引的节点并返回其包含的元素 return node(index).item; } Node<E> node(int index) { // 判断索引在链表中的位置，以决定从头部还是尾部开始遍历 // size >> 1 计算链表长度/2 向下取整 // 如果size是偶数 右移一位的结果就是size的一半 如果size是奇数 右移一位的结果就是size的一半再减0.5 if (index < (size >> 1)) { // 如果索引在前半部分，从头部开始遍历 Node<E> x = first; // 通过不断访问 next 来找到指定索引的节点 for (int i = 0; i < index; i++) x = x.next; return x; } else { // 如果索引在后半部分，从尾部开始遍历 Node<E> x = last; // 通过不断访问 prev 来找到指定索引的节点 for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
- 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
这里我做了个动画来演示查找的过程。
- ①、从链表头部开始遍历
public static void main(String[] args){
LinkedList<String> list = new LinkedList<>(Arrays.asList("1","2","秀逗","4","5","6","7","四眼","9","10"));
String s = list.get(2);
System.out.println(s); // 秀逗
}
- 1
- 2
- 3
- 4
- 5
由于下标2 小于整个链表长度size 10右移一位 10 >> 1 = 5, 即2<5， 就从链表的头部开始遍历
- ②、从链表尾部开始遍历
public static void main(String[] args){
LinkedList<String> list = new LinkedList<>(Arrays.asList("1","2","秀逗","4","5","6","7","四眼","9","10"));
String s = list.get(7);
System.out.println(s); // 四眼
}
- 1
- 2
- 3
- 4
- 5
由于下标7 大于整个链表长度size 10右移一位 10 >> 1 = 5, 即7>5， 就从链表的尾部开始遍历
8、LinkedList的removeXXX方法
LinkedList删除元素的方法有下面几个:
- ①、removeFirst()：删除并返回链表的第一个元素。
- ②、removeLast()：删除并返回链表的最后一个元素。
- ③、remove(E e)：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。
- ④、remove(int index)：删除指定索引处的元素，并返回该元素的值。
①、removeFirst()方法 (移除LinkedList的第一个元素)：
public E removeFirst() { // 获取链表的第一个节点，赋值给变量 f final Node<E> f = first; // 如果链表为空，即第一个节点为 null，抛出 NoSuchElementException 异常 if (f == null) throw new NoSuchElementException(); // 调用 unlinkFirst 方法，从链表中移除第一个节点 return unlinkFirst(f); } private E unlinkFirst(Node<E> f) { // 确保 f 是第一个节点且不为 null 的断言，注释掉的是因为在实际代码中没有执行断言检查的需要 // assert f == first && f != null; // 保存第一个节点的值 final E element = f.item; // 保存第一个节点的下一个节点 final Node<E> next = f.next; // 将第一个节点的值设为 null，帮助垃圾回收 f.item = null; // 将第一个节点的 next 指针设为 null，帮助垃圾回收 f.next = null; // 更新链表的头节点为原头节点的下一个节点 first = next; // 如果更新后的头节点为 null，说明链表现在为空，更新尾节点为 null if (next == null) last = null; else // 如果更新后的头节点不为 null，将它的 prev 指针设为 null next.prev = null; // 链表长度减一 size--; // 修改计数器增加一，用于记录链表结构的修改次数 modCount++; // 返回被移除的节点的值 return 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
- 34
- 35
- 36
- 37
- 38
总结一下：
-
1.removeFirst() 方法：
首先，获取链表的第一个节点，并检查其是否为 null。
如果链表为空，则抛出 NoSuchElementException 异常。
否则，调用 unlinkFirst(f) 方法从链表中移除第一个节点，并返回该节点的值。 -
2.unlinkFirst(Node f) 方法：
保存要移除的节点的值和它的下一个节点。
将要移除节点的 item 和 next 设为 null，以帮助垃圾回收。
更新链表的头节点为原头节点的下一个节点。如果新头节点为 null，说明链表现在为空，因此将尾节点也设为 null；否则，将新头节点的 prev 指针设为 null。
减少链表的大小，并增加修改计数器。
返回被移除节点的值。
②、removeLast()方法 (移除LinkedList的最后一个元素)：
public E removeLast() { // 获取链表的最后一个节点，赋值给变量 l final Node<E> l = last; // 如果链表为空，即最后一个节点为 null，抛出 NoSuchElementException 异常 if (l == null) throw new NoSuchElementException(); // 调用 unlinkLast 方法，从链表中移除最后一个节点 return unlinkLast(l); } private E unlinkLast(Node<E> l) { // 确保 l 是最后一个节点且不为 null 的断言，注释掉的是因为在实际代码中没有执行断言检查的需要 // assert l == last && l != null; // 保存最后一个节点的值 final E element = l.item; // 保存最后一个节点的前一个节点 final Node<E> prev = l.prev; // 将最后一个节点的值设为 null，帮助垃圾回收 l.item = null; // 将最后一个节点的 prev 指针设为 null，帮助垃圾回收 l.prev = null; // 更新链表的尾节点为原尾节点的前一个节点 last = prev; // 如果更新后的尾节点为 null，说明链表现在为空，更新头节点为 null if (prev == null) first = null; else // 如果更新后的尾节点不为 null，将它的 next 指针设为 null prev.next = null; // 链表长度减一 size--; // 修改计数器增加一，用于记录链表结构的修改次数 modCount++; // 返回被移除的节点的值 return 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
- 34
- 35
- 36
- 37
总结一下：
-
1.removeLast() 方法：
首先，获取链表的最后一个节点，并检查其是否为 null。
如果链表为空，则抛出 NoSuchElementException 异常。
否则，调用 unlinkLast(l) 方法从链表中移除最后一个节点，并返回该节点的值。 -
2.unlinkLast(Node l) 方法：
保存要移除的节点的值和它的前一个节点。
将要移除节点的 item 和 prev 设为 null，以帮助垃圾回收。
更新链表的尾节点为原尾节点的前一个节点。如果新尾节点为 null，说明链表现在为空，因此将头节点也设为 null；否则，将新尾节点的 next 指针设为 null。
减少链表的大小，并增加修改计数器。
返回被移除节点的值。
③、remove(E e)方法 (这个方法值得深入)
public boolean remove(Object o) { // 如果要移除的元素为 null if (o == null) { // 从链表的第一个节点开始遍历 for (Node<E> x = first; x != null; x = x.next) { // 如果当前节点的值为 null if (x.item == null) { // 调用 unlink 方法移除当前节点 unlink(x); // 返回 true 表示成功移除元素 return true; } } } else { // 如果要移除的元素不为 null // 从链表的第一个节点开始遍历 for (Node<E> x = first; x != null; x = x.next) { // 如果当前节点的值与要移除的元素相等 if (o.equals(x.item)) { // 调用 unlink 方法移除当前节点 unlink(x); // 返回 true 表示成功移除元素 return true; } } } // 如果遍历整个链表没有找到要移除的元素，返回 false return false; }
- 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
E unlink(Node<E> x) { // 确保 x 不为 null 的断言，注释掉的是因为在实际代码中没有执行断言检查的需要 // 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 { // 否则，将前一个节点的 next 指向要移除节点的下一个节点 prev.next = next; // 将要移除节点的 prev 指针设为 null，帮助垃圾回收 x.prev = null; } // 如果要移除的节点是最后一个节点 if (next == null) { // 更新链表的尾节点为要移除节点的前一个节点 last = prev; } else { // 否则，将下一个节点的 prev 指向要移除节点的前一个节点 next.prev = prev; // 将要移除节点的 next 指针设为 null，帮助垃圾回收 x.next = null; } // 将要移除节点的值设为 null，帮助垃圾回收 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
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
总结一下：
remove(Object o) 方法：
该方法用于从链表中移除第一个与给定元素 o 相等的节点。
如果 o 为 null，则遍历链表，找到第一个节点值为 null 的节点，并调用 unlink(x) 方法移除该节点，返回 true。
如果 o 不为 null，则遍历链表，找到第一个节点值与 o 相等的节点，并调用 unlink(x) 方法移除该节点，返回 true。
如果遍历完整个链表没有找到与 o 相等的节点，返回 false。
unlink(Node<E> x) 方法：
该方法用于从链表中移除指定的节点 x。
保存要移除节点的值、下一个节点和前一个节点。
如果要移除的节点是第一个节点，则更新链表的头节点为下一个节点；否则，将前一个节点的 next 指针指向下一个节点，并将要移除节点 的 prev 指针设为 null。
如果要移除的节点是最后一个节点，则更新链表的尾节点为前一个节点；否则，将下一个节点的 prev 指针指向前一个节点，并将要移除节点的 next 指针设为 null。
将要移除节点的值设为 null，以帮助垃圾回收。
链表的长度减一，并增加修改计数器。
返回被移除节点的值。
这里还是做个动画帮助理解 双向链表移除某个数据的过程：
可以看到最后
秀逗的pre 和 next 都被置为了null。
这样做可以确保该节点与链表完全断开连接，从而有助于垃圾回收机制回收该节点。
④、remove(int index)方法
这个方法 实际上在上面的分析中都提到了：
比如checkElementIndex、unlink、node方法在上面都有。
所以这个只给出方法注释 就不总结画图了。
public E remove(int index) {
// 检查给定的索引是否在链表的有效范围内
checkElementIndex(index);
// 找到给定索引处的节点并移除它，返回被移除节点的值
return unlink(node(index));
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
private void checkElementIndex(int index) {
// 如果给定的索引不是有效的元素索引，抛出 IndexOutOfBoundsException 异常
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 1
- 2
- 3
- 4
- 5
- 6
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; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
E unlink(Node<E> x) { // 确保 x 不为 null 的断言，注释掉的是因为在实际代码中没有执行断言检查的需要 // 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 { // 否则，将前一个节点的 next 指向要移除节点的下一个节点 prev.next = next; // 将要移除节点的 prev 指针设为 null，帮助垃圾回收 x.prev = null; } // 如果要移除的节点是最后一个节点 if (next == null) { // 更新链表的尾节点为要移除节点的前一个节点 last = prev; } else { // 否则，将下一个节点的 prev 指向要移除节点的前一个节点 next.prev = prev; // 将要移除节点的 next 指针设为 null，帮助垃圾回收 x.next = null; } // 将要移除节点的值设为 null，帮助垃圾回收 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
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
最后还有个clear方法 也很有意思
也来看下 这可比 ArrayList的 clear方法麻烦多了
public void clear() { // 清除所有节点之间的链接是“非必要”的，但这样做有以下好处： // - 如果被丢弃的节点跨越多个垃圾分代，有助于分代的垃圾回收 (generational GC) // - 即使存在可达的迭代器，也能确保释放内存 // 从链表的第一个节点开始 for (Node<E> x = first; x != null; ) { // 保存当前节点的下一个节点 Node<E> next = x.next; // 将当前节点的值设为 null，帮助垃圾回收 x.item = null; // 将当前节点的 next 指针设为 null，帮助垃圾回收 x.next = null; // 将当前节点的 prev 指针设为 null，帮助垃圾回收 x.prev = null; // 移动到下一个节点 x = next; } // 将链表的头节点和尾节点设为 null，表示链表为空 first = last = null; // 将链表的大小设为 0 size = 0; // 修改计数器增加一，用于记录链表结构的修改次数 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
9、LinkedList的反向迭代器 DescendingIterator
DescendingIterator 可以从最后一个元素往前迭代。
public static void main(String[] args) throws Exception {
LinkedList<String> list = new LinkedList<>(Arrays.asList("1","2","秀逗","4","5","6","7","四眼","9","10"));
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
System.out.print(iterator.next() + " ");
}
System.out.println("\n=============================");
Iterator<String> descIterator = list.descendingIterator();
while (descIterator.hasNext()){
System.out.print(descIterator.next() + " ");
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
执行结果：
1 2 秀逗 4 5 6 7 四眼 9 10
=============================
10 9 四眼 7 6 5 4 秀逗 2 1
- 1
- 2
- 3
看下DescendingIterator 的实现：
// LinkedList的内部类，实现从尾部到头部的迭代器 private class DescendingIterator implements Iterator<E> { // 使用ListItr类的实例实现迭代器功能 private final ListItr itr = new ListItr(size()); // 检查是否有下一个元素（实际上是前一个元素，因为我们是反向迭代） public boolean hasNext() { // 调用ListItr的hasPrevious方法，检查是否有前一个元素 return itr.hasPrevious(); } // 获取下一个元素（实际上是前一个元素，因为我们是反向迭代） public E next() { // 调用ListItr的previous方法，返回前一个元素 return itr.previous(); } // 移除当前元素 public void remove() { // 调用ListItr的remove方法，移除当前元素 itr.remove(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
所以DescendingIterator 本质上 就是对ListItr 的包装 主要是实现细节都在 ListItr中
再看下 ListItr 的细节：
注意这个ListItr 是LinkedList的内部类 ， 而不是 AbstractList抽象类里面的 内部类 ListItr (集合API内部类的命名就不能好好区分一下吗…)
// LinkedList的内部类，实现双向列表迭代器 private class ListItr implements ListIterator<E> { // 最近返回的节点 private Node<E> lastReturned; // 下一个节点 private Node<E> next; // 下一个节点的索引 private int nextIndex; // 预期的修改计数，用于检测并发修改 private int expectedModCount = modCount; // 构造函数，根据给定的索引初始化迭代器 ListItr(int index) { // 如果索引等于列表大小，next为null next = (index == size) ? null : node(index); // 初始化下一个节点的索引 nextIndex = index; } // 检查是否有下一个元素 public boolean hasNext() { return nextIndex < size; } // 获取下一个元素 public E next() { // 检查是否有并发修改 checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); // 设置最后返回的节点为当前的下一个节点 lastReturned = next; // 移动到下一个节点 next = next.next; // 增加下一个节点的索引 nextIndex++; // 返回最后返回节点的值 return lastReturned.item; } // 检查是否有前一个元素 public boolean hasPrevious() { return nextIndex > 0; } // 获取前一个元素 public E previous() { // 检查是否有并发修改 checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); // 如果next为null，说明当前在列表的末尾 // 否则移动到前一个节点 lastReturned = next = (next == null) ? last : next.prev; // 减少下一个节点的索引 nextIndex--; // 返回最后返回节点的值 return lastReturned.item; } // 获取下一个元素的索引 public int nextIndex() { return nextIndex; } // 获取前一个元素的索引 public int previousIndex() { return nextIndex - 1; } // 移除当前元素 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 = modCount; } // 更新当前元素 public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } // 添加元素 public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount = modCount; } // 检查是否有并发修改的方法 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
- 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
