数据结构：图解单个链表的各种操作（插入表头、插入表尾、插入任意位置、删除节点、查询节点、查找链表长度、清空链表）
前言：在上一篇文章中，我们认识了线性数据结构中的顺序表，而本篇文章则是介绍线性数据结构中的另一个结构——链表
想要了解顺序表相关操作的知识可以查看这篇文章：
图文详解顺序表的各种操作
一.什么是链表
链表是一种数据结构，它由一系列节点（node）构成，每个节点中包含了数据（data）和指向下一个节点的指针（next）。链表中的节点可以在内存中任何位置，它们通过指针链接在一起，形成一个链式结构。链表相对于数组的优点在于它可以动态地增加、删除节点，而不需要移动大量的数据。链表的缺点是访问元素时需要遍历整个链表，效率较低。
二.链表的实现
链表由不同的节点相互串起来，每个节点由俩个部分组成，一个是数据域，用来放具体是数值内容，另一个是指针域，用来存放下一个节点的地址信息，彼此之间就像是用链条串起来一样，就像下图展示的这样，所以称之为链表。
对于上图这样的结构，我们可以如下定义一个链表，将链表作为一个类，并且在这个类中有一个内部类专门存储每一个节点的数据结构，还有一个头节点单独定义来记录链表的起始位置
public class MyLinkList{ //节点的数据结构 static class ListNode{ public int val; public ListNode next; } //链表的属性 public ListNode head;//记录链表的第一个元素：头节点 }
对一个链表，它应该完成以下这些功能，我们将这些功能抽象出一个接口，然后通过这个接口去实现一个真正的链表
public interface Ilist { //头插 void addFirst(int data); //尾插 void addLast(int data); //指定插入 void addIndex(int index,int data); //查询是否存在 boolean contains(int key); //删除节点 void remove(int key); //删除所有与目标相同的节点 void removeAllKey(int key); //得到链表的长度 int size(); //清空链表 void clear(); //输出链表的所有信息 void display(); }
节点的插入
我们将节点的插入分为三种：
- 头部插入：将节点插入到链表的最前面
- 尾部插入：将节点插入到链表的最后面
- 指定位置插入：将节点插入到链表的中间
头插法
如图，我们准备对于刚才的链表进行插入
我们这里分俩个步骤进行操作：
- 将新节点指向头节点
- 更新头节点的位置
我们更改要添加节点的指针域，让它指向新的节点
在指向完成后，我们新添加的节点就已经是链表的第一个节点了，所以我们要更新头节点的信息，记录新节点才是第一个节点
这样我们就完成了头部插入节点，具体代码实现如下，先生成一个节点，然后按照上面图示的思路进行操作
//头插法 public void addFirst(int data) { ListNode newNode = new ListNode(data); newNode.next = this.head; this.head = newNode; }
尾插法
尾插法是将节点插入到链表的末尾，但是我们是并没有记录末尾节点的位置的，所以如果要使用尾插法的话就需要先找到尾部节点。那我们只需要根据最后一个节点特征进行遍历找到最后一个节点就可以了，而最后一个节点最大的特征就是，它只有数据域内有信息，指针域里面是空。如果链表为空的话，那我们直接在头节点之后添加就可以，整体流程如下：
整体代码实现如下，先判断是否为空链表，为空就直接在头节点之后添加，不为空就遍历找到最后一个节点，然后更改指针域内容，添加新节点
//尾插法 public void addLast(int data) { //当链表为空的时候，直接将节点插入到头节点的位置 ListNode newNode = new ListNode(data); if (head == null) { head = newNode; }else{ ListNode cur = head; while (cur.next != null){ cur = cur.next; } //找到最后一个节点 cur.next = newNode; //newNode.next = null;//默认新节点的指针域为空，所以这里可以不写这一行代码 } }
指定位置插入
在中间位置插入是最麻烦的，原因就在于我们不能立马获取到想要插入位置的信息，我们需要先进行判断，如果输入位置是在最前面，那就可以使用头插，如果是最后就使用尾插。在得知输入位置在链表中间后，我们就需要先找到这个位置前后的节点的信息，如下图，假如我们要插入的位置是第三个位置，那就需要知道第二个位置和第三个位置的信息，当我们找到了后可以分俩布进行操作（顺序不能更改）：
- 先让节点指向后面的节点
- 再让前面的节点指向插入节点
第一步，让插入节点指向后面的节点
第二步，将前面的节点指向插入的节点
我们可以通过代码来实现这段过程，先是进行合法性的判断，然后是针对性的插入
//指定位置添加 public void addIndex(int index, int data) { if(index < 0 || index > size()) { //这里不一定非要抛出自定义异常，大家可以更具喜好自行设置 throw new IndexException("index不合法: "+index); } //如果输入的位置在最前面就进行头插 if (index == 0) addFirst(data); //如果输入的位置在链表最后就进行尾插 if (index == size()) addLast(data); //输入位置在中间，就先找到这个节点的位置 ListNode cur = searchPrevIndex(index); ListNode newNode = new ListNode(data); //这俩步是顺序非常重要 newNode.next = cur.next; cur.next = newNode; } //找到位置对应的节点 private ListNode searchPrevIndex(int index) { ListNode cur = head; int count = 0; while (count != index-2) { cur = cur.next; count++; } return cur; }
节点的删除
对于节点是删除相当于插入简单了很多，我们依旧是分为俩种方式进行删除，一种是只删除第一次出现的节点，另一种是删除全部想要删除的节点。
删除第一次出现的关键字节点
我们依旧是用初始的链表进行举例，假如我们想要删除第三个节点
第一步，我们直接更改要删除节点的前面节点的指针域，让它指向要删除的节点后的节点
第二步，我们将要删除的节点的指针域置为空
这俩步的顺序同样也不能错，因为一旦我们先将要删除的节点的指针域置为空，我们就无法再找到后面的节点了，链表就相当于断开了
我们封装一个函数用来找到要删除节点的前一个节点，然后通过它再删除目标节点
//删除第一个关键字 public void remove(int key) { if (head == null) return; if (head.val == key){ head = head.next; return; } //查找val等于key的节点 ListNode cur = findKey(key); if (cur == null){ System.out.println("查无此元素，无法删除");