数据结构：4.2 LinkedList（内置）和MyLinkedList（手写实现）

【目标】

1.手写MyLinkedList，体会LinkedList的底层逻辑

2.掌握LinkedList中的一些方法等

3.章节测试

【引言】

关于数据结构，我们按照逻辑关系进行划分，可以分为以下部分：

所谓数据结构，就是对数据的整合与存储，没有数据结构，程序就没办法高效地处理复杂数据。

而java相较于c的不同是其内置了部分经典、常用的数据结构，我们在开发的过程中，不能只会用内置数据结构的方法等，还要明白底层是怎么实现的。因此我们本节的学习顺序就是从自己实现链表——MyLinkedList{MysinglyLinkdeList（单向链表的实现） 和 MyDoublyLinkedList（双向链表的实现）}，在此之后认识并掌握内置链表——LinkedList（双向链表的实现）。

提醒：本章我们用基本数据类型进行演示，如果要顺序表中存储的元素是引用类型，还需要具体的根据需求进行操作

1.ArrayList的弊端

1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)——>进行增删时，时间复杂度大

2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。——>时间消耗 和 空间消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继 续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。——>空间浪费

为了解决上述问题，我们引入了链表。

2.MyLinkedList

2.1 链表的类型

链表的修饰是这样的： 单向/双向、带头/不带头、循环/非循环

我们先来解释一下分别都是什么含义：

2.1.1 单向/双向

链表的方向分为单向和双向，其中具体的示例图如下：

单向：

双向：

2.1.2 带头/不带头

所谓头，指的就是头节点。先提醒：第一个数据元素所在的节点叫做首元节点（首元节点是会发生变化的）；头节点就是数据域不存储数据元素、指针域指向首元节点的节点，这个头节点是链表的一部分（对于整个链表的 任何操作 都会操作到头结点），是固定不变的（不像首元结点可以进行变化）。

我们再说头指针，头指针就是这个head，是一个引用，恒指向链表的第一个节点（有头时指向头结点，无头时指向首元节点）

不带头：

带头：

在这里提醒一句：有些初学者在学到链表的时候，对于这个头指针会有模糊的认识（似懂非懂），我们这里就进行说明白。

2.1.3 循环/非循环

所谓循环，就是链表的尾节点指向头节点。

非循环：

循环：

2.1.4 总结与介绍

所以说总共有八种链表形式，本章节我们主要进行实现常用的两种——单向不带头非循环链表和双向不带头非循环链表

2.2 MySinglyLinkedLIst（单向不带头非循环链表）

2.2.1 基本结构

单向链表是通过一组物理地址不连续的存储单元（节点）来存储数据元素的线性结构。

每个节点由数据域（存储元素值）和指针域（存储下一个节点的地址）组成，节点之间的逻辑顺序（逻辑上是连续的）通过指针链接实现。整个链表通过头指针（指向第一个节点）来标识，最后一个节点的指针指向NULL（空），表示链表的结束。

2.2.2单向链表的增（Create）、删（Delete）、查（Read）、改（Update）——CRUD

1.打印链表

