#从数组到链表从数据结构的底层原理到 Java 集合框架中的 LinkedList理解数据是如何被组织、存储和操作的一、前言在完成 Java SE 基础语法的学习之后我们会逐渐接触数据结构之前学习数组的时候更多关注的是如何把多个数据保存到一起而学习链表之后就会开始思考另外一个问题数据到底应该以什么方式组织和存储数组可以通过下标快速访问元素但是它的长度通常固定而且在中间插入、删除数据时可能需要移动大量元素。链表则采用了完全不同的思路。它不要求所有数据连续存放而是通过一个个节点之间的引用关系将多个数据连接起来。Java 中还提供了现成的 LinkedList 集合类使我们不需要自己从零实现链表就可以使用链表的相关功能。因此这一阶段的学习可以分成两个部分链表↓理解底层数据结构和节点之间的关系↓LinkedList↓理解 Java 如何把链表封装成集合二、什么是链表链表Linked List是一种常见的线性数据结构与数组不同链表中的每一个元素通常被称为一个节点Node。一个节点一般包含两个部分┌──────────────┬──────────────┐│ 数据 │ 下一节点 ││ data │ next │└──────────────┴──────────────┘例如Node1 Node2 Node3┌──────┬─────┐ ┌──────┬─────┐ ┌──────┬──────┐│ 10 │ ●──┼────→│ 20 │ ●──┼────→│ 30 │ null │└──────┴─────┘ └──────┴─────┘ └──────┴──────┘可以看到10 → 20 → 30 → null这就是一个最基本的单向链表。这里的 next 并不是保存下一个数据本身而是保存下一个节点的引用。因此链表最重要的思想就是通过节点之间的引用关系将多个独立的节点连接起来三、数组和链表有什么区别在学习链表之前我首先需要理解它为什么会出现。数组数组┌────┬────┬────┬────┬────┐│ 10 │ 20 │ 30 │ 40 │ 50 │└────┴────┴────┴────┴────┘0 1 2 3 4数组中的元素按照一定顺序存储可以直接通过下标访问。例如int[] arr {10,20,30,40,50}; System.out.println(arr[3]);可以直接获取40。而链表10 → 20 → 30 → 40 → 50如果想找到 40通常需要从头节点开始一个节点一个节点向后寻找。因此对比数组链表存储方式连续存储节点通过引用连接随机访问快慢根据下标访问支持不适合中间插入成本较高节点调整较方便中间删除成本较高节点调整较方便内存利用连续空间节点分散存储结构简单更灵活所以并不存在绝对意义上的“数组好”或者“链表好”。真正应该考虑的是当前的问题更适合哪一种数据结构四、链表的核心结构1. 节点 Node如果自己实现一个简单的单向链表可以首先定义一个节点class Node{ int data; Node next; public Node(int data) { this.datadata; } }这里int data;用于保存数据。而Node next用于保存下一个节点的引用。五、手动创建一个链表例如创建10 → 20 → 30代码可以写成Node node1 new Node(10); Node node2 new Node(20); Node node3 new Node(30); node1.next node2; node2.next node3;最终形成node1│↓┌────┬─────┐│ 10 │ ●──┼────┐└────┴─────┘ ↓┌────┬─────┐│ 20 │ ●──┼────┐└────┴─────┘ ↓┌────┬──────┐│ 30 │ null │└────┴──────┘这时候就可以从 node1 开始遍历整个链表。Node current node1; while (current ! null) { System.out.println(current.data); current current.next; }输出102030这里的current current.next;就是链表遍历中最核心的操作之一。六、单向链表刚才介绍的是最基本的单向链表。它的特点是Node│↓data next每个节点只能知道自己的下一个节点。结构head↓10 → 20 → 30 → 40 → null其中 head 表示链表的头节点。如果需要访问最后一个节点就必须从头开始逐个寻找。七、双向链表除了单向链表还有一种比较重要的结构双向链表。双向链表中的节点通常包含┌─────────┬──────┬─────────┐│ prev │ data │ next │└─────────┴──────┴─────────┘例如null ← 10 ⇄ 20 ⇄ 30 → null每一个节点既可以找到前面的节点也可以找到后面的节点。因此相比单向链表双向链表在某些插入、删除以及反向遍历场景中更加灵活。八、链表中的几个重要操作学习链表的时候我认为最重要的不是记住各种代码而是理解几个基本操作。1. 遍历Node current head; while (current ! null) { System.out.println(current.data); current current.next; }核心思想当前节点↓获取数据↓移动到下一个节点↓继续判断2. 查找例如寻找数据 30Node current head; while (current ! null) { if (current.data 30) { System.out.println(找到了); break; } current current.next; }3. 插入例如10 → 20 → 40现在想把 30 插入到 20 和 40 之间10 → 20 → 30 → 40本质上需要修改节点之间的引用关系。4. 删除例如删除 3010 → 20 → 30 → 40变成10 → 20 → 40核心仍然是调整节点之间的引用关系。这也是链表和数组非常重要的区别之一。九、时间复杂度为什么链表适合插入和删除学习数据结构时我们接触一个非常重要的概念时间复杂度简单来看操作数组链表根据下标访问O(1)O(n)查找元素O(nO(n)头部插入O(n)O(1)已知节点位置插入O(n)O(1)已知节点位置删除O(n)O(1)这里需要特别注意链表的插入和删除并不是任何情况下都是 O(1)。如果你已经找到需要操作的位置只需要修改节点之间的引用那么插入或删除本身可以做到 O(1)。但是如果你需要先从头节点遍历到目标位置那么寻找目标位置本身仍然需要 O(n)。所以链表的优势主要来自节点连接关系的调整而不是“所有插入删除都很快”十、Java 中的 LinkedLi如果每次都自己实现链表代码量会比较大。Java 已经为我们提供了LinkedList它属于 Java 集合框架的一部分。使用时import java.util.LinkedList;然后LinkedListInteger list new LinkedList();现在就可以像其中添加数据list.add(10); list.add(20); list.add(30);此时LinkedList↓10 → 20 → 30十一、LinkedList 的基本操作1. 添加元素LinkedListInteger list new LinkedList(); list.add(10); list.add(20); list.add(30);也可以指定位置list.add(1, 100);结果10 → 100 → 20 → 302. 获取元素System.out.println(list.get(0));可以根据索引获取元素。但是要注意“LinkedList 并不适合频繁通过索引访问元素因为它不像数组那样可以直接定位到对应位置。3. 修改元素list.set(1, 200)将索引 1 位置的元素修改为 200。4. 删除元素list.remove(1);也可以list.removeFirst(); list.removeLast();分别删除第一个和最后一个元素。十二、LinkedList 的特殊能力LinkedList 和普通的 List 最大的一个区别是它同时具备比较明显的双向链表特征。因此它还提供了一些非常方便的方法。例如list.addFirst(10); list.addLast(20); list.getFirst(); list.getLast(); list.removeFirst(); list.removeLast();可以简单理解成LinkedList│┌───────┴───────┐↓ ↓List Deque│ │↓ ↓按列表管理 两端进行操作因此 LinkedList 不只是一个“链表集合”还可以用于实现队列、双端队列等结构。十三、LinkedList 与 ArrayList 的区别这是 Java 集合学习中非常重要的一组对比。对比ArrayListLinkedList底层结构动态数组双向链表随机访问快较慢get(index)O(1)O(n)尾部添加通常较快较快中间插入/删除需要移动元素已定位节点后调整引用内存占用相对较低每个节点需要额外引用适合场景查询较多两端操作较多所以实际开发中不能简单理解为“需要插入删除就用 LinkedList”更合理的判断方式是如果程序存在大量随机访问通常优先考虑 ArrayList如果需要频繁进行两端操作可以考虑 LinkedList 或其他更合适的队列/双端队列实现十四、LinkedList 的使用示例下面通过一个简单案例综合使用 LinkedList。import java.util.LinkedList; public class LinkedListDemo { public static void main(String[] args) { LinkedListString list new LinkedList(); // 添加元素 list.add(Java); list.add(MySQL); list.add(Spring); // 头部添加 list.addFirst(JavaSE); // 尾部添加 list.addLast(SpringBoot); // 遍历 for (String item : list) { System.out.println(item); } // 删除第一个元素 list.removeFirst(); // 删除最后一个元素 list.removeLast(); System.out.println(list); } }这个例子把 LinkedList 最基本的一些操作串联了起来。通过自己编写和运行这样的代码我认为比单纯记忆 API 更容易真正理解 LinkedList。十五、为什么要学习链表刚开始学习链表的时候可能会觉得“Java 已经有 LinkedList 了为什么还要自己学习链表”我认为原因主要有三个。第一理解数据结构如果只会LinkedListInteger list new LinkedList();我们只是知道怎么使用工具。而学习链表的节点、引用、遍历、插入和删除之后才开始理解这个工具底层为什么可以这样工作第二为算法学习打基础链表是很多算法问题的重要基础。例如- 链表反转- 链表中点- 判断链表是否有环- 合并两个有序链表- 删除链表节点- 快慢指针这些都是非常经典的链表问题。第三培养抽象能力学习链表之后我们会开始发现数据结构其实是在研究如何组织数据以及如何更加高效地操作数据这比单纯学习某一个 Java API 更重要。 链表与LikedList
#从数组到链表从数据结构的底层原理到 Java 集合框架中的 LinkedList理解数据是如何被组织、存储和操作的一、前言在完成 Java SE 基础语法的学习之后我们会逐渐接触数据结构之前学习数组的时候更多关注的是如何把多个数据保存到一起而学习链表之后就会开始思考另外一个问题数据到底应该以什么方式组织和存储数组可以通过下标快速访问元素但是它的长度通常固定而且在中间插入、删除数据时可能需要移动大量元素。链表则采用了完全不同的思路。它不要求所有数据连续存放而是通过一个个节点之间的引用关系将多个数据连接起来。Java 中还提供了现成的 LinkedList 集合类使我们不需要自己从零实现链表就可以使用链表的相关功能。因此这一阶段的学习可以分成两个部分链表↓理解底层数据结构和节点之间的关系↓LinkedList↓理解 Java 如何把链表封装成集合二、什么是链表链表Linked List是一种常见的线性数据结构与数组不同链表中的每一个元素通常被称为一个节点Node。一个节点一般包含两个部分┌──────────────┬──────────────┐│ 数据 │ 下一节点 ││ data │ next │└──────────────┴──────────────┘例如Node1 Node2 Node3┌──────┬─────┐ ┌──────┬─────┐ ┌──────┬──────┐│ 10 │ ●──┼────→│ 20 │ ●──┼────→│ 30 │ null │└──────┴─────┘ └──────┴─────┘ └──────┴──────┘可以看到10 → 20 → 30 → null这就是一个最基本的单向链表。这里的 next 并不是保存下一个数据本身而是保存下一个节点的引用。因此链表最重要的思想就是通过节点之间的引用关系将多个独立的节点连接起来三、数组和链表有什么区别在学习链表之前我首先需要理解它为什么会出现。数组数组┌────┬────┬────┬────┬────┐│ 10 │ 20 │ 30 │ 40 │ 50 │└────┴────┴────┴────┴────┘0 1 2 3 4数组中的元素按照一定顺序存储可以直接通过下标访问。例如int[] arr {10,20,30,40,50}; System.out.println(arr[3]);可以直接获取40。而链表10 → 20 → 30 → 40 → 50如果想找到 40通常需要从头节点开始一个节点一个节点向后寻找。因此对比数组链表存储方式连续存储节点通过引用连接随机访问快慢根据下标访问支持不适合中间插入成本较高节点调整较方便中间删除成本较高节点调整较方便内存利用连续空间节点分散存储结构简单更灵活所以并不存在绝对意义上的“数组好”或者“链表好”。真正应该考虑的是当前的问题更适合哪一种数据结构四、链表的核心结构1. 节点 Node如果自己实现一个简单的单向链表可以首先定义一个节点class Node{ int data; Node next; public Node(int data) { this.datadata; } }这里int data;用于保存数据。而Node next用于保存下一个节点的引用。五、手动创建一个链表例如创建10 → 20 → 30代码可以写成Node node1 new Node(10); Node node2 new Node(20); Node node3 new Node(30); node1.next node2; node2.next node3;最终形成node1│↓┌────┬─────┐│ 10 │ ●──┼────┐└────┴─────┘ ↓┌────┬─────┐│ 20 │ ●──┼────┐└────┴─────┘ ↓┌────┬──────┐│ 30 │ null │└────┴──────┘这时候就可以从 node1 开始遍历整个链表。Node current node1; while (current ! null) { System.out.println(current.data); current current.next; }输出102030这里的current current.next;就是链表遍历中最核心的操作之一。六、单向链表刚才介绍的是最基本的单向链表。它的特点是Node│↓data next每个节点只能知道自己的下一个节点。结构head↓10 → 20 → 30 → 40 → null其中 head 表示链表的头节点。如果需要访问最后一个节点就必须从头开始逐个寻找。七、双向链表除了单向链表还有一种比较重要的结构双向链表。双向链表中的节点通常包含┌─────────┬──────┬─────────┐│ prev │ data │ next │└─────────┴──────┴─────────┘例如null ← 10 ⇄ 20 ⇄ 30 → null每一个节点既可以找到前面的节点也可以找到后面的节点。因此相比单向链表双向链表在某些插入、删除以及反向遍历场景中更加灵活。八、链表中的几个重要操作学习链表的时候我认为最重要的不是记住各种代码而是理解几个基本操作。1. 遍历Node current head; while (current ! null) { System.out.println(current.data); current current.next; }核心思想当前节点↓获取数据↓移动到下一个节点↓继续判断2. 查找例如寻找数据 30Node current head; while (current ! null) { if (current.data 30) { System.out.println(找到了); break; } current current.next; }3. 插入例如10 → 20 → 40现在想把 30 插入到 20 和 40 之间10 → 20 → 30 → 40本质上需要修改节点之间的引用关系。4. 删除例如删除 3010 → 20 → 30 → 40变成10 → 20 → 40核心仍然是调整节点之间的引用关系。这也是链表和数组非常重要的区别之一。九、时间复杂度为什么链表适合插入和删除学习数据结构时我们接触一个非常重要的概念时间复杂度简单来看操作数组链表根据下标访问O(1)O(n)查找元素O(nO(n)头部插入O(n)O(1)已知节点位置插入O(n)O(1)已知节点位置删除O(n)O(1)这里需要特别注意链表的插入和删除并不是任何情况下都是 O(1)。如果你已经找到需要操作的位置只需要修改节点之间的引用那么插入或删除本身可以做到 O(1)。但是如果你需要先从头节点遍历到目标位置那么寻找目标位置本身仍然需要 O(n)。所以链表的优势主要来自节点连接关系的调整而不是“所有插入删除都很快”十、Java 中的 LinkedLi如果每次都自己实现链表代码量会比较大。Java 已经为我们提供了LinkedList它属于 Java 集合框架的一部分。使用时import java.util.LinkedList;然后LinkedListInteger list new LinkedList();现在就可以像其中添加数据list.add(10); list.add(20); list.add(30);此时LinkedList↓10 → 20 → 30十一、LinkedList 的基本操作1. 添加元素LinkedListInteger list new LinkedList(); list.add(10); list.add(20); list.add(30);也可以指定位置list.add(1, 100);结果10 → 100 → 20 → 302. 获取元素System.out.println(list.get(0));可以根据索引获取元素。但是要注意“LinkedList 并不适合频繁通过索引访问元素因为它不像数组那样可以直接定位到对应位置。3. 修改元素list.set(1, 200)将索引 1 位置的元素修改为 200。4. 删除元素list.remove(1);也可以list.removeFirst(); list.removeLast();分别删除第一个和最后一个元素。十二、LinkedList 的特殊能力LinkedList 和普通的 List 最大的一个区别是它同时具备比较明显的双向链表特征。因此它还提供了一些非常方便的方法。例如list.addFirst(10); list.addLast(20); list.getFirst(); list.getLast(); list.removeFirst(); list.removeLast();可以简单理解成LinkedList│┌───────┴───────┐↓ ↓List Deque│ │↓ ↓按列表管理 两端进行操作因此 LinkedList 不只是一个“链表集合”还可以用于实现队列、双端队列等结构。十三、LinkedList 与 ArrayList 的区别这是 Java 集合学习中非常重要的一组对比。对比ArrayListLinkedList底层结构动态数组双向链表随机访问快较慢get(index)O(1)O(n)尾部添加通常较快较快中间插入/删除需要移动元素已定位节点后调整引用内存占用相对较低每个节点需要额外引用适合场景查询较多两端操作较多所以实际开发中不能简单理解为“需要插入删除就用 LinkedList”更合理的判断方式是如果程序存在大量随机访问通常优先考虑 ArrayList如果需要频繁进行两端操作可以考虑 LinkedList 或其他更合适的队列/双端队列实现十四、LinkedList 的使用示例下面通过一个简单案例综合使用 LinkedList。import java.util.LinkedList; public class LinkedListDemo { public static void main(String[] args) { LinkedListString list new LinkedList(); // 添加元素 list.add(Java); list.add(MySQL); list.add(Spring); // 头部添加 list.addFirst(JavaSE); // 尾部添加 list.addLast(SpringBoot); // 遍历 for (String item : list) { System.out.println(item); } // 删除第一个元素 list.removeFirst(); // 删除最后一个元素 list.removeLast(); System.out.println(list); } }这个例子把 LinkedList 最基本的一些操作串联了起来。通过自己编写和运行这样的代码我认为比单纯记忆 API 更容易真正理解 LinkedList。十五、为什么要学习链表刚开始学习链表的时候可能会觉得“Java 已经有 LinkedList 了为什么还要自己学习链表”我认为原因主要有三个。第一理解数据结构如果只会LinkedListInteger list new LinkedList();我们只是知道怎么使用工具。而学习链表的节点、引用、遍历、插入和删除之后才开始理解这个工具底层为什么可以这样工作第二为算法学习打基础链表是很多算法问题的重要基础。例如- 链表反转- 链表中点- 判断链表是否有环- 合并两个有序链表- 删除链表节点- 快慢指针这些都是非常经典的链表问题。第三培养抽象能力学习链表之后我们会开始发现数据结构其实是在研究如何组织数据以及如何更加高效地操作数据这比单纯学习某一个 Java API 更重要。