当前位置: 首页 > news >正文

Java基础系列-LinkedList源码解析

文章目录

  • 简介
    • LinkedList 插入和删除元素的时间复杂度?
    • LinkedList 为什么不能实现 RandomAccess 接口?
  • LinkedList 源码分析
    • Node 定义
    • 初始化
    • 获取元素
    • 插入元素
    • 删除元素
    • 遍历链表

简介

LinkedList 是一个基于双向链表实现的集合类,经常被拿来和 ArrayList 做比较。
在这里插入图片描述

不过,我们在项目中一般是不会使用到 LinkedList 的,需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替,并且,性能通常会更好!就连 LinkedList 的作者约书亚 · 布洛克(Josh Bloch)自己都说从来不会使用 LinkedList

另外,不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1),其他情况增删元素的平均时间复杂度都是 O(n) 。

LinkedList 插入和删除元素的时间复杂度?

  • 头部插入/删除:只需要修改头结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。

  • 尾部插入/删除:只需要修改尾结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。

  • 指定位置插入/删除:需要先移动到指定位置,再修改指定节点的指针完成插入/删除,不过由于有头尾指针,可以从较近的指针出发,因此需要遍历平均 n/4 个元素,时间复杂度为 O(n)。

LinkedList 为什么不能实现 RandomAccess 接口?

RandomAccess 是一个标记接口,用来表明实现该接口的类支持随机访问(即可以通过索引快速访问元素)。由于 LinkedList 底层数据结构是链表,内存地址不连续,只能通过指针来定位,不支持随机快速访问,所以不能实现 RandomAccess 接口。

LinkedList 源码分析

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 中有一个无参构造函数和一个有参构造函数。

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

获取元素

LinkedList获取元素相关的方法一共有 3 个:

  1. getFirst():获取链表的第一个元素。

  2. getLast():获取链表的最后一个元素。

  3. get(int index):获取链表指定位置的元素。

// 获取链表的第一个元素
public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;
}// 获取链表的最后一个元素
public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;
}// 获取链表指定位置的元素
public E get(int index) {// 下标越界检查,如果越界就抛异常checkElementIndex(index);// 返回链表中对应下标的元素return node(index).item;
}

这里的核心在于 node(int index) 这个方法:

// 返回指定下标的非空节点
Node<E> node(int index) {// 断言下标未越界// assert isElementIndex(index);// 如果index小于size的二分之一  从前开始查找(向后查找)  反之向前查找if (index < (size >> 1)) {Node<E> x = first;// 遍历,循环向后查找,直至 i == indexfor (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(int index)remove(int index) 等方法内部都调用了该方法来获取对应的节点。

从这个方法的源码可以看出,该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半,就从链表头开始遍历,反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点,充分利用了双向链表的特性来提高效率。

插入元素

在这里插入图片描述

add() 方法有两个版本:

  • add(E e):用于在 LinkedList 的尾部插入元素,即将新元素作为链表的最后一个元素,时间复杂度为 O(1)。

  • add(int index, E element):用于在指定位置插入元素。这种插入方式需要先移动到指定位置,再修改指定节点的指针完成插入/删除,因此需要移动平均 n/4 个元素,时间复杂度为 O(n)

// 在链表尾部插入元素
public boolean add(E e) {linkLast(e);return true;
}// 在链表指定位置插入元素
public void add(int index, E element) {// 下标越界检查checkPositionIndex(index);// 判断 index 是不是链表尾部位置if (index == size)// 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可linkLast(element);else// 如果不是则调用 linkBefore 方法将其插入指定元素之前linkBefore(element, node(index));
}// 将元素节点插入到链表尾部
void linkLast(E e) {// 将最后一个元素赋值(引用传递)给节点 lfinal Node<E> l = last;// 创建节点,并指定节点前驱为链表尾节点 last,后继引用为空final Node<E> newNode = new Node<>(l, e, null);// 将 last 引用指向新节点last = newNode;// 判断尾节点是否为空// 如果 l 是null 意味着这是第一次添加元素if (l == null)// 如果是第一次添加,将first赋值为新节点,此时链表只有一个元素first = newNode;else// 如果不是第一次添加,将新节点赋值给l(添加前的最后一个元素)的nextl.next = newNode;size++;modCount++;
}// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {// assert succ != null;断言 succ不为 null// 定义一个节点元素保存 succ 的 prev 引用,也就是它的前一节点信息final Node<E> pred = succ.prev;// 初始化节点,并指明前驱和后继节点final Node<E> newNode = new Node<>(pred, e, succ);// 将 succ 节点前驱引用 prev 指向新节点succ.prev = newNode;// 判断前驱节点是否为空,为空表示 succ 是第一个节点if (pred == null)// 新节点成为第一个节点first = newNode;else// succ 节点前驱的后继引用指向新节点pred.next = newNode;size++;modCount++;
}

删除元素

LinkedList删除元素相关的方法一共有 5 个,可以直接看核心方法 unlink:

  1. removeFirst():删除并返回链表的第一个元素。

  2. removeLast():删除并返回链表的最后一个元素。

  3. remove(E e):删除链表中首次出现的指定元素,如果不存在该元素则返回 false。

  4. remove(int index):删除指定索引处的元素,并返回该元素的值。

  5. void clear():移除此链表中的所有元素。

