31. LinkedList 解码，双向链表解析

大家好，欢迎来到IT知识分享网。

哈喽 大家好，我是老陈!

这节课拆解 Java 中的LinkedList，它就像一列 “灵活拼接的火车”—— 每个元素都是一个 “车厢”，通过前后指针连接。相比 ArrayList 的动态数组结构，LinkedList 在频繁插入删除场景下更高效！全程干货，带你从原理到实战！

31.1 LinkedList vs ArrayList

ArrayList 是 “连续排列的书架”，随机取书快但插入麻烦；LinkedList 是 “火车车厢”，添加删除车厢（元素）灵活，但找指定位置的车厢需要从头遍历。

LinkedList两个常用方法：

add(E element)：把元素添加到链表的尾部。

add(int index, E element)：在链表的指定索引位置插入元素。

代码示例如下：

package com.linkedlist.demo; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; / * @author 今日头条：老陈说编程 * 对比ArrayList和LinkedList的基本特性及性能差异 * 1. ArrayList基于动态数组实现，支持随机访问，适合读多写少的场景 * 2. LinkedList基于双向链表实现，适合频繁插入/删除的场景 */ public class LinkedListVsArrayList { public static void main(String[] args) { // 创建ArrayList和LinkedList实例 List<Integer> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>(); // 测试尾部添加元素性能（两者效率相近） // ArrayList: 动态数组在容量不足时需扩容（约为O(n)），但平均为O(1) // LinkedList: 双向链表直接在尾部添加节点，时间复杂度O(1) long start = System.currentTimeMillis(); for (int i = 0; i < ; i++) { arrayList.add(i); } System.out.println("ArrayList尾部添加耗时：" + (System.currentTimeMillis() - start) + "ms"); start = System.currentTimeMillis(); for (int i = 0; i < ; i++) { linkedList.add(i); } System.out.println("LinkedList尾部添加耗时：" + (System.currentTimeMillis() - start) + "ms"); // 测试中间插入元素性能（LinkedList更高效） // ArrayList: 在中间插入需移动后续所有元素，时间复杂度O(n) // LinkedList: 仅需修改前后节点的指针，时间复杂度O(1) start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { arrayList.add(5000, i); // 插入到中间位置，触发大量元素移动 } System.out.println("ArrayList中间插入耗时：" + (System.currentTimeMillis() - start) + "ms"); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { linkedList.add(5000, i); // 链表仅修改指针，无需移动元素 } System.out.println("LinkedList中间插入耗时：" + (System.currentTimeMillis() - start) + "ms"); // 补充：测试随机访问性能（ArrayList更高效） // ArrayList: 支持O(1)随机访问，直接通过索引定位元素 // LinkedList: 需从头/尾遍历链表，时间复杂度O(n) start = System.currentTimeMillis(); for (int i = 0; i < ; i++) { arrayList.get(i); } System.out.println("ArrayList随机访问耗时：" + (System.currentTimeMillis() - start) + "ms"); start = System.currentTimeMillis(); for (int i = 0; i < ; i++) { linkedList.get(i); // 链表需遍历，性能较差 } System.out.println("LinkedList随机访问耗时：" + (System.currentTimeMillis() - start) + "ms"); } } 

31.2增删改查：链表特有的操作

LinkedList 除了实现 List 接口的常规方法，还提供了队列（Queue）和栈（Stack）相关的方法！

1. 添加元素

add() ：是 List 接口方法，向尾部添加元素，失败时抛异常；

offer() ：属于 Queue 接口，功能和 add 一致，但失败返回 false；

offerFirst() 和 offerLast() 是 Deque 特有的头尾添加方法。

2. 获取元素

get(0) ： 按索引获取，但链表需要遍历；

peek() 和 peekFirst() 从头部获取元素且不删除，空列表返回 null；

peekLast() ：可以直接获取尾部元素。

这里所有方法都不会修改原列表，适合仅查看数据的场景。

3. 修改元素

set(index, value) ：直接替换指定位置的元素。

4. 删除元素

remove(index) ：按索引删除，需要遍历链表；

remove(Object) ：按值删除第一个匹配项；

poll() 和 pollFirst() 从头部删除并返回元素，空列表返回 null。

5. 作为栈使用

push() ：向栈顶（头部）添加元素

pop() ：弹出栈顶元素

这种后进先出的特性，适合表达式求值、撤销操作等场景。

6. 作为队列使用

offer() ：从队尾添加元素

poll() ：从队头删除元素

这种结构适合任务调度、广度优先搜索等场景。

7. 其他常用方法

contains()： 判断元素是否存在；

size() ：获取元素数量；

clear() ：清空列表，isEmpty () 返回 true。

这些方法在集合操作中非常常用。

代码示例如下：

package com.linkedlist.demo; import java.util.LinkedList; / * @author 今日头条：老陈说编程 * LinkedList的基本操作及特有方法（队列/栈功能） * <p> * LinkedList实现了List和Deque接口，兼具链表和双端队列的特性： * - 元素有序且可重复 * - 允许null元素 * - 非线程安全 * - 插入/删除效率高(O(1))，随机访问效率低(O(n)) */ public class LinkedListBasicOps { public static void main(String[] args) { // 1. 创建LinkedList // 可以作为List、Queue、Deque使用，根据需要选择接口类型 LinkedList<String> names = new LinkedList<>(); System.out.println("1. 创建LinkedList后：" + names); // 2. 添加元素：add()与offer() names.add("张三"); // List接口方法，尾部添加，失败时抛出异常 System.out.println("add(\"张三\")后：" + names); names.offer("李四"); // Queue接口方法，尾部添加，失败时返回false（等效于add） System.out.println("offer(\"李四\")后：" + names); names.offerFirst("王二"); // Deque接口方法：头部添加（链表特有） System.out.println("offerFirst(\"王二\")后：" + names); names.offerLast("王五"); // Deque接口方法：尾部添加（链表特有） System.out.println("offerLast(\"王五\")后：" + names); System.out.println("2. 添加后列表：" + names + "\n"); // [王二, 张三, 李四, 王五] // 3. 获取元素：get()与peek() String first = names.get(0); // List接口：按索引获取（O(n)，需遍历链表） System.out.println("get(0)获取的元素：" + first); String firstElement = names.peek(); // Queue接口：获取头部元素，不删除，空列表返回null System.out.println("peek()获取的元素：" + firstElement); String firstElement2 = names.peekFirst(); // Deque接口：等效于peek() System.out.println("peekFirst()获取的元素：" + firstElement2); String lastElement = names.peekLast(); // Deque接口：获取尾部元素 System.out.println("peekLast()获取的元素：" + lastElement); System.out.println("3. 头部元素（不删除）：" + first + ", " + firstElement + ", " + firstElement2 + "\n"); // 4. 修改元素 names.set(1, "张三改"); // List接口方法，替换指定位置元素 System.out.println("4. 修改后列表：" + names + "\n"); // [王二, 张三改, 李四, 王五] // 5. 删除元素：remove()与poll() System.out.println("删除前列表：" + names); names.remove(0); // List接口：按索引删除，需遍历链表 System.out.println("remove(0)后列表：" + names); names.remove("李四"); // 按值删除（删除第一个匹配项） System.out.println("remove(\"李四\")后列表：" + names); String polled = names.poll(); // Queue接口：获取并删除头部元素，空列表返回null System.out.println("poll()删除的元素：" + polled); String polledFirst = names.pollFirst(); // Deque接口：等效于poll() System.out.println("pollFirst()删除的元素：" + polledFirst); System.out.println("5. 删除后列表：" + names); // [王五] System.out.println("5. 删除的元素：" + polled + ", " + polledFirst + "\n"); // 6. 作为栈使用（LIFO） // LinkedList可直接作为栈使用，无需使用已过时的Stack类 LinkedList<Integer> stack = new LinkedList<>(); System.out.println("6. 栈操作："); System.out.println("空栈：" + stack); stack.push(1); // Deque接口：入栈（添加到头部） System.out.println("push(1)后栈：" + stack); stack.push(2); System.out.println("push(2)后栈：" + stack); System.out.println("6. 栈：" + stack); // [2, 1] int popped = stack.pop(); // Deque接口：出栈（获取并删除头部元素） System.out.println("pop()出栈元素：" + popped); System.out.println("6. 出栈元素：" + popped + "，剩余栈：" + stack + "\n"); // 2, [1] // 7. 作为队列使用（FIFO） LinkedList<Integer> queue = new LinkedList<>(); System.out.println("7. 队列操作："); System.out.println("空队列：" + queue); queue.offer(10); // 入队（尾部添加） System.out.println("offer(10)后队列：" + queue); queue.offer(20); System.out.println("offer(20)后队列：" + queue); int head = queue.poll(); // 出队（头部删除） System.out.println("poll()出队元素：" + head); System.out.println("7. 队列：" + queue + "\n"); // [20] // 8. 其他常用方法 System.out.println("8. 其他常用方法："); // 重新添加元素以便演示其他方法 names.add("王五"); System.out.println("重新添加元素后列表：" + names); boolean hasElement = names.contains("王五"); // 判断元素是否存在 System.out.println("列表是否包含\"王五\"：" + hasElement); int size = names.size(); // 获取元素数量 System.out.println("列表大小：" + size); names.clear(); // 清空列表 System.out.println("clear()后列表：" + names); System.out.println("8. 列表是否为空：" + names.isEmpty()); // true } }

31.3 遍历方式：迭代器更高效

LinkedList 不推荐用普通 for 循环按索引遍历，推荐用迭代器或增强 for 循环。若需在遍历中删除元素，必须用迭代器的remove()方法！

add(E e)：将指定元素添加到列表末尾。

iterator()：返回列表的迭代器，用于顺序遍历元素。

size()：返回列表中的元素个数。

get(int index)：获取指定索引位置的元素（不推荐频繁用于 LinkedList，效率低）。

descendingIterator()：返回列表的反向迭代器（从尾部向前遍历）。

迭代器的 hasNext()：判断迭代器是否还有下一个元素。

迭代器的 next()：返回迭代器的下一个元素。

迭代器的 remove()：安全删除迭代器最后返回的元素。

代码示例如下：

package com.linkedlist.demo; import java.util.Iterator; import java.util.LinkedList; import java.util.List; / * @author 今日头条：老陈说编程 * LinkedList的遍历方式及安全删除 * 演示了四种遍历LinkedList的方法，并展示了如何安全地删除元素 */ public class LinkedListTraversal { public static void main(String[] args) { // 创建LinkedList实例并添加元素 List<String> list = new LinkedList<>(); list.add("元素1"); // 添加元素到列表末尾 list.add("删除项"); // 添加元素到列表末尾 list.add("元素2"); // 添加元素到列表末尾 list.add("删除项"); // 添加元素到列表末尾 list.add("元素3"); // 添加元素到列表末尾 // 1. 增强for循环（简洁，但遍历时不能删除，否则会抛出ConcurrentModificationException） System.out.println("增强for循环遍历："); for (String item : list) { System.out.println(item); // 打印当前元素 } // 2. 迭代器遍历（推荐，可安全删除元素） System.out.println("\n迭代器遍历并删除："); Iterator<String> it = list.iterator(); // 获取列表的迭代器 while (it.hasNext()) { // 判断是否有下一个元素 String item = it.next(); // 获取下一个元素 if (item.equals("删除项")) { it.remove(); // 安全删除当前元素，避免ConcurrentModificationException } } // 3. 普通for循环（不推荐，随机访问效率低，因为LinkedList的get(i)是O(n)操作） System.out.println("\n普通for循环（不推荐）："); for (int i = 0; i < list.size(); i++) { // size()方法返回列表的元素个数 System.out.println(list.get(i)); // 获取指定索引位置的元素 } // 4. 链表特有：双向迭代器（Deque接口特性，可从尾部向前遍历） System.out.println("\n双向迭代器（从尾部遍历）："); Iterator<String> descendingIt = ((LinkedList<String>) list).descendingIterator(); // 获取反向迭代器 while (descendingIt.hasNext()) { // 判断是否有下一个元素（反向顺序） System.out.println(descendingIt.next()); // 获取下一个元素（反向顺序） } } } 

31.4 作为双端队列（Deque）的高级用法

LinkedList 实现了Deque接口，可作为双端队列使用，支持从头部和尾部双向操作，像 “双向通车的隧道”！

offerFirst(E e)：将元素添加到双端队列的头部。

offerLast(E e)：将元素添加到双端队列的尾部。

peekFirst()：获取双端队列的头部元素，但不删除。若队列为空则返回null。

peekLast()：获取双端队列的尾部元素，但不删除。若队列为空则返回null。

pollFirst()：获取并删除双端队列的头部元素。若队列为空则返回null。

pollLast()：获取并删除双端队列的尾部元素。若队列为空则返回null。

push(E e)：将元素压入栈顶（等价于offerFirst）。

pop()：弹出栈顶元素（等价于pollFirst）。若栈为空则抛出异常。

offer(E e)：将元素添加到队列尾部（等价于offerLast）。

poll()：获取并删除队列头部元素（等价于pollFirst）。

代码示例如下：

package com.linkedlist.demo; import java.util.LinkedList; import java.util.Deque; / * @author 今日头条：老陈说编程 * LinkedList作为双端队列（Deque）的用法 * 演示了LinkedList作为双端队列时的常用操作，包括双端添加、获取和删除元素， * 以及如何将其用作栈（LIFO）和队列（FIFO）。 */ public class LinkedListDequeOps { public static void main(String[] args) { // 1. 创建双端队列（Deque接口的实现类可以是LinkedList） Deque<String> deque = new LinkedList<>(); // 2. 双端添加元素（支持在队列头部和尾部添加元素） deque.offerFirst("A"); // 在队列头部添加元素A deque.offerLast("B"); // 在队列尾部添加元素B deque.offerFirst("0"); // 在队列头部再添加元素0 System.out.println("双端队列：" + deque); // 输出: [0, A, B] // 3. 双端获取元素（仅获取不删除元素） String first = deque.peekFirst(); // 获取队列头部元素（不删除） String last = deque.peekLast(); // 获取队列尾部元素（不删除） System.out.println("头部元素：" + first + "，尾部元素：" + last); // 4. 双端删除元素（获取并删除元素） String pollFirst = deque.pollFirst(); // 删除并返回队列头部元素 String pollLast = deque.pollLast(); // 删除并返回队列尾部元素 System.out.println("删除后队列：" + deque); // 输出: [A] // 5. 双端队列作为栈（LIFO - 后进先出）使用 Deque<Integer> stack = new LinkedList<>(); stack.push(1); // 入栈操作（等价于offerFirst，将元素添加到队列头部） stack.push(2); System.out.println("栈：" + stack); // 输出: [2, 1] int pop = stack.pop(); // 出栈操作（等价于pollFirst，删除队列头部元素） System.out.println("出栈元素：" + pop + "，剩余栈：" + stack); // 输出: 2, [1] // 6. 双端队列作为队列（FIFO - 先进先出）使用 Deque<Integer> queue = new LinkedList<>(); queue.offer(10); // 入队操作（等价于offerLast，将元素添加到队列尾部） queue.offer(20); System.out.println("队列：" + queue); // 输出: [10, 20] int poll = queue.poll(); // 出队操作（等价于pollFirst，删除队列头部元素） System.out.println("出队元素：" + poll + "，剩余队列：" + queue); // 输出: 10, [20] } }

下期将讲解 Java 集合中的HashSet，记得点赞关注，评论区留你遇到的 LinkedList 问题，我们一起解决！

#java##计算机##程序员##编程#