阅读量:2
文章目录
前言
我们之前学习过顺序表，也学习了 ArrayList 类的使用，它们的本质实际上就是数组。而今天我们要介绍的链表和它们都不一样，它解决了 ArrayList 不适用做任意位置插入和删除的缺点，链表不需要将元素整体向前或者向后搬移，插入和删除都十分方便，接下来就让我们一起来认识链表吧
1. 链表的介绍
1.1 链表的定义
链表是由多个地址不连续的存储节点连接而成的一种线性表，这些节点在内存中不是连续存放的，每个节点不仅存放实际的数据（数据域），而且包含下一个节点的地址信息（地址域，也叫做指针域）
注意：
- 链表在逻辑结构上是连续的，在物理结构上不一定连续（和顺序表不一样）
- 节点的地址域可以存储下一个节点的地址，最后一个节点的地址域为 null
- 因为创建节点的申请是在堆上的，两次申请的空间可能连续，也可能不连续，它们通常分散在内存中的任何位置
1.2 链表的结构种类
我们可以根据是否带头节点、单向或双向链接、以及是否循环来分类，一共有八种类型，每种类型都有其独特的特点
带头节点或不带头节点
- 带头链表：最前面有一个头节点，称作“哨兵位”，它不存储数据，用来指向第一个存储有效数据的节点
- 不带头链表：直接从第一个节点开始，没有额外的头节点
单向或者双向
- 单向链表：每个节点只包含一个指向下一个节点的地址。它只能从前往后遍历，不能从后往前遍历
- 双向链表：每个节点包含两个地址，一个指向前一个节点，一个指向后一个节点。它可以从任一节点开始向前或向后遍历
循环或者非循环
- 循环链表：链表的最后一个节点的地址域指向链表的第一个节点，形成一个闭环
- 非循环链表：链表的最后一个节点的地址域为空（null），表示链表的结束
在上面八种组合中，我们主要介绍的是：无头单向非循环链表，无头双向非循环链表
- 无头单向非循环链表：结构简单，是一种非常灵活的数据结构，适用于多种不同的应用场景，我们在力扣上刷链表题遇到最多的就是这种类型，也经常出现在很多笔试面试中
- 无头双向非循环链表：在需要双向遍历和频繁修改链表结构的场景中非常有用，而且在 Java 的集合中 LinkedList 的底层就是无头双向非循环链表
2. 单向链表的模拟实现
请注意，以下的链表默认为 无头单向非循环
链表是由若干个节点组成的，而节点又是个完整的结构，包含数据域和地址域，所以我们可以把节点定义为内部类，这样就可以更方便的使用节点
除此之外，我们还需要定义成员变量 head，用来指向第一个节点。因为它是链表的属性，所以应该定义在节点内部类的外面
// 我们创建一个 MySingleLinkedList 类 public class MySingleLinkedList { //内部类-节点 static class ListNode { public int val; //数据域 public ListNode next; //地址域 public ListNode(int val) { this.val = val; } } //链表的头节点 public ListNode head; } 2.1 创建链表
接着我们可以来创建链表，此处先展示比较简单的方法：创建一个个节点，再按顺序连接起来
问题是，我们要怎么让第一个节点和第二个节点进行关联？
node1.next = node2; 原因：node1 指向的是节点对象，可以使用 . 来访问里面的成员属性 next，node2 引用的是完整的对象，它会存储自己所存储位置的地址
//创建链表 public void createList() { ListNode node1 = new ListNode(11); ListNode node2 = new ListNode(22); ListNode node3 = new ListNode(33); ListNode node4 = new ListNode(44); //将前一个节点的 next 赋值为下一个节点的地址 node1.next = node2; node2.next = node3; node3.next = node4; //最后让 head 赋值为第一个节点 this.head = node1; } //最后可以使用 head 来引出整个链表 分析：
- 我们创建 node1 到 node4 共四个节点，再将
next赋值为下一个节点的地址。node4 的节点因为没有赋值，默认为 null，标志链表的结尾。最后再将head为赋值 node1 的地址，就完成了最简单的链表创建 - 出了该方法后，因为node 是局部变量，因此它们都会消失，我们就可以使用 head 来引出整个链表
测试：debug 一下
（这是一个比较粗糙的创建链表方法，仅为了方便理解和演示）
2.2 打印链表
思路：很简单，我们可以让 head 一直往后走，使用 head = head.next 向后遍历，并且当 head == null ，就让循环停下来，表示遍历完成
但是这个方法有一个缺点：即我们只能打印一次，打印完后 head 就变成 null 了，无法再找到该链表。解决方法也很简单，我们设置一个“代理人” cur，打印的时候只让它去往后遍历，head 就还是呆在头节点那里
//打印链表 public void display() { //代理人cur，防止head跑完后找不到头节点 ListNode cur = head; while (cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } 代码运行结果如下：
2.3 求链表长度
思路：cur + 计数器。跟打印链表基本一样，多加了一个计数器，最后返回计数器的值
//求链表长度 public int size() { int count = 0; ListNode cur = head; while (cur != null) { count++; cur = cur.next; } return count; } 3. 单向链表常见方法的模拟实现
3.1 头插法
头插法是在链表中插入新节点的方法，新节点总是被插入到链表的头部，即成为链表的第一个节点
实现思路：我们要先实例化一个新的节点 node，拿着这个节点去头插，插入到当前链表头节点的前面，成为新的头节点；具体操作就是先让新节点和后面的节点建立关系 node.next = head，接着 head 要指向当前头插的新节点 head = node（这两步的顺序一定不能颠倒）
//头插节点，也适用于空链表 public void addFirst(int val) { //先绑后面的节点，再让 head 赋值 ListNode node = new ListNode(val); node.next = head; this.head = node; } - 该头插法也适用于空链表，因为此时的
head为null，node 的地址域指向null也是正确的 - 时间复杂度为 O(1)，在插入节点时不需要遍历整个链表
3.2 尾插法
有头插法，那也应该有尾插法。它是在链表尾部插入新节点的方法，新节点被添加到链表的最后一个节点之后，成为新的最后一个节点
实现思路：还是要先实例化一个新的节点 node，拿着这个节点去尾插；具体操作要先找到链表的尾巴，然后将最后一个节点的 next 赋值为当前要插入节点的地址。而且，尾插需要考虑 head 为空的情况，这个需要单独判断
//后插节点 public void addLast(int val) { ListNode node = new ListNode(val); //如果链表为空 if (head == null) { head = node; return; } //不为空，就正常尾插 ListNode cur = head; while (cur.next != null) { cur = cur.next; } //找到尾节点了，next 赋值 cur.next = node; } - 尾插法需要遍历整个链表以找到最后一个节点，因此时间复杂度为 O(n)，其中 n 是链表的长度
- 为了优化尾插法的性能，我们可以在链表结构中维护一个指向最后一个节点的尾指针，这样在插入新节点时可以直接访问到链表的尾部，而不需要遍历整个链表。但是在每次插入或者删除时都需要更新尾指针
3.3 指定位置插入
我们可以在指定位置 index 插入新节点，假设第一个节点的下标为 0，一共有三种情况我们要考虑到
index不合法，即小于 0 或者大于 链表长度，出现这种情况就报错，抛出异常index为 0，我们就可以使用头插法；index为链表长度，我们就可以使用尾插法index合法且不为 0 也不为链表长度，那我们就正常插入：首先要找到index前一个位置的节点，找到后让新节点的next指向后一个节点node.next = cur.next，然后再把前一个节点的next指向要插入的新节点的地址cur.next = node（这两步的顺序一定不能颠倒）
//在 index 位置插入 public void addIndex(int index, int val) { //1.判断index的合法性 try { checkIndex(index); } catch (IndexNotLegalException e) { e.printStackTrace(); } //2.考虑 index == 0 || index == length if (index == 0) { addFirst(val); return; } if (index == size()){ addLast(val); return; } //3.一切正常就在 index 位置插入 ListNode node = new ListNode(val); ListNode cur = head; //找到 index - 1 位置的节点 int count = index - 1; while (count != 0) { cur = cur.next; count--; } //让新节点的 next 指向下一个节点，且绑定新节点 node.next = cur.next; cur.next = node; } //判断异常 public class IndexNotLegalException extends RuntimeException{ public IndexNotLegalException() { } public IndexNotLegalException(String message) { super(message); } } - 要创建异常类来判断
index的不合法情况 - 先让新节点绑定后面的节点，再让前一个节点的
next指向新节点的地址**（顺序不能乱）**
3.4 查找值 key 的节点是否在链表中
也是非常简单，使用 cur 直接遍历，再判断 key 等不等于每一个节点的 val 值，如果 val 的类型是引用类型，就得使用 equals 来判断。因为此处演示的 val 的类型为 int，所以就直接 == 判断了
//查找是否存在 key public boolean contains(int key) { ListNode cur = head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; } 3.5 删除值为 key 的节点
思路：先判断有没有等于 key 的节点，如果没有就直接 return；如果有，那就得找到数据为 key 的前一个节点，如果跳过这个节点，让前一个节点直接连接后一个节点，这时因为 key 节点没有人引用它，就会被直接回收
//删除值第一个值为 key 的节点 public void remove(int key) { //判空 if (head == null) { return; } //判断头节点，如果是，直接让 head 跳到下一个节点 if (head.val == key) { head = head.next; return; } //正常删除 ListNode cur = head; //不能使用 cur != null，防止空指针异常 while (cur.next != null) { //找到了，开始删除 if (cur.next.val == key) { cur.next = cur.next.next; return; } //继续往后找 cur = cur.next; } } 3.6 删除所有值为 key 的节点
上面介绍的操作实际上删除的是第一个值为 key 的节点，此处我们想要的是删除所有值为 key 的节点，思路类似，但方法还是有些不同：我们先创建 cur 用来表示要删除的节点，prev 用来表示 cur 的前驱节点；接着就是让 cur 去找到值为 key 的节点，找到后让 prev 的 next 去指向 cur 的下一个节点，然后 cur 继续往后走；另外头节点需要单独考虑，删除完成后，最后再来判断头节点的值，如果也是 key，那就让 head 往后走
//删除所有值为 key 的节点 public void removeAllVal(int key) { //判空 if (head == null) { return; } //判断是否相等并删除 ListNode prev = head; ListNode cur = head.next; while (cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { prev = cur; cur = cur.next; } } //判断头节点的值是否为 key if (head.val == key) { head = head.next; } } 3.7 清空链表
清空链表很简单，我们可以直接让 head = null ，这样链表中的所有节点都会被回收，因而被清空；麻烦点的话也可以遍历链表一个个置为 null，
//清空链表（简单版） public void clear1() { head = null; } //清空链表（复杂版） public void clear2() { ListNode cur = head; while(cur != null) { ListNOde curN = cur.next; cur.next = null; cur = curN; } head = null; } 4. 双向链表的模拟实现
请注意，以下的链表默认为 无头双向非循环
上面讲完了单向链表，这里我们再来讲一下双向链表，因为在集合里中的 LinkedList 类的底层就是双向链表，我们来看一下它长什么样
与单向链表的区别在于它不仅有后继节点，还有前驱节点，可以找到前一个节点。而且为了方便从后往前遍历，我们使用 last 来标记最后一个节点
public class MyLinkedList { static class ListNode { public int val; public ListNode prev;//前驱 public ListNode next;//后继 public ListNode(int val) { this.val = val; } } public ListNode head;//标志头节点 public ListNode last;//标志尾节点 } 因为无论单向还是双向链表，在求链表的长度，打印链表，还是查找值 key 的节点是否在链表中这三种方法都是一样的，双向链表这博主就略过了
5. 双向链表常见方法的模拟实现
5.1 头插法
实现思路：首先创建一个新节点，然后让头节点的 prev 赋值为新节点的地址，接着让新节点的 next 指向头节点，最后把 head 赋值为新节点的地址。但是我们还是要考虑空链表的情况
//头插法 public void addFirst(int val) { ListNode node = new ListNode(val); //空链表，直接让 head 和 last 等于 node if (head == null) { head = last = node; } else { //开始绑定，注意顺序不能随意调换 node.next = head; head.prev = node; head = node; } } 5.2 尾插法
实现思路：跟头插法很类似，就是绑定的时候顺序不能乱，也是要判空
//尾插法 public void addLast(int val) { ListNode node = new ListNode(val); //空链表，直接让 head 和 last 等于 node if (head == null) { head = last = node; } else { //绑定 last.next = node; node.prev = last; last = node; } } 5.3 指定位置插入
实现思路：因为在双向链表中，我们可以找到前一个节点，所以就让 cur 直接走到要插入的位置 index，接下来就是绑定了。一共要改变四个地方，顺序什么的不能搞乱了
//在 index 位置前插入 key，且第一个数据节点下标为 0 public void addIndex(int index, int key) { //index 的值不合法 try { checkIndex(index); } catch (Exception e) { e.printStackTrace(); } //如果为0，就是头插 if (index == 0) { addFirst(key); return; } //如果是链表的长度，就是尾插 if (index == size()) { addLast(key); return; } //找到要插入位置的那个节点 ListNode cur = findIndex(index); //简单遍历就行 ListNode node = new ListNode(key); cur.prev.next = node; node.prev = cur.prev; node.next = cur; cur.prev = node; } 5.4 删除值为 key 的节点
实现思路：想要删除，我们必须先遍历一遍链表，使用 cur 从头到尾找一遍。找到后就让当前节点 cur 的前一个节点的后继连上下一个节点，下一个节点的前驱连接前一个节点 cur.prev.next = cur.next 和 cur.next.prev = cur.prev。但是我们还要考虑特殊情况，如要删的是头节点或尾节点，链表只有一个节点或者空链表的情况
//删除第一个值为 key 的节点 public void remove(int key) { ListNode cur = head; while (cur != null) { if (cur.val == key) { //如果是头节点 if (cur == head) { head = head.next; //如果链表仅有一个节点 if (head == null) { //让 last 也变为 null last = null; } else { //让新的头节点的前驱为 null head.prev = null; } } else { //前面的连上后面的 cur.prev.next = cur.next; if (cur.next == null) { //如果是尾节点 last = last.prev; } else { //后面的接上前面的 cur.next.prev = cur.prev; } } //找到一个删除完就 return return; } //一直往后走 cur = cur.next; } } - 在删完节点后，记得及时
return - 关于删头节点和尾节点那部分有点绕，
if - else太多了（如果有大佬能有更简洁的思路，欢迎评论区留言）
5.5 删除所有值为 key 的节点
实现思路：很简单，我们可以直接使用上面的代码，然后把 return 去掉，这样就能遍历完链表上的所有节点，删去所有值为 key 的节点，最后遍历到结尾，就能自然结束方法
//删除所有值为 key 的节点 public void removeAll(int key) { ListNode cur = head; while (cur != null) { if (cur.val == key) { //如果是头节点 if (cur == head) { head = head.next; //如果链表仅有一个节点 if (head == null) { //让 last 也变为 null last = null; } else { //让新的头节点的前驱为 null head.prev = null; } } else { //前面的连上后面的 cur.prev.next = cur.next; if (cur.next == null) { //如果是尾节点 last = last.prev; } else { //后面的接上前面的 cur.next.prev = cur.prev; } } //找到一个删除完就 return //return; } //一直往后走 cur = cur.next; } } 5.6 清空链表
实现思路：跟上面一样，将一个个节点置为 null 也行，一次性 head = last = null 也行
//清空链表（简单版） public void clear1() { head = last = null; } //清空链表（复杂版） public void clear2() { ListNode cur = head; while(cur != null) { ListNOde curN = cur.next; cur.prev = null; cur.next = null; cur = curN; } head = last = null; } 6. LinkedList 常见方法的使用
LinkedList 是采用双向循环链表实现，LinkedList 是 List 接口的另一个实现。除了可以根据索引访问集合元素外，LinkedList 还实现了 Deque 接口，可以当作双端队列来使用，也就是说，既可以当作“栈”使用，又可以当作队列使用
6.1 构造方法
| 方法 | 介绍 |
|---|---|
| LinkedList( ) | 无参构造器 |
| public LinkedList（Collection<? extends E> c） | 一个包含指定集合元素的构造器 |
LinkedList<String> list = new LinkedList<>(); Collection<String> elements = ...; // 已有的集合（必须是E或者E的子类） LinkedList<String> list = new LinkedList<>(elements); //演示1 List<Integer> list = new LinkedList<>(); //平时创建链表的方式 //演示2 List<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(4); List<Integer> list1 = new LinkedList<>(list); System.out.println(list1.toString()); 6.2 常见方法
| 方法 | 介绍 |
|---|---|
| boolean add(E e) | 尾插元素 e |
| void add(int index, E e) | 在位置为 index 上插入 e（注意，头节点位置为 0） |
| void addAll(Collection<? extends E> c) | 尾插一个集合 c 中的所有元素 |
| E get(int index) | 获取下标 index 位置的元素 |
| E set(int index, E element) | 将下标 index 的元素改成 element |
| boolean remove(Object o) | 删除第一个元素 o |
| E remove(int index) | 删除 index 位置的元素 |
| boolean contains(Object o) | 判断 o 是否在线性表中 |
| void clear( ) | 清空链表 |
| int size( ) | 得到链表大小 |
- 关于这些方法知道就好，常用的方法就这么一些，如果忘记了就查查文档，不需要死记硬背
6.3 遍历 LinkedList
直接打印，因为 LinkedList 重写了 toString
List<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); System.out.println(list.toString());for-each 遍历
for (Integer x : list) { System.out.print(x + " "); } System.out.println();迭代器打印
//创建迭代器 ListIterator<Integer> iterator = list.listIterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); } System.out.println();反向迭代器打印
ListIterator<Integer> rit = list.listIterator(list.size()); while (rit.hasPrevious()) { System.out.print(rit.previous() + " "); } System.out.println();
7. ArrayList 和 LinkedList 的区别
| 不同点 | ArrayList | LinkedList |
|---|---|---|
| 底层结构 | 动态数组 | 双向链表 |
| 存储空间 | 逻辑和物理上都连续 | 逻辑上连续，物理上不一定连续 |
| 访问性能 | 支持随机访问：O（1） | 不支持随机访问：O（n） |
| 插入/删除性能 | 需要移动元素，效率低 | 直接改变节点的链接，效率高 |
| 内存机制 | 超出了初始容量需要扩容 | 可以动态扩容 |
| 使用场景 | 频繁随机访问元素 | 大量插入删除元素 |
ArrayList 和 LinkedList 在很多方面都不相同，各有优劣，我们还是要根据实际的应用场景来选择合适的顺序表
结语
今天我们讲了链表中的单向和双向链表，关于它们的方法机制以及方法的使用需要十分熟练地掌握，最后我们还比较了一下 ArrayList 和 LinkedList 的区别，使用哪种还是要具体的使用场景~
希望大家能够喜欢本篇博客，有总结不到位的地方还请多多谅解。若有纰漏，希望大佬们能够在私信或评论区指正，博主会及时改正，共同进步！