// 删除并返回链表的第一个元素
public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);
}// 删除并返回链表的最后一个元素
public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);
}// 删除链表中首次出现的指定元素,如果不存在该元素则返回 false
public boolean remove(Object o) {// 如果指定元素为 null,遍历链表找到第一个为 null 的元素进行删除if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {// 如果不为 null ,遍历链表找到要删除的节点for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}// 删除链表指定位置的元素
public E remove(int index) {// 下标越界检查,如果越界就抛异常checkElementIndex(index);return unlink(node(index));
}

这里的核心在于 unlink(Node<E> x) 这个方法:

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,,方便 GC 回收x.prev = null;}// 如果下一个节点为空,则说明当前节点是尾节点if (next == null) {// 直接让链表尾指向当前节点的前一个节点last = prev;} else { // 如果下一个节点不为空// 将下一个节点的 prev 指针指向当前节点的前一个节点next.prev = prev;// 将当前节点的 next 指针置为 null,方便 GC 回收x.next = null;}// 将当前节点元素置为 null,方便 GC 回收x.item = null;size--;modCount++;return element;
}

unlink() 方法的逻辑如下:

  1. 首先获取待删除节点 x 的前驱和后继节点;

  2. 判断待删除节点是否为头节点或尾节点:

    • 如果 x 是头节点,则将 first 指向 x 的后继节点 next

    • 如果 x 是尾节点,则将 last 指向 x 的前驱节点 prev

    • 如果 x 不是头节点也不是尾节点,执行下一步操作

  3. 将待删除节点 x 的前驱的后继指向待删除节点的后继 next,断开 x 和 x.prev 之间的链接;

  4. 将待删除节点 x 的后继的前驱指向待删除节点的前驱 prev,断开 x 和 x.next 之间的链接;

  5. 将待删除节点 x 的元素置空,修改链表长度。

在这里插入图片描述

遍历链表

推荐使用for-each 循环来遍历 LinkedList 中的元素, for-each 循环最终会转换成迭代器形式。

LinkedList<String> list = new LinkedList<>();
list.add("apple");
list.add("banana");
list.add("pear");for (String fruit : list) {System.out.println(fruit);
}

LinkedList 的遍历的核心就是它的迭代器的实现。

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

下面我们对迭代器 ListItr 中的核心方法进行详细介绍。

我们先来看下从头到尾方向的迭代:

// 判断还有没有下一个节点
public boolean hasNext() {// 判断下一个节点的下标是否小于链表的大小,如果是则表示还有下一个元素可以遍历return nextIndex < size;
}
// 获取下一个节点
public E next() {// 检查在迭代过程中链表是否被修改过checkForComodification();// 判断是否还有下一个节点可以遍历,如果没有则抛出 NoSuchElementException 异常if (!hasNext())throw new NoSuchElementException();// 将 lastReturned 指向当前节点lastReturned = next;// 将 next 指向下一个节点next = next.next;nextIndex++;return lastReturned.item;
}

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

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

如果需要删除或插入元素,也可以使用迭代器进行操作。

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

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

// 从列表中删除上次被返回的元素
public void remove() {// 检查是否在迭代过程中链表被修改checkForComodification();// 如果上次返回的节点为空,则抛出异常if (lastReturned == null)throw new IllegalStateException();// 获取当前节点的下一个节点Node<E> lastNext = lastReturned.next;// 从链表中删除上次返回的节点unlink(lastReturned);// 修改指针if (next == lastReturned)next = lastNext;elsenextIndex--;// 将上次返回的节点引用置为 null,方便 GC 回收lastReturned = null;expectedModCount++;
}
http://www.xdnf.cn/news/685.html

相关文章:

  • Vue项目Webpack Loader全解析:从原理到实战配置指南
  • MYOJ_11700(UVA10591)Happy Number(快乐数)(超快解法:图论思想解题)
  • JVM考古现场(二十二):降维打击·用二向箔优化内存模型
  • android如何在生产环境中做到详实的日志收集而不影响性能?
  • 算法之贪心算法
  • 【音视频】音视频FLV合成实战
  • Pikachu靶场-CSRF
  • Golang errors 包快速上手
  • 使用Qt multimedia模块实现简易的视频播放器
  • AI在能源消耗管理及能源效率提升中的核心应用场景及技术实现
  • Java性能剖析工具箱
  • 数据结构——反射、枚举以及lambda表达式
  • Qt 性能优化总结
  • Django 实现物联网管理系统的详细方案
  • 使用 OpenRewrite 简化 Java 和 SpringBoot 迁移
  • SDL基础
  • MATLAB 控制系统设计与仿真 - 34
  • 机器学习 | 细说Deep Q-Network(DQN)
  • 学习笔记十六——Rust Monad从头学
  • 【音视频】FLV格式分析
  • 让SQL飞起来:搭建企业AI应用的SQL性能优化实战
  • 2025年4月16日华为留学生笔试第二题200分
  • VS2022+QT环境配置及基本操作
  • Prometheus thanos架构
  • 2025年4月16日华为留学生笔试第三题300分
  • 自求导实现线性回归与PyTorch张量详解
  • Unity3d 6(6000.*.*)版本国区下载安装参考
  • 机器学习简介
  • python20-while和for in的美
  • 2025能源网络安全大赛CTF --- Crypto wp