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

Collection-LinkedList源码解析

文章目录

    • 概述
    • LinkedList实现
      • 底层数据结构
      • 构造函数
      • getFirst(), getLast()
      • removeFirst(), removeLast(), remove(e), remove(index)
      • add()
      • addAll()
      • clear()
      • Positional Access 方法
      • 查找操作

概述

LinkedList同时实现了List接口和Deque接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList简直就是个全能冠军。当你需要使用栈或者队列时,可以考虑使用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类,更遗憾的是,Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列,现在的首选是ArrayDeque,它有着比LinkedList(当作栈或队列使用时)有着更好的性能。


LinkedList_base

LinkedList实现

底层数据结构

LinkedList底层通过双向链表实现,本节将着重讲解插入和删除元素时双向链表的维护过程。双向链表的每个节点用内部类Node表示。LinkedList通过firstlast引用分别指向链表的第一个和最后一个元素。当链表为空的时候firstlast都指向null

    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;

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

构造函数

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

getFirst(), getLast()

获取第一个元素, 和获取最后一个元素:

    /*** Returns the first element in this list.** @return the first element in this list* @throws NoSuchElementException if this list is empty*/public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}/*** Returns the last element in this list.** @return the last element in this list* @throws NoSuchElementException if this list is empty*/public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}

removeFirst(), removeLast(), remove(e), remove(index)

remove()方法也有两个版本,一个是删除跟指定元素相等的第一个元素remove(Object o),另一个是删除指定下标处的元素remove(int index)


LinkedList_remove.png

删除元素 - 指的是删除第一次出现的这个元素, 如果没有这个元素,则返回false;判断的依据是equals方法, 如果equals,则直接unlink这个node;由于LinkedList可存放null元素,故也可以删除第一次出现null的元素;

    /*** Removes the first occurrence of the specified element from this list,* if it is present.  If this list does not contain the element, it is* unchanged.  More formally, removes the element with the lowest index* {@code i} such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>* (if such an element exists).  Returns {@code true} if this list* contained the specified element (or equivalently, if this list* changed as a result of the call).** @param o element to be removed from this list, if present* @return {@code true} if this list contained the specified element*/public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;}/*** 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; // GCsize--;modCount++;return element;}

remove(int index)使用的是下标计数, 只需要判断该index是否有元素即可,如果有则直接unlink这个node。

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

删除head元素:

    /*** Removes and returns the first element from this list.** @return the first element from this list* @throws NoSuchElementException if this list is empty*/public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}/*** Unlinks non-null first node f.*/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 GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}

删除last元素:

	/*** Removes and returns the last element from this list.** @return the last element from this list* @throws NoSuchElementException if this list is empty*/public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}/*** Unlinks non-null last node l.*/private E unlinkLast(Node<E> l) {// assert l == last && l != null;final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}

add()

add()*方法有两个版本,一个是add(E e),该方法在*LinkedList的末尾插入元素,因为有last指向链表末尾,在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可;另一个是add(int index, E element),该方法是在指定下表处插入元素,需要先通过线性查找找到具体位置,然后修改相关引用完成插入操作。

    /*** 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;}/*** 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;elsel.next = newNode;size++;modCount++;}

LinkedList_add

add(int index, E element), 当index==size时,等同于add(E e); 如果不是,则分两步: 1.先根据index找到要插入的位置,即node(index)方法;2.修改引用,完成插入操作。

    /*** 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);elselinkBefore(element, node(index));}

addAll()

addAll(index, c) 实现方式并不是直接调用add(index,e)来实现,主要是因为效率的问题,另一个是fail-fast中modCount只会增加1次;

    /*** Appends all of the elements in the specified collection to the end of* this list, in the order that they are returned by the specified* collection's iterator.  The behavior of this operation is undefined if* the specified collection is modified while the operation is in* progress.  (Note that this will occur if the specified collection is* this list, and it's nonempty.)** @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 NullPointerException if the specified collection is null*/public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}/*** 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;elsepred.next = newNode;pred = newNode;}if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}

clear()

为了让GC更快可以回收放置的元素,需要将node之间的引用关系赋空。

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

Positional Access 方法

通过index获取元素

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

将某个位置的元素重新赋值:

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

将元素插入到指定index位置:

    /*** 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);elselinkBefore(element, node(index));}

删除指定位置的元素:

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

查找操作

查找操作的本质是查找元素的下标:

查找第一次出现的index, 如果找不到返回-1;

    /*** Returns the index of the first occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the lowest index {@code i} such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.** @param o element to search for* @return the index of the first occurrence of the specified element in*         this list, or -1 if this list does not contain the element*/public int indexOf(Object o) {int index = 0;if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}

