【数据结构与算法】4.自主实现单链表的增删查改

📚博客主页：爱敲代码的小杨.

✨专栏：《Java SE语法》

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️

🙏小杨水平有限，欢迎各位大佬指点，相互学习进步！

1. 前言

在上一篇《顺序表》中，我们已经熟悉了 ArrayList 的使用并且进行了简单的模拟实现。ArrayList底层使用数组来存储元素，由于其底层是一段连续的空间，当ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后移动，时间复杂度为O(n)，效率比较低，因此ArrayList 不适合做任意位置插入和删除比较多的场景。因此：Java集合这种又引入了 LinkedList，即链表结构。

2. 链表

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中引用链接次序实现的。

注意：

1. 从上图可看出，链表结构正在逻辑上是连续的，但是在物理上（内存）不一定连续。
2. 现实中的节点一般都是从堆上申请出来的。
3. 从堆上申请的空间，是按照一定的额策略来分配的，两次申请的空间可能连续，也可能不连续。

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

   

2. 带头或者不带头

   

3. 循环或者非循环

   

   虽然有这么多的链表结构，但是我们重点掌握两种：

   • 无头单向非循环链表：结构简单，一般不会单独用来存放数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
   • 无头双向链表：在Java的集合类中LinkedList底层实现就是无头双向循环链表

3. 单链表的实现

创建一个链表

public class MySingleList {// 节点static class ListNode {public int val; // 数值域 - 存放当前节点的值public ListNode next; // next域 指向下一个节点public ListNode(int val) {this.val = val;}}// 链表的属性 链表的头节点public ListNode head; // nullpublic void createList() {ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);node1.next = node2;node2.next = node3;node3.next = node4;this.head = node1;}
}

画图表示：

3.1 打印链表

1. 怎么从第一个节点走到第二个节点？

   答：head = head.next

2. 什么时候算是把节点都遍历完成？

   答： head == null

代码实现：

	/**** 打印链表*/@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;// 让cur这个节点 可以从一个节点走到下一个节点}System.out.println();}

3.2 头插法

在链表的第一个位置插入元素。

思路：

1. 插入元素的next指向head
2. head指向插入元素

代码实现：

    /*** 头插法* @param data*/@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data); // 定义一个节点node.next = head;head = node;}

3.3 尾插法

在链表的最后个位置插入元素

思路：

1. 判断链表中是否有元素。
2. 如果没有元素，直接添加头结点即可。
3. 如果有元素，将原链表最后一个元素next指向插入的元素。

代码实现：

	/*** 尾插法* @param data*/@Overridepublic void addLast(int data) {ListNode node = new ListNode(data); // 定义一个节点if (head == null) { // 链表一个元素都没有head = node;} else {ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}}

3.4 任意位置插入元素

思路：

1. 判断index是否合法（index < 0 或者 index 大于链表长度），如果不合法则抛出异常。
2. 判断index 等于0或者index等于链表长度，则使用头插法或尾插法
3. cur找到index - 1位置
4. 插入元素的next指向cur的next
5. cur的next指向插入的元素

代码实现：

    /*** 在index位置 插入data* @param index* @param data*/@Overridepublic void addIndex(int index, int data) throws IndexException{if (index < 0 || index > size()) {throw new IndexException("index不合法：" + index);}ListNode node = new ListNode(data); // 定义一个节点if (head == null) {head = node;return;}if (index == 0) {addFirst(data);return;}if (index == size()) {addLast(data);return;}ListNode cur = searchPrevIndex(index);node.next = cur.next;cur.next = node;}/*** 找到index-1的位置* @param index* @return*/private ListNode searchPrevIndex(int index) {ListNode cur = head;int count = 0;while (count != index - 1) {cur = cur.next;count++;}return cur;}

异常类：

public class IndexException extends RuntimeException{public IndexException() {}public IndexException(String msg) {super(msg);}
}

3.5 查找元素

代码实现：

    /**** 求当前链表 是否存在key* @param key* @return*/@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}

3.6 链表节点个数

代码实现：

	/*** 求当前链表 有多少个节点* @return*/@Overridepublic int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}

3.7 删除元素

思路：

1. 判断链表是否为空，如果为空直接返回
2. 判断删除元素是否为头节点，如果是则head指向head的next
3. 定义指针找到要删除节点的前一个节点
4. 前一个节点的next指向删除节点的next

代码实现：

    /**** @param key*/@Overridepublic void remove(int key) {if (head == null) {return;}if (head.val == key) {head = head.next;return;}ListNode cur = findPrevKey(key);if (cur == null) {return;// 链表里要没有删除的数字}ListNode del = cur.next;cur.next = del.next;}/*** 找到删除节点的前一个节点* @param key* @return*/private ListNode findPrevKey(int key) {ListNode cur = head;while (cur.next != null) {if (cur.next.val == key) {return cur;} else {cur = cur.next;}}return null;}

3.8 删除链表中指定的所有元素

思路:

1. 判断链表是否为空，如果是空直接返回
2. 定义指针cur：可能要删除的节点
3. 定义指针prev：可能要删除的节点的前驱
4. 判断cur的val是不是要删除的元素，如果是prev的next指向cur的next，cur指向cur的next；否则prev指向cur，cur指向cur的next
5. 判断头节点的val是否为的元素，如果是头节点指向头节点的neext

代码实现：

    /*** 删除链表中所有的key* @param key*/@Overridepublic void removeAllKey(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;}}if (head.val == key) {head = head.next;}}

3.9 清空链表

当一个对象，没有被引用的时候，就会被回收掉

    /*** 清空链表*/@Overridepublic void clear() {head = null;}

4. 代码

代码链接🔗