@Override public void display() { ListNode cur = this.head; while(cur != null) { System.out.print(cur.val + " "); cur = cur.next; } } public static void main(String[] args) { //我们进行打印 System.out.print("目前的链表元素是："); mySinglyLinkedList.display(); }

2.增加/插入节点

2.1 头插法

//头插法 @Override public void addFirst(int data) { ListNode node = new ListNode(data); node.next = this.head; this.head = node; } public static void main(String[] args) { //1.头插 System.out.print("请输入你要添加的元素（头插）："); int data1 = scanner.nextInt(); mySinglyLinkedList.addFirst(data1); System.out.print("目前的链表元素是："); mySinglyLinkedList.display(); }

2.2 尾插法

//尾插法 @Override public void addLast(int data) { ListNode node = new ListNode(data); if (this.head == null) { this.head = node; return; } //这里我们需要先进行遍历 ListNode cur = this.head; while(cur.next != null) { cur = cur.next; } //说明这个时候走到了最后一个元素位置 cur.next = node; } public static void main(String[] args) { //2.尾插 System.out.print("请输入你要添加的元素（尾插）："); int data2 = scanner.nextInt(); mySinglyLinkedList.addLast(data2); System.out.print("目前的链表元素是："); mySinglyLinkedList.display(); }

2.3 指定位置插入

public class SizeException extends RuntimeException { public SizeException(String message) { super(message); } } //得到单链表的长度 @Override public int size() { int count = 0; ListNode cur = this.head; while(cur != null) { count++; cur = cur.next; } return count; } //指定位置插入 @Override public void addIndex(int index,int data) { //由于不是数组，我们这里规定，第一个节点就是0号位置 int len = size(); //表示指定位置有错，那么我们就报错 if(index < 0 || index > len) { throw new SizeException("你指定位置有误"); } ListNode node = new ListNode(data); if (index == 0) { node.next = this.head; this.head = node; return; } //遍历到指定位置的前一个节点 ListNode cur = this.head; for (int i = 0; i < index - 1; i++) { cur = cur.next; } node.next = cur.next; cur.next = node; } public static void main(String[] args) { //3.任意位置插入 System.out.print("请输入你要添加的元素："); int data3 = scanner.nextInt(); System.out.print("请输入你要添加的元素的位置："); int index = scanner.nextInt(); mySinglyLinkedList.addIndex(index,data3); System.out.print("目前的链表元素是："); mySinglyLinkedList.display(); }

在这里有一个小的知识点，就是关于 异常——throws 的小知识点。

可能会有人提出疑问，为什么这里不写成：

addIndex(int index,int data) throws SizeException

反而写的是：

addIndex(int index,int data)

实际上对于非受检异常（运行期检查），我们可以写throws，也可以不写，在工程上我们一般是不写的。而对于受检异常（编译期检查），我们必须要写throws。

• 写不写都能编译是Java语言为了区分两种异常的设计

• 建议不写是为了保持语义清晰：让调用者明白，这是他们的代码写错了，不是运行时需要处理的外部异常（即受检异常）

3.查找指定节点的数据元素

//数据的查找 @Override public boolean contains(int key) { ListNode cur = head; //进行遍历 while(cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; } public static void main(String[] args) { //查找链表中是否有指定元素，有的话就打印true System.out.print("请输入你要查找的元素："); int data4 = scanner.nextInt(); System.out.println(mySinglyLinkedList.contains(data4)); }

4.删除节点

4.1 删除第一次出现关键字为key的节点

//节点的删除 private ListNode find(ListNode listNode, int key) { //调用这个方法的前提是已经确定了有这个元素了 ListNode cur1 = listNode; ListNode cur2 = listNode; //找到指定位置的前一个 int flag = 0; while(cur1 != null) { if(key == cur1.val) { break;//表示到了指定位置 } flag++; cur1 = cur1.next; } //这时候flag所代表的数就是该指定位置的位置（默认初始位置是0） //走到这里表示知道了这个指定位置的前一个的位置了，那么我们进行遍历 for (int i = 0; i < flag - 1; i++) { cur2 = cur2.next; } return cur2; //这一个方法是这样的： //如果删除的元素是第一个，那么返回值就是第一个节点 //如果删除的元素不是第一个，那么返回值就是该节点的上一个节点 } //1.删除第一次出现关键字为key的节点 @Override public void remove(int key) { ListNode cur = this.head; //进行遍历 while(cur != null) { if(cur.val == key) { ListNode ret = find(this.head, key); if(ret == this.head) { //表示的是第一个节点 this.head = this.head.next;//删除头节点 }else { //表示的是非第一个节点 ret.next = cur.next; } //cur = null;置空 //这一步是没有必要的，因为java不同于c，没有被指向的内存空间会被jvm的GC自动回收 System.out.println("删除成功"); return; } cur = cur.next; } System.out.println("单链表中没有你要删除的内容"); } public static void main(String[] args) { //删除第一次出现为key的节点 System.out.print("请输入你要删除的元素(删除第一个)："); int data5 = scanner.nextInt(); mySinglyLinkedList.remove(data5); System.out.print("目前的链表元素是："); mySinglyLinkedList.display(); }

4.2 删除全部出现关键字为key的节点

//2.删除全部出现关键字为key的节点 @Override public void removeAllKey(int key) { while (this.head != null && this.head.val == key) { this.head = this.head.next; //连续去掉匹配的头节点，保证头节点不是指定删除的节点，比如 //key == 13 //而链表是：13、13、13、15、85 } if(this.head == null){ return; } ListNode cur = this.head.next; ListNode prev = this.head; while(cur != null) { if(cur.val == key) { prev.next = cur.next; cur = cur.next; }else { prev = cur; cur = cur.next; } } } public static void main(String[] args) {//删除全部出现为key的节点 System.out.print("请输入你要删除的元素（删除所有）："); int data6 = scanner.nextInt(); mySinglyLinkedList.removeAllKey(data6); System.out.print("目前的链表元素是："); mySinglyLinkedList.display(); }

4.3 清空链表

//删除整个链表 @Override public void clear() { while(this.head != null) { ListNode cur = this.head.next; this.head = cur; if(this.head != null) { //表示未走到最后一个位置 cur = this.head.next; } } } public static void main(String[] args) { //清空链表 System.out.print("接下来是清空后的链表:"); mySinglyLinkedList.clear(); }

5.修改节点的元素

public class SizeException extends RuntimeException { public SizeException(String message) { super(message); } } //指定位置数据元素的修改 @Override public void exchange(int index, int data) { //指定第一个数据节点所在的位置为0 int len = size(); //表示指定位置有错，那么我们就报错 if(index < 0 || index > len) { throw new SizeException("你指定位置有误"); } ListNode cur = this.head; for (int i = 0; i < index; i++) { cur = cur.next; } //这里说明到了指定的位置了 cur.val = data; } public static void main(String[] args) { //修改指定位置的元素 System.out.print("请输入你要修改的元素："); int data_e = scanner.nextInt(); System.out.print("请输入你要修改的元素的位置："); int index_e = scanner.nextInt(); mySinglyLinkedList.exchange(index_e, data_e); System.out.print("目前的链表元素是："); mySinglyLinkedList.display(); }

2.2.3 总结

针对单链表，我们需要记住的是：单链表是用一段物理地址不连续的存储单元依次存储数据元素的线性结构。也就是说我们需要记住的是单链表的结构，至于具体的方法，要根据存储的数据元素的类型来进行改写，对存储不同类型数据元素的单链表的操作并不相同。

2.3 MyDoublyLinkedList（双向不带头非循环链表）

单链表是“向前看”的简洁设计，当你需要“回头”时，就会付出遍历的代价。而双链表为“回头看”这个能力，多花了一点内存（每个节点需要额外存储一个prev指针）和操作时间（执行具体操作步骤时，需要多做几次指针赋值），换来了更高的灵活性。

在学习双向链表时，我们不需要有过多压力、认为双向链表很难，其实双向链表的操作在逻辑上和单向链表无异，只是在实操过程中需要多处理一个指针。

2.3.1 基本结构

双向链表是通过一组物理地址不连续的存储单元（节点）来存储数据元素的线性结构。

每个节点由数据域（存储元素值）、指针域（存储下一个节点的地址）和另一个指针域（存储上一个节点的地址）组成，节点之间的逻辑顺序通过双向的指针链接实现。整个链表通过头指针（指向第一个节点）来标识，通常也会保留尾指针（指向最后一个节点）以便从尾部操作。第一个节点的“上一个节点”指针指向NULL，最后一个节点的“下一个节点”指针也指向NULL，表示链表的边界。

2.3.2双向链表的增（Create）、删（Delete）、查（Read）、改（Update）——CRUD

1.打印链表

@Override public void display() { ListNode cur = this.head; while(cur != null) { System.out.print(cur.val + " "); cur = cur.next; } } public static void main(String[] args) { //我们进行打印 System.out.print("目前的链表元素是："); mySinglyLinkedList.display(); }

2.增加/插入节点

2.1 头插法

//1.头插法 public void addFirst(int data) { ListNode node = new ListNode(data); if(this.head == null) { this.head = this.tail = node; }else { node.next = this.head; this.head.prev = node; this.head = node; } } public static void main(String[] args) { //1.头插 System.out.print("请输入你要添加的元素（头插）："); int data1 = scanner.nextInt(); myDoublyLinkedList.addFirst(data1); System.out.print("目前的链表元素是："); myDoublyLinkedList.display(); }

2.2 尾插法

//2.尾插法 public void addLast(int data) { ListNode node = new ListNode(data); if(this.head == null) { this.head = this.tail = node; }else { node.prev = this.tail; this.tail.next = node; this.tail = node; } } public static void main(String[] args) { //2.尾插 System.out.print("请输入你要添加的元素（尾插）："); int data2 = scanner.nextInt(); myDoublyLinkedList.addLast(data2); System.out.print("目前的链表元素是："); myDoublyLinkedList.display(); }

2.3 指定位置插入

@Override public int size() { ListNode cur = this.head; int flag = 0; while(cur != null) { flag++; cur = cur.next; } return flag; } //3.任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data) { int len = this.size(); if(index < 0 || index > len) { throw new SizeException("你指定的位置有错误"); } ListNode node = new ListNode(data); if(this.head == null) { this.head = this.tail = node; } ListNode cur = this.head; if(index == 0) { this.addFirst(data); return; }else if(index == len){ this.addLast(data); return; }else { int count = 0; while(cur != null) { if(count == index) { break; } count++; cur = cur.next; } //走到这里表示 cur 为指定位置原来的节点 cur.prev.next = node; node.prev = node.prev; cur.prev = node; node.next = cur; } } public static void main(String[] args) { //3.任意位置插入 System.out.print("请输入你要添加的元素："); int data3 = scanner.nextInt(); System.out.print("请输入你要添加的元素的位置："); int index = scanner.nextInt(); myDoublyLinkedList.addIndex(index,data3); System.out.print("目前的链表元素是："); myDoublyLinkedList.display(); }

3.查找指定节点的数据元素

//数据的查找 @Override public boolean contains(int key) { ListNode cur = head; //进行遍历 while(cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; } public static void main(String[] args) { //查找链表中是否有指定元素，有的话就打印true System.out.print("请输入你要查找的元素："); int data4 = scanner.nextInt(); System.out.println(myDoublyLinkedList.contains(data4)); }

4.删除节点

4.1 删除第一次出现关键字为key的节点

//删除第一次出现为key的节点 @Override public void remove(int key) { if (this.head == null) { System.out.println("当前是空链表，不能进行删除"); } ListNode cur = this.head; while(cur.next != null) { if(cur.val == key) { //走到这里了表示cur就是要删除的节点 System.out.println("链表中有你要删除的节点,已删除一个"); if(cur == this.head) { this.head = this.head.next; }else if(cur == this.tail) { this.tail = this.tail.prev; }else { cur.prev.next = cur.next; cur.next.prev = cur.prev; } break; } cur = cur.next; } if(cur == null) { //表示遍历到了最后了，但是还是没有找到 System.out.println("当前链表中没有你要删除的节点"); return; } } public static void main(String[] args) { //删除第一次出现为key的节点 System.out.print("请输入你要删除的元素（删除第一个）："); int data5 = scanner.nextInt(); myDoublyLinkedList.removeAllKey(data5); System.out.print("目前的链表元素是："); myDoublyLinkedList.display(); }

4.2 删除全部出现关键字为key的节点

//删除全部出现为key的节点 @Override public void removeAllKey(int key) { if (this.head == null) { System.out.println("当前是空链表，不能进行删除"); } ListNode cur = this.head; boolean flag = false;//用来判断链表中是否有指定删除的节点 while(cur.next != null) { if(cur.val == key) { //表示找到了 flag = true; if(cur == this.head) { this.head = this.head.next; }else if(cur == this.tail) { this.tail = this.tail.prev; }else { cur.prev.next = cur.next; cur.next.prev = cur.prev; } } cur = cur.next; } if(flag) { System.out.println("链表中有你要删除的节点，已删除所有"); } } public static void main(String[] args) { System.out.print("请输入你要删除的元素（删除所有）："); int data6 = scanner.nextInt(); myDoublyLinkedList.removeAllKey(data6); System.out.print("目前的链表元素是："); myDoublyLinkedList.display(); }

4.3 清空链表（需注意）

//清空链表 @Override public void clear() { if(this.head == null) { System.out.println("当前链表已是空链表，不需要进行再次清空"); return; } ListNode cur = this.head; while(cur != null) { ListNode curN = cur.next; cur.prev = null; cur.next = null; cur = curN; } this.head = null; this.tail = null; } public static void main(String[] args) { System.out.print("接下来是清空后的链表:"); myDoublyLinkedList.clear(); myDoublyLinkedList.display(); }

以上的清空链表的方法是和LinkedList一样原理的，其实我们还有个更简单的方法清空链表，那就是

//清空链表 @Override public void clear() { this.head = null; this.tail = null; } public static void main(String[] args) { System.out.print("接下来是清空后的链表:"); myDoublyLinkedList.clear(); myDoublyLinkedList.display(); }

至于为什么可以这样做，我们来进行详细讲解：

一、数据槽的概念

1. JVM 底层没有“变量”和“引用”的语义区分：只有数据槽 (Slot)。它是一个确定大小的存储单元（比如 32 位或 64 位），例 int a ，这个a就是数据槽。

2. 数据槽里存的都是“值”：这个值就是一段二进制数字。

3. 区别在于如何解释这个“值”：

   • 存基本类型：这个值就是数据本身。JVM 直接用。

   • 存引用类型：这个值是对象的地址。JVM 把它作为“线索”，去堆里找真正的对象。

4. 多了的步骤：确实，对于引用类型，JVM 多了“链接 (reference)”这一步——通过地址去堆里定位对象。

二、什么在JVM栈上，什么不在JVM栈上

三、GC Roots

1.什么是 GC Roots？

GC Roots 是一组必须作为“可达性分析”起点的内存对象。

用大白话说：GC Roots 就是 JVM 认定“肯定活着”的那批对象，以及能直接找到这些对象的引用入口。

2.GC Roots干什么的，有什么作用？

JVM 在进行垃圾回收时，会以 GC Roots 作为根节点，顺着它们的引用链向下查找。所有能被找到的对象都标记为存活；找不到的，就标记为垃圾，等待回收。

3.怎么判断是不是 GC Roots？

一个数据槽（内存单元）是 GC Roots，当且仅当：

（1）它不在堆里

（2）它里面存的是一个有效的堆内存地址

这两个条件缺一不可。

四、为啥令 head = tail =null ，就把这个链表回收了

首先，myDoublyLinkedList 这个数据槽存储在 JVM栈 上，作为GC Root。

MyDoublyLinkedList 对象：可达 ✅（因为栈上有myDoublyLinkedList）

其次，接着向下找，当发现 head = tail = null 时

ListNode 节点们：不可达 ❌（因为head = tail = null ，不能到达 ListNode 对象）

所以说，ListNode 节点就被一个一个的回收了

5.修改节点的元素

//修改指定位置的元素 @Override public void exchange(int index_e, int data_e) { int len = this.size(); if (index_e < 0 || index_e > len - 1) { //注意这里是修改，不是尾插 throw new SizeException("你指定的位置有误"); } if (this.head == null) { System.out.println("这个表是空表，无法修改元素"); return; } ListNode cur = this.head; if (index_e == 0) { this.head.val = data_e; return; } else if (index_e == len - 1) { this.tail.val = data_e; return; } else { int count = 0; while (cur != null) { if (count == index_e) { break; } count++; cur = cur.next; } //cur是指定位置的节点 cur.val = data_e; } } public static void main(String[] args) { //修改指定位置的元素 System.out.print("请输入你要修改的元素："); int data_e = scanner.nextInt(); System.out.print("请输入你要修改的元素的位置："); int index_e = scanner.nextInt(); myDoublyLinkedList.exchange(index_e, data_e); System.out.print("目前的链表元素是："); myDoublyLinkedList.display(); }

3.LinkedList

3.1 LinkedList的简介

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

LinkdeList 采用单继承（extends）、多实现（implement）的结构关系

实线 + 箭头 ：继承关系（extends）

虚线 + 箭头 ：实现关系（implement）

3.2 LinkedList的使用

我们对于LinkedList的使用不进行详细解释，只是对某些地方进行简单的提醒，有兴趣的可以自己去看一看。

3.2.1 LinkedList的基本结构

3.2.2 LinkedList的构造

public class TestDemo { public static void main(String[] args) { LinkedList<Integer> li = new LinkedList<>(); li.add(1); li.add(2); li.add(3); li.add(4); System.out.println(li); LinkedList<Integer> li1 = new LinkedList<>(li); System.out.println(li1); } }

LinkedList() 的含义是：创建了一个链表，但是这个链表初始的时候是空的

LinkedList(Collection<? extends E> c)的含义是：

1.我们先不要看<? extends E>，也就是LinkedList(Collection c)，这表明了我的参数须是一个实现了Collection接口的数据，而我们的 li 是 LinkdeList 类型的（LinkedList 实现了 Collection 接口）

2.<? extends E>的意思是我们的链表的操作对象的类型需要是E或者其子类 。我们的 li 的操作对象是Integer类型，li1 要求的操作对象需要是Integer或者其子类

3.这个构造方法的含义就是使用指定集合容器中的元素构造LinkedList

3.2.3 LinkedList的遍历

LinkedList的遍历有三种，分别如下：

1.通过for循环进行遍历

public class TestDemo { public static void main(String[] args) { LinkedList<Integer> li = new LinkedList<>(); li.add(1); li.add(2); li.add(3); li.add(4); //通过 for循环 进行遍历 for (int i = 0; i < li.size(); i++) { System.out.print(li.get(i) + " "); } } }

2.通过for—each循环进行遍历

public class TestDemo { public static void main(String[] args) { LinkedList<Integer> li = new LinkedList<>(); li.add(1); li.add(2); li.add(3); li.add(4); //通过 for—each循环 进行遍历 for (int x: li) { System.out.print( x + " "); } } }

3.通过迭代器（Iterator/ListIterator）进行遍历

public class TestDemo { public static void main(String[] args) { LinkedList<Integer> li = new LinkedList<>(); li.add(1); li.add(2); li.add(3); li.add(4); //通过 迭代器（Iterator/ListIterator）进行遍历 ListIterator<Integer> it = li.listIterator(); //正向遍历 while(it.hasNext()) { System.out.print(it.next() + " ");// 1 2 3 4 } //反向遍历 while(it.hasPrevious()) { System.out.print(it.previous() + " ");// 4 3 2 1 } } }

提醒一句：ListIterator继承了Iterator,在 LIstIterator类中多了反向遍历功能相关的方法

3.2.4 LinkedList的常用方法

4

4.ArrayList 和 LinkedList