查找最后一次出现的index, 如果找不到返回-1;

    /*** Returns the index of the last occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the highest index {@code i} such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.** @param o element to search for* @return the index of the last occurrence of the specified element in*         this list, or -1 if this list does not contain the element*/public int lastIndexOf(Object o) {int index = size;if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1;}

相关文章:

Collection-LinkedList源码解析

文章目录 概述LinkedList实现底层数据结构构造函数getFirst(), getLast()removeFirst(), removeLast(), remove(e), remove(index)add()addAll()clear()Positional Access 方法查找操作 概述 LinkedList同时实现了List接口和Deque接口&#xff0c;也就是说它既可以看作一个顺序…...

vue判断对象数组里是否有重复数据

TOCvue判断对象数组里是否有重复数据 try {//通过产品编码赛选出新的数组 在比较let names this.goodsJson.map(item > item["productCode"]);let nameSet new Set(names)if (nameSet.size ! names.length) {this.$message({message: 警告&#xff01;产品选项…...

CSS 3D转换

在 CSS 中&#xff0c;除了可以对页面中的元素进行 2D 转换外&#xff0c;您也可以对象元素进行 3D转换&#xff08;将页面看作是一个三维空间来对页面中的元素进行移动、旋转、缩放和倾斜等操作&#xff09;。与 2D 转换相同&#xff0c;3D 转换同样不会影响周围的元素&#x…...

51单片机数码管循环显示0~f

原理图&#xff1a; #include <reg52.h>sbit dulaP2^6;//段选信号 sbit welaP2^7;//位选信号unsigned char num;//数码管显示的数字0~funsigned char code table[]{ 0x3f,0x06,0x5b,0x4f, 0x66,0x6d,0x7d,0x07, 0x7f,0x6f,0x77,0x7c, 0x39,0x5e,0x79,0x71};//定义数码管显…...

【编程进阶知识】Java NIO:掌握高效的I/O多路复用技术

Java NIO&#xff1a;掌握高效的I/O多路复用技术 摘要&#xff1a; 本文将带你深入了解Java NIO&#xff08;New I/O&#xff09;中的Selector类&#xff0c;探索如何利用它实现高效的I/O多路复用&#xff0c;类似于Linux中的select和epoll系统调用。文章将提供详细的代码示例…...

vscode创建flutter项目,运行flutter项目

打开View&#xff08;查看&#xff09; > Command Palette...&#xff08;命令面板&#xff09;。 可以按下 Ctrl / Cmd Shift P 输入 flutter 选择Flutter: New Project 命令 按下 Enter 。选择Application 选择项目地址 输入项目名称 。按下 Enter 等待项目初始化完成 …...

STM32之CAN外设

相信大家在学习STM32系列的单片机时&#xff0c;在翻阅芯片的数据手册时&#xff0c;都会看到这么一个寄存器外设——CAN外设寄存器。那么&#xff0c;大家知道这个外设的工作原理以及该如何使用吗&#xff1f;这节的内容将会详细介绍STM32上的CAN外设&#xff0c;文章结尾附有…...

【阅读笔记】水果轻微损伤的无损检测技术应用

一、水果轻微损伤检测技术以及应用 无损检测技术顾名思义就是指在不破坏水果样品完整性的情况下对样品进行品质鉴定。目前比较常用的农产品水果类无损检测法有&#xff1a;基于红外热成像、机器视觉技术的图像处理方法、光谱检测技术、介电特性技术检测法等。 1.1 基于红外热…...

忘记7-zip密码,如何解压文件?

7z压缩包设置了密码&#xff0c;解压的时候就需要输入正确对密码才能顺利解压出文件&#xff0c;正常当我们解压文件或者删除密码的时候&#xff0c;虽然方法多&#xff0c;但是都需要输入正确的密码才能完成。忘记密码就无法进行操作。 那么&#xff0c;忘记了7z压缩包的密码…...

SpringBoot基础(一)

1.SpringBoot简介 Spring Boot是Spring社区发布的一个开源项目&#xff0c;旨在帮助开发者快速并且更简单的构建项目。它 使用习惯优于配置的理念让你的项目快速运行起来&#xff0c;使用Spring Boot很容易创建一个独立运行 &#xff08;运行jar&#xff0c;内置Servlet容器&am…...

Java智能匹配灵活用工高效人力资源管理系统小程序源码

智能匹配灵活用工高效人力资源管理系统 &#x1f4bc;&#x1f680; &#x1f680; 开篇&#xff1a;职场新风尚&#xff0c;智能匹配引领变革 在这个瞬息万变的时代&#xff0c;职场也在经历着前所未有的变革。传统的用工模式已难以满足现代企业的需求&#xff0c;而“智能匹…...

openpdf

1、简介 2、示例 2.1 引入依赖 <dependency><groupId>com.github.librepdf</groupId><artifactId>openpdf</artifactId><version>1.3.34</version></dependency><dependency><groupId>com.github.librepdf</…...

C#垃圾回收机制详解

本文详解C#垃圾回收机制。 目录 一、C#垃圾收集器定义 二、C#中的垃圾收集器特点 三、垃圾回收触发条件 四、常见的内存泄漏情况 五、高性能应用程序的垃圾回收策略 六、最佳实践和建议 七、实例 一、C#垃圾收集器定义 int、string变量,这些数据都存储在内存中,如果…...

身份证二要素核验操作指南

身份证二要素核验主要涉及验证身份证上的姓名和身份证号码这两个关键信息&#xff0c;以下是详细的操作指南&#xff1a; 一、核验流程 输入信息&#xff1a;用户在客户端&#xff08;如APP、网站等&#xff09;输入自己的姓名和身份证号码。 信息加密与传输&#xff1a;客户端…...

量子数字签名概述

我们都知道&#xff0c;基于量子力学原理研究密钥生成和使用的学科称为量子密码学。其内容包括了量子密钥分发、量子秘密共享、量子指纹识别、量子比特承诺、量子货币、秘密通信扩展量子密钥、量子安全计算、量子数字签名、量子隐性传态等。虽然各种技术发展的状态不同&#xf…...

算法题——合并 k 个升序的链表

题目描述&#xff1a; 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 数据范围&#xff1a;节点总数 0≤n≤50000≤n≤5000&#xff0c;每个节点的val满足 ∣val∣<1000∣val∣<1000 要求&#xff1a;时间复杂度 O(nlogn) 一、常见解法 &#xff08…...

智能制造与精益制造的模型搭建

现行制造模式分析I-痛点改善思路-管控省优四化推行...

快速生成生产级Go应用的利器——Cgapp

简介 CGAPP是一个强大的命令行工具&#xff0c;开发者通过简单的命令就可以快速搭建起一个完整的Go项目框架。这个框架不仅包括后端服务&#xff0c;还可以集成前端代码和数据库配置&#xff0c;大大简化了项目的初始化过程。 安装 安装CGAPP的过程非常简单。首先&#xff0…...

MySQL基本语法、高级语法知识总结以及常用语法案例

MySQL基本语法总结 MySQL是一种广泛使用的关系型数据库管理系统&#xff0c;其基本语法涵盖了数据库和数据表的创建、查询、修改和删除等操作。 一、数据库操作 创建数据库&#xff08;CREATE DATABASE&#xff09; 语法&#xff1a;CREATE DATABASE [IF NOT EXISTS] databa…...

单片机(学习)2024.10.11

目录 按键 按键原理 按键消抖 1.延时消抖 2.抬手检测 通信 1.通信是什么 2.电平信号和差分信号 3.通信的分类 (1)时钟信号划分 同步通信 异步通信 (2)通信方式划分 串行通信 并行通信 (3)通信方向划分 单工 半双工 全双工 4.USART和UART&#xff08;串口通信&a…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...