ps做网站素材文件打包,一键搭建论坛,重庆渝中区企业网站建设哪家好,小程序免费制作平台官网大家好#xff0c;我是栗筝i#xff0c;这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 014 篇文章#xff0c;在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验#xff0c;并希望进… 大家好我是栗筝i这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 014 篇文章在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验并希望进一步完善自己对整个 Java 技术体系来充实自己的技术栈的同学。与此同时本专栏的所有文章也都会准备充足的代码示例和完善的知识点梳理因此也十分适合零基础的小白和要准备工作面试的同学学习。当然我也会在必要的时候进行相关技术深度的技术解读相信即使是拥有多年 Java 开发经验的从业者和大佬们也会有所收获并找到乐趣。 – Java 集合框架中包含了多种用于数据存储和操作的类其中 LinkedList 是一个重要且常用的实现。LinkedList 作为一个双向链表提供了高效的插入和删除操作特别适用于频繁进行元素增删的场景。对于很多开发者而言深入理解 LinkedList 的特性和工作原理是提高代码性能和优化数据处理逻辑的关键。本文将对 LinkedList 进行全面的介绍和解析帮助读者掌握其使用方法、内部原理以及源码实现。 文章目录 1、LinkedList 概述2、LinkedList 的具体实现原理2.1、LinkedList 底层的数据结构2.2、LinkedList 增删改查的实现2.2.1、LinkedList 的插入2.2.2、LinkedList 的删除2.2.3、LinkedList 的修改2.2.4、LinkedList 的查询 2.3、LinkedList 对链表结构的实现 3、LinkedList 相关知识点3.1、关于 Queue 队列3.2、关于 ArrayList 和 LinkedList 的区别3.3、算法翻转链表 4、LinkedList 的使用常用方法4.1、LinkedList 的常用方法4.2、继承自 Queue 接口的方法4.3、Collections 类中涉及 LinkedList 的常用方法 1、LinkedList 概述
LinkedList 是 List 接口的一个实现它是一个双向链表。与 ArrayList 相比LinkedList 的元素在内存中不是连续存放的。每个元素称为节点都包含两部分数据一部分是存储的数据另一部分是指向前一个节点和后一个节点的链接指针。
LinkedList 的优点在于插入和删除元素时效率很高。因为链表的数据结构使得它只需要修改前后节点的指针即可而不需要像 ArrayList 那样移动其他元素。因此LinkedList 适合用在需要频繁执行添加和删除操作的场景。
然而LinkedList 的随机访问效率不高每次查找某个元素都需要从头开始遍历链表直到找到目标元素。这使得 LinkedList 在执行随机访问操作时速度较慢不如 ArrayList。
在 Java 中LinkedList 除了实现 List 接口外还实现了 Deque 接口这意味着它还可以被当作队列Queue、双端队列Deque使用提供了更加丰富的方法如 addFirst(), addLast(), removeFirst(), removeLast() 等。
LinkedList 也是非线程安全的。如果在多线程环境中使用需要外部同步或者考虑使用 java.util.concurrent 包中的线程安全类如 LinkedBlockingDeque 等。
总的来说LinkedList 由于其结构的特点适合于数据量不大但插入和删除操作频繁的场景而不适合大量的随机访问操作。 2、LinkedList 的具体实现原理
2.1、LinkedList 底层的数据结构
LinkedList 是基于链表数据结构实现的它包含一系列的节点Node每个节点包括三个部分前一个节点的引用previous储存的元素data和下一个节点的引用next。这种数据结构支持高效的元素插入和删除操作。
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{transient int size 0;// 链表中元素的数量transient int size 0;/*** 指向第一个节点的指针*/transient NodeE first;/*** 指向最后一个节点的指针*/transient NodeE last;/*** 构造一个空的链表*/public LinkedList() {}/*** 构造一个包含指定集合元素的链表这些元素按集合的迭代器返回的顺序排列。** param c 要放入链表中的集合* throws NullPointerException 如果指定的集合为 null*/public LinkedList(Collection? extends E c) {this();// 将集合中的所有元素添加到链表中addAll(c);}// 省略其他方法和实现细节.../*** Node 是一个私有的静态内部类用于表示 LinkedList 中的每个节点** param E*/private static class NodeE {// 节点存储的元素E item;// 指向下一个节点的引用NodeE next;// 指向前一个节点的引用NodeE prev;/*** 构造方法创建一个新的节点** param prev 该节点的前一个节点* param element 该节点存储的元素* param next 该节点的后一个节点*/Node(NodeE prev, E element, NodeE next) {// 设置节点存储的元素this.item element;// 设置指向下一个节点的引用this.next next;// 设置指向前一个节点的引用this.prev prev;}}// 省略其他方法和实现细节...
}2.2、LinkedList 增删改查的实现
2.2.1、LinkedList 的插入
LinkedList 的插入的实现并不复杂其插入式主要会有两种场景一种是在链表的末尾插入另一种是在指定节点之前插入一个新节点二者的实现都是通过创建一个新节点并更新其前驱和后继节点的引用唯一的区别就是linkBefore 是在指定节点之后插入该新节点而 linkAfter 是在指定节点之后插入该新节点。
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{// 省略其他方法和实现细节.../*** 在链表末尾添加一个元素** param e 要添加的元素* return 总是返回 true*/Overridepublic boolean add(E e) {// 在链表末尾链接一个新的节点linkLast(e);return true;}/*** 在链表末尾链接一个新的节点** param e 新节点存储的元素*/void linkLast(E e) {// 保存当前链表的最后一个节点final NodeE l last;// 创建一个新的节点前驱节点是当前最后一个节点后继节点是 nullfinal NodeE newNode new Node(l, e, null);// 将链表的最后一个节点更新为新节点last newNode;if (l null)// 如果链表之前是空的即没有任何元素// 将新节点设置为链表的第一个节点first newNode;else// 如果链表中已有元素// 将原最后一个节点的 next 指针指向新节点l.next newNode;// 链表大小增加 1size; }/*** 在指定索引处插入元素** param index 要插入元素的位置* param element 要插入的元素*/public void add(int index, E element) {checkPositionIndex(index);if (index size)linkLast(element);elselinkBefore(element, node(index));}/*** 在指定节点之前插入一个新节点** param e 新节点存储的元素* param succ 指定的节点新节点将插入在其之前*/void linkBefore(E e, NodeE succ) {// assert succ ! null; // 确保 succ 不为 null确保在调用该方法前 succ 一定存在// 保存指定节点的前驱节点final NodeE pred succ.prev;// 创建一个新的节点其前驱是 pred后继是 succfinal NodeE newNode new Node(pred, e, succ);// 将指定节点的前驱更新为新节点succ.prev newNode;if (pred null)// 如果 pred 为 null说明 succ 是第一个节点// 将新节点设置为链表的第一个节点first newNode;else// 如果 pred 不为 null说明 succ 不是第一个节点// 将 pred 的后继节点更新为新节点pred.next newNode;// 链表大小增加 1size;// 修改计数器增加 1用于快速失败机制modCount; }// 省略其他方法和实现细节...
}此外另一个十分值得注意的点是add(int index, E element) 在调用指定节点之前插入一个新节点方法时调用了 node(int index) 方法来返回指定索引处的节点。该方法可以看作是 LinkedList 的核心实现之一除插入方法之外LinkedList 在查询、删除、修改等方法除也需要调用当前方法
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{// 省略其他方法和实现细节.../*** 返回指定索引处的节点。** param index 要获取节点的位置* return 指定索引处的节点*/NodeE node(int index) {// assert isElementIndex(index); // 确保索引在有效范围内// 判断索引是否在链表的前半部分if (index (size 1)) {// 从链表的第一个节点开始遍历NodeE x first;// 遍历到指定索引位置for (int i 0; i index; i)// 依次移动到下一个节点x x.next;// 返回找到的节点return x;} else {// 索引在链表的后半部分NodeE x last;// 从链表的最后一个节点开始遍历for (int i size - 1; i index; i--)// 依次移动到前一个节点x x.prev;// 返回找到的节点return x;}}// 省略其他方法和实现细节...
}2.2.2、LinkedList 的删除
LinkedList 的删除的实现同样十分简单是使用 unlink 方法即通过更新前驱和后继节点的引用移除指定节点并返回其存储的元素实现的。
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{// 省略其他方法和实现细节.../*** 解除并移除指定节点。** param x 要移除的节点* return 被移除节点存储的元素*/E unlink(NodeE x) {// assert x ! null; // 确保 x 不为 null// 保存节点中的元素final E element x.item;// 保存节点的后继节点final NodeE next x.next;// 保存节点的前驱节点final NodeE prev x.prev;if (prev null) {// 如果前驱节点为 null说明 x 是第一个节点// 将链表的第一个节点更新为 x 的后继节点first next;} else {// 如果前驱节点不为 null// 将前驱节点的后继更新为 x 的后继节点prev.next next;// 将 x 的前驱设为 null帮助垃圾回收x.prev null;}if (next null) {// 如果后继节点为 null说明 x 是最后一个节点// 将链表的最后一个节点更新为 x 的前驱节点last prev;} else {// 如果后继节点不为 null// 将后继节点的前驱更新为 x 的前驱节点next.prev prev;// 将 x 的后继设为 null帮助垃圾回收x.next null;}// 将 x 中的元素设为 null帮助垃圾回收x.item null;// 链表大小减 1size--;// 修改计数器增加 1用于快速失败机制modCount;// 返回被移除节点中的元素return element;}/*** 移除指定索引处的元素。** param index 要移除元素的位置* return 被移除的元素*/public E remove(int index) {checkElementIndex(index);return unlink(node(index));}/*** 从链表中移除第一次出现的指定元素如果存在。* 如果列表不包含该元素则不做改变。** param o 要移除的元素* return 如果列表包含指定元素并移除成功则返回 true否则返回 false*/public boolean remove(Object o) {// 如果要移除的元素为 nullif (o null) { for (NodeE x first; x ! null; x x.next) {// 从链表的第一个节点开始遍历if (x.item null) {// 如果当前节点的元素为 nullunlink(x); // 解除并移除当前节点// 返回 true表示移除成功return true; }}} else { // 如果要移除的元素不为 nullfor (NodeE x first; x ! null; x x.next) { // 从链表的第一个节点开始遍历// 如果当前节点的元素等于要移除的元素if (o.equals(x.item)) {// 解除并移除当前节点unlink(x);// 返回 true表示移除成功return true; }}}// 如果没有找到要移除的元素返回 falsereturn false; }// 省略其他方法和实现细节...
}2.2.3、LinkedList 的修改
LinkedList 对于修改的则是通过找到原位置的 Node 并修改其 item 值实现的。
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{// 省略其他方法和实现细节.../*** 替换指定索引处的元素并返回被替换的元素。** param index 要替换元素的位置* param element 要设置的新元素* return 被替换的旧元素* throws IndexOutOfBoundsException 如果索引超出范围*/public E set(int index, E element) {// 检查索引是否在范围内checkElementIndex(index);// 获取指定索引处的节点NodeE x node(index);// 保存当前节点的旧元素E oldVal x.item;// 将节点的元素设置为新元素x.item element;// 返回被替换的旧元素return oldVal;}/*** 将迭代器返回的最后一个元素替换为指定的元素。** param e 要设置的新元素* throws IllegalStateException 如果没有调用 next() 或 previous() 方法*/public void set(E e) {if (lastReturned null)// 如果 lastReturned 为 null表示未调用 next() 或 previous()// 抛出非法状态异常throw new IllegalStateException();// 检查是否发生并发修改checkForComodification();// 将 lastReturned 节点的元素设置为新元素 elastReturned.item e;}// 省略其他方法和实现细节...
}2.2.4、LinkedList 的查询
LinkedList 的查询即获取指定索引处的元素。它的实现同前面的其他方法获取索引处元素一样依赖 node(int index) 方法。
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{// 省略其他方法和实现细节.../*** 获取指定索引处的元素** param index 要获取元素的位置* return 指定索引处的元素*/public E get(int index) {checkElementIndex(index);return node(index).item;}/*** 返回指定索引处的节点。** param index 要获取节点的位置* return 指定索引处的节点*/NodeE node(int index) {// assert isElementIndex(index); // 确保索引在有效范围内// 判断索引是否在链表的前半部分if (index (size 1)) {// 从链表的第一个节点开始遍历NodeE x first;// 遍历到指定索引位置for (int i 0; i index; i)// 依次移动到下一个节点x x.next;// 返回找到的节点return x;} else {// 索引在链表的后半部分NodeE x last;// 从链表的最后一个节点开始遍历for (int i size - 1; i index; i--)// 依次移动到前一个节点x x.prev;// 返回找到的节点return x;}}// 省略其他方法和实现细节...
}2.3、LinkedList 对链表结构的实现
LinkedList 类实现了 Queue 接口因此提供了队列相关的方法。这些方法允许 LinkedList 作为一个双端队列Deque使用支持在队列的头部和尾部进行插入和删除操作。下面是对 LinkedList 中与 Queue 相关方法的概括说明
offer(E e)将指定的元素添加到队列的尾部并返回 true。实现调用 linkLast(E e) 方法将元素添加到链表的尾部poll()获取并移除此队列的头部如果队列为空则返回 null。实现调用 unlinkFirst(NodeE f) 方法移除并返回链表的第一个元素remove()获取并移除此队列的头部如果队列为空则抛出 NoSuchElementException。实现调用 unlinkFirst(NodeE f) 方法移除并返回链表的第一个元素。如果链表为空抛出 NoSuchElementExceptionpeek()获取但不移除此队列的头部如果队列为空则返回 null。实现返回链表的第一个元素 first.item如果链表为空返回 null。element()获取但不移除此队列的头部如果队列为空则抛出 NoSuchElementException。实现返回链表的第一个元素 first.item如果链表为空抛出 NoSuchElementException。
具体实现
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{// 省略其他方法和实现细节.../*** 将指定的元素添加到队列的尾部。** param e 要添加的元素* return 添加成功返回 true*/public boolean offer(E e) {// 调用 add 方法将元素添加到链表的尾部return add(e);}/*** 获取并移除此队列的头部如果队列为空则返回 null。** return 队列头部的元素如果队列为空则返回 null*/public E poll() {// 保存链表的第一个节点final NodeE f first;// 如果链表为空返回 null否则移除并返回第一个元素return (f null) ? null : unlinkFirst(f);}/*** 获取并移除此队列的头部如果队列为空则抛出 NoSuchElementException。** return 队列头部的元素* throws NoSuchElementException 如果队列为空*/public E remove() {// 保存链表的第一个节点final NodeE f first;// 如果链表为空抛出 NoSuchElementExceptionif (f null)throw new NoSuchElementException();// 移除并返回第一个元素return unlinkFirst(f);}/*** 获取但不移除此队列的头部如果队列为空则返回 null。** return 队列头部的元素如果队列为空则返回 null*/public E peek() {// 保存链表的第一个节点final NodeE f first;// 返回第一个元素但不移除如果链表为空返回 nullreturn (f null) ? null : f.item;}/*** 获取但不移除此队列的头部如果队列为空则抛出 NoSuchElementException。** return 队列头部的元素* throws NoSuchElementException 如果队列为空*/public E element() {return getFirst();}/*** 返回链表的第一个元素如果链表为空则抛出 NoSuchElementException。** return 链表的第一个元素* throws NoSuchElementException 如果链表为空*/public E getFirst() {// 保存链表的第一个节点final NodeE f first;// 如果链表为空抛出 NoSuchElementExceptionif (f null)throw new NoSuchElementException();// 返回第一个元素return f.item;}// 省略其他方法和实现细节...
}内部辅助方法unlinkFirst(NodeE f)移除并返回链表的第一个节点。实现更新链表的头节点 first 为当前头节点 f 的下一个节点 f.next并将旧头节点的前驱引用设为 null。
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{// 省略其他方法和实现细节.../*** 移除并返回链表的第一个节点。** param f 要移除的第一个节点* return 被移除节点存储的元素*/private E unlinkFirst(NodeE f) {// 保存第一个节点的元素final E element f.item;// 保存第一个节点的后继节点final NodeE next f.next;// 清空第一个节点的元素f.item null;// 清空第一个节点的后继引用帮助垃圾回收f.next null;// 更新链表的头节点为原头节点的后继节点first next;// 如果新的头节点为 null说明链表现在为空if (next null) {// 更新链表的尾节点为 nulllast null;} else {// 将新的头节点的前驱引用设为 nullnext.prev null;}// 链表大小减 1size--;// 修改计数器增加 1用于快速失败机制modCount;// 返回被移除的元素return element;}// 省略其他方法和实现细节...
}3、LinkedList 相关知识点
3.1、关于 Queue 队列
队列Queue也是一种操作受限的线性表只允许在表的一端进行插入而在表的另一端进行删除。向队列中插入元素称为入队或进队删除元素称为出队或离队。 这和我们日常生活中的排队是一致的最早排队的也是最早离队的。其操作的特性是先进先出First In First Out, FIFO故又称为先进先出的线性表。基本上一个队列就是一个先入先出FIFO的数据结构
在Java 中 Queue 接口与 List、Set 同一级别都是继承了 Collection 接口。LinkedList 实现了 Deque 接口。
3.2、关于 ArrayList 和 LinkedList 的区别
ArrayList 和 LinkedList 都是 List 接口的实现但它们在内部数据结构和性能上有一些区别
内部数据结构ArrayList 是基于动态数组实现的支持随机访问按索引访问元素非常快时间复杂度为 O(1)。LinkedList 是基于双向链表实现的不支持高效的随机访问按索引访问元素需要从头或尾开始遍历时间复杂度为 O(n)。插入和删除ArrayList 的插入和删除操作需要进行数组元素的移动除非插入和删除操作在列表末尾进行所以插入和删除元素的时间复杂度为 O(n)。LinkedList 的插入和删除操作只需要改变节点的引用所以在列表中间插入和删除元素的时间复杂度为 O(1)前提是已经获取到了要插入位置的节点。内存占用ArrayList 的内存占用相对较低因为它只需要存储元素数据和数组的引用。LinkedList 的内存占用较高因为它需要额外存储节点之间的引用。
总的来说ArrayList 更适合随机访问场景LinkedList 更适合插入和删除操作频繁的场景。
3.3、算法翻转链表
假设链表为 1→2→3→∅我们想要把它改成 ∅←1←2←3。
在遍历链表时将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点因此必须事先存储其前一个节点。在更改引用之前还需要存储后一个节点。最后返回新的头引用。
class Solution {/*** 反转链表。** param head 链表的头节点* return 反转后的链表的头节点*/public ListNode reverseList(ListNode head) {// 初始化前一个节点为 nullListNode prev null;// 初始化当前节点为头节点ListNode curr head;// 遍历链表直到当前节点为 nullwhile (curr ! null) {// 保存当前节点的下一个节点ListNode next curr.next;// 将当前节点的下一个节点指向前一个节点完成反转curr.next prev;// 将前一个节点更新为当前节点prev curr;// 将当前节点更新为下一个节点curr next;}// 返回反转后的链表头节点return prev;}
}4、LinkedList 的使用常用方法
下面是对 LinkedList 的常用方法和 Collections 类中的一些涉及 LinkedList 的方法进行详细介绍
4.1、LinkedList 的常用方法
add(E e)
功能将元素添加到链表的末尾。用例
LinkedListString list new LinkedList();
list.add(Apple);add(int index, E element)
功能在指定位置插入元素。用例
LinkedListString list new LinkedList();
list.add(Apple);
list.add(Banana);
list.add(1, Orange); // 将 Orange 插入在 Banana 前面remove(Object o)
功能删除链表中首次出现的指定元素。用例
LinkedListString list new LinkedList();
list.add(Apple);
list.add(Banana);
list.remove(Apple);remove(int index)
功能删除指定索引处的元素。用例
LinkedListString list new LinkedList();
list.add(Apple);
list.add(Banana);
list.remove(0); // 删除 Appleget(int index)
功能返回链表中指定位置的元素。用例
LinkedListString list new LinkedList();
list.add(Apple);
String item list.get(0); // 获取第一个元素 Appleset(int index, E element)
功能替换指定位置的元素并返回旧值。用例
LinkedListString list new LinkedList();
list.add(Apple);
String oldItem list.set(0, Orange); // 将 Apple 替换为 Orangesize()
功能返回链表中的元素数量。用例
LinkedListString list new LinkedList();
list.add(Apple);
int size list.size(); // size 为 1isEmpty()
功能检查链表是否为空。用例
LinkedListString list new LinkedList();
boolean empty list.isEmpty(); // 判断链表是否为空clear()
功能清空链表中的所有元素。用例
LinkedListString list new LinkedList();
list.add(Apple);
list.clear(); // 清空链表contains(Object o)
功能检查链表是否包含指定的元素。用例
LinkedListString list new LinkedList();
list.add(Apple);
boolean contains list.contains(Apple); // 检查是否包含 AppleindexOf(Object o) 和 lastIndexOf(Object o)
功能返回指定元素首次出现和最后一次出现的索引位置。用例
LinkedListString list new LinkedList();
list.add(Apple);
list.add(Banana);
list.add(Apple);
int firstIndex list.indexOf(Apple); // 返回 0
int lastIndex list.lastIndexOf(Apple); // 返回 2toArray()
功能将链表中的元素转换为数组。用例
LinkedListString list new LinkedList();
list.add(Apple);
Object[] array list.toArray(); // 转换为数组addAll(Collection? extends E c)
功能将指定集合中的所有元素添加到链表的尾部。用例
LinkedListInteger list new LinkedList();
LinkedListInteger newElements new LinkedList(Arrays.asList(1, 2, 3));
list.addAll(newElements); // 添加多个元素addAll(int index, Collection? extends E c)
功能将指定集合中的所有元素添加到链表中的指定位置。用例
LinkedListString list new LinkedList(Arrays.asList(a, b, c));
LinkedListString newElements new LinkedList(Arrays.asList(x, y));
list.addAll(1, newElements); // 在索引1的位置添加多个元素removeAll(Collection? c)
功能从链表中移除指定集合中也存在的所有元素。用例
LinkedListString list new LinkedList(Arrays.asList(a, b, c, b));
list.removeAll(Collections.singleton(b)); // 移除所有 bretainAll(Collection? c)
功能仅保留链表中那些也包含在指定集合中的元素。用例
LinkedListString list new LinkedList(Arrays.asList(a, b, c));
list.retainAll(Arrays.asList(a, b)); // 保留 a 和 bcontainsAll(Collection? c)
功能如果链表包含指定集合中的所有元素则返回 true。用例
LinkedListString list new LinkedList(Arrays.asList(a, b, c));
boolean contains list.containsAll(Arrays.asList(a, b)); // 检查是否包含 a 和 b4.2、继承自 Queue 接口的方法
offer(E e)
功能将指定的元素添加到队列的尾部。用例
LinkedListString queue new LinkedList();
queue.offer(Apple);poll()
功能获取并移除队列的头部元素如果队列为空则返回 null。用例
LinkedListString queue new LinkedList();
queue.offer(Apple);
String item queue.poll(); // 获取并移除 Appleremove()
功能获取并移除队列的头部元素如果队列为空则抛出 NoSuchElementException。用例
LinkedListString queue new LinkedList();
queue.offer(Apple);
String item queue.remove(); // 获取并移除 Applepeek()
功能获取但不移除队列的头部元素如果队列为空则返回 null。用例
LinkedListString queue new LinkedList();
queue.offer(Apple);
String item queue.peek(); // 获取但不移除 Appleelement()
功能获取但不移除队列的头部元素如果队列为空则抛出 NoSuchElementException。用例
LinkedListString queue new LinkedList();
queue.offer(Apple);
String item queue.element(); // 获取但不移除 Apple4.3、Collections 类中涉及 LinkedList 的常用方法
sort(ListT list)
功能对链表进行排序自然顺序。用例
LinkedListInteger list new LinkedList(Arrays.asList(3, 1, 4, 1, 5));
Collections.sort(list); // 对链表排序reverse(List? list)
功能反转链表中元素的顺序。用例
LinkedListInteger list new LinkedList(Arrays.asList(1, 2, 3));
Collections.reverse(list); // 链表变为 [3, 2, 1]shuffle(List? list)
功能随机打乱链表中元素的顺序。用例
LinkedListInteger list new LinkedList(Arrays.asList(1, 2, 3));
Collections.shuffle(list); // 打乱链表元素的顺序binarySearch(List? extends Comparable? super T list, T key)
功能在已排序的链表中使用二分查找法查找指定元素的索引。用例
LinkedListInteger list new LinkedList(Arrays.asList(1, 2, 3, 4, 5));
Collections.sort(list);
int index Collections.binarySearch(list, 3); // 在链表中查找数字 3 的索引copy(List? super T dest, List? extends T src)
功能将一个链表中的所有元素复制到另一个链表中。用例
LinkedListInteger src new LinkedList(Arrays.asList(1, 2, 3));
LinkedListInteger dest new LinkedList(Arrays.asList(5, 6, 7, 8));
Collections.copy(dest, src); // 将 src 复制到 destfill(List? super T list, T obj)
功能使用指定元素替换链表中的所有元素。用例
LinkedListInteger list new LinkedList(Arrays.asList(1, 2, 3));
Collections.fill(list, 0); // 将链表中的所有元素替换为 0addAll(Collection? super T c, T... elements)
功能向集合中添加多个元素。用例
LinkedListInteger list new LinkedList();
Collections.addAll(list, 1, 2, 3, 4); // 向链表中添加多个元素replaceAll(ListT list, T oldVal, T newVal)
功能替换链表中所有的旧值为新值。用例
LinkedListInteger list new LinkedList(Arrays.asList(1, 2, 1, 3));
Collections.replaceAll(list, 1, 99); // 将所有1替换为99frequency(Collection? c, Object o)
功能返回指定元素在集合中出现的次数。用例
LinkedListInteger list new LinkedList(Arrays.asList(1, 2, 1, 3));
int freq Collections.frequency(list, 1); // 计算1在链表中出现的次数disjoint(Collection? c1, Collection? c2)
功能如果两个集合没有共同的元素则返回 true。用例
LinkedListInteger list1 new LinkedList(Arrays.asList(1, 2, 3));
LinkedListInteger list2 new LinkedList(Arrays.asList(4, 5, 6));
boolean isDisjoint Collections.disjoint(list1, list2); // 检查两个链表是否没有共同元素通过以上方法可以对 LinkedList 进行各种常用操作如添加、删除、获取元素等以及使用 Collections 类中的方法对 LinkedList 进行排序、反转、打乱顺序等批量操作。特别是继承自 Queue 接口的方法可以使 LinkedList 作为队列使用提供了队列相关的操作。
