数据结构 实现单链表
本节目标：
- 了解链表
- 实现一个简单的单链表
在实现单链表之前，我们先来了解一下链表是个什么东西。
1.链表
链表的概念
链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。像这样：
【注意】
- 从上图可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。
- 图中一个个对象称为节点，现实中节点一般都是从堆上申请出来的。
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能不连续，也可能连续。
链表的结构种类
实际上，链表的结构非常多样，通常有以下三大情况：
1.单向或者双向：
2.带头或者不带头：
3.循环或者非循环
而这三大情况能够组成八种链表结构：
虽然种类很多，但是我们重点掌握两种：
- 不带头单向非循环链表：结构简单，一般不会单独用来储存数据。实际中更多是作为其他数据结构的子结构，如哈希表、图的邻接表等等。不仅如此，这种结构在笔试面试中很常见！
- 不带头双向链表：在Java的集合框架中LinkedList类底层实现的就是不带头双向循环链表。
本节我们就来实现一个简单的不带头单向非循环链表。
2.不带头单向非循环链表的实现
我们实现的不带头单向循环链表和它的一些操作方法如下：
// 1、不带头单向非循环链表实现
public class SingleLinkedList {
//头插法
public void addFirst(int data){
}
//尾插法
public void addLast(int data){
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
}
//查找是否包含数据key
public boolean contains(int key){
return false;
}
//删除第一次出现的数据key的节点方法
public void remove(int key){
}
//删除所有值为key的节点
public void removeAllKey(int key){
}
//得到单链表的长度
public int size(){
return -1;
}
//清空链表
public void clear() {
}
//展示链表，这个方法用于测试的！
public void display() {
}
//给定一个初始链表，用于测试
public void func() {
}
}
在实现这个单链表之前，我们需要先把节点类定义好，可以定义为一个普通类，也可以定义为内部类。这里定义为普通类。
节点类：
public class ListNode {int val; //用于储存节点的数据ListNode next; //用于储存下一个节点的位置public ListNode(int val) {this.val = val;}
}好的，现在有了节点类，就可以开始实现链表了。还是老规矩，从简到繁。
展示链表方法和给定初始链表方法
展示链表方法
要求：将链表中储存的数据全部打印出来。
思路：在链表 SingleLinkedList 中定义一个头节点（带头的链表的头节点是不存储数据的，仅作为一个标志，但是不带头的链表的头节点是可以用来储存数据的），这个头节点作为链表的起点，因为头节点的next字段中存储着下一个节点的地址，所以可以通过这个字段接着访问下一个节点，那么定义一个节点对象，从头节点开始，一个个节点去遍历整个链表，因为最后一个节点的next中储存的是null，因此可以作为遍历终止条件。
public class SingleLinkedList {ListNode head; //定义的头节点int size; //用于记录元素的个数，即节点个数//展示链表，这个方法用于测试的！public void display() {ListNode cur = this.head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next; //向后遍历，一直到最后一个节点}System.out.println();}
}给定初始链表方法
要求：给定一个初始的链表。
思路：创建一个个节点，接着把他们串起来，并且把头节点标记出来。像这样：
//给定初始链表方法public void func() {//创建节点ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);//将节点串起来this.head = node1; //标记头节点head.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;}进行测试：
public class Test {public static void main(String[] args) {SingleLinkedList list = new SingleLinkedList();list.func();list.display();}
}//运行结果
12 23 34 45 56 结果符合预期。
得到单链表长度方法
要求：通过这个方法返回单链表的长度，即单链表包含的元素个数。
思路：进需要将size字段返回即可。
//得到单链表的长度方法public int size() {return this.size;}头插法
要求：在单链表的头节点前插入一个新的节点。
思路：将原头节点的地址赋予新节点所指向的下一个节点next字段，再新节点作为新的头节点，最后size++即可。像这样：
//头插法
public void addFirst(int data) {ListNode cur = new ListNode(data);cur.next = this.head;head = cur;this.size++;}尾插法
要求：在单链表最后一个节点后面插入一个新节点。
思路：先通过遍历链表的方式找到最后一个节点，接着令这个节点所指向的下一个节点更改为新节点的地址，最后size++即可。
//尾插法public void addLast(int data) {ListNode cur = new ListNode(data);ListNode pre = this.head;while (pre.next != null) {pre = pre.next;}pre.next = cur;this.size++;}不过这里我们可能会忽略一个问题：单链表万一一开始是空的，怎么办？当单链表为空时，令新节点为头节点即可。
//尾插法（完善版）public void addLast(int data) {ListNode cur = new ListNode(data);if (this.head == null){this.head = cur;this.size++;return;}else {ListNode pre = this.head;while (pre.next != null) {pre = pre.next;}pre.next = cur;this.size++;}}查找是否包含数据key的方法
要求：查找单链表中是否包含数据key，若包含则返回true，否则返回false。
思路：通过遍历链表，查看是否包含key，包含就返回true，否则返回false。
//查找是否包含数据key的方法public boolean contains(int key) {ListNode cur = this.head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}在任一位置插入的方法(第一个数据节点为0号下标)
要求：在单链表中的任一位置插入一个新节点。
思路：在插入先必须要判断插入位置是否合法，合法了才能插入，而这里的插入可以分为三种情况：1.在链表的前端插入，也就是头插法；2.在链表的后端插入，即尾插法；3.在中间任一位置插入。第1和第2种情况我们已经解决了，考虑第3种情况即可。对于第3种情况，先通过遍历的方式找出要插入新节点的位置的前一个节点（首先，链表不能像顺序表那样直接找到要插入的位置，其次，单链表不能往前走，只能往后走，因此要找的不是插入的位置，而是插入的位置的前一个节点），接着调整节点之间的指向完成插入。
打个比方，现在要在2位置插入一个新节点，那么我们要找到它的前一个节点，即1位置的节点，接着令要插入的新节点的下一节点指向原来2位置的节点，然后1位置的1节点的下一节点指向新节点，最后size++即可。
注意：在任一位置插入的原则是：优先绑定后边，不然会找不到插入位置后面的节点！
对于插入位置的合法性，我们可以写一个方法用于判断是否合法，并且写一个异常类，当位置不合法是弹出异常。
异常类
public class LocationException extends RuntimeException{ public LocationException() {}public LocationException(String str) {super(str);}
}
判断是否合法方法
//判断位置是否合法private void isIllegal(int index) {if (index < 0 || index > this.size) {throw new LocationException("插入位置非法！");}}处理完插入位置是否合法后，就可以实现插入的操作了，前面说过我们要先获取插入位置的前一个节点，因此可以写一个方法实现。
//获取插入位置的前一个节点private ListNode find(int index) {ListNode cur = this.head;int k = 0;while (k < index - 1) {cur = cur.next;k++;}return cur;}这个方法的思路是定义一个指针，从头节点开始走，走 index - 1 步，走完了之后这个指针指向的就是插入位置的前一个节点。
实现插入操作
//在任一位置插入的方法public void addIndex(int index,int data) {try {isIllegal(index);//处理在前端插入if (index == 0) {addFirst(data);return;}//处理在后端插入if (index == this.size) {addLast(data);return;}//处理中间插入ListNode newNode = new ListNode(data);ListNode pre = find(index);newNode.next = pre.next; //cur.next 表示插入位置的原节点pre.next = newNode;this.size++;}catch (LocationException e) {e.printStackTrace();}}删除第一次出现的数据key的节点方法
要求：删除第一次出现数据key的节点。
思路：首先，要确认链表是否为空，如果链表为空就给出提示；不为空的话，再通过遍历链表的方式，查看链表中是否有包含key的节点，若没有就给出提示；有的话，开始进行删除操作。
删除操作：首先分两种情况：1.删除链表前端，即头删；2.删除中间节点及链表后端。第1种情况：令头节点指向原头节点的下一节点，接着size--即可。第2种情况：令包含key的节点的前一个节点指向包含key的节点的下一个节点，再size--即可；
//删除第一次出现的数据key的节点方法public void remove(int key) {//判断链表是否为空if (this.head == null) {System.out.println("链表为空，无法删除");return;}//判断是否有包含key的节点if (judgment(key)) {System.out.println("该链表中没有这个节点");return;}//第1种情况if (this.head.val == key) {this.head = this.head.next;this.size--;return;}//第2种情况ListNode pre = find1(key);pre.next = pre.next.next;this.size--;}//判断是否有包含key的节点的方法private boolean judgment(int key) {ListNode cur = this.head;while (cur != null) {if (cur.val == key) {return false;}cur = cur.next;}return true;}//寻址删除节点的前一个节点的方法private ListNode find1(int key) {ListNode cur = this.head;while (cur.next != null) {if (cur.next.val == key) {return cur;}cur = cur.next;}return cur;}删除所有包含key的节点
要求：将链表中所有包含key的节点都删除。
思路：在开始进行删除操作之前，需要处理链表为空的情况和是否有包含key的节点的情况，然后开始实现删除操作。这里的删除操作可以借助快慢指针的想法。
//删除所有包含key的节点的方法public void removeAllKey(int key) {//判断链表是否为空if (this.head == null) {System.out.println("链表为空，无法删除");return;}//判断是否有包含key的节点if (judgment(key)) {System.out.println("该链表中没有包含" + key + "的节点");return;}ListNode slow = this.head;ListNode fast = this.head.next;while (fast != null) {if (fast.val == key) {fast = fast.next;slow.next = fast;this.size--;}else {slow = fast;fast = fast.next;}}}这个方法还有一个问题没有处理，就是我们是从第2个节点开始判断并删除包含key的节点的，要是头节点也是我们要删除的节点，就会被忽略掉，因此我们需要最后处理一下头节点万一是包含key的节点的问题。
//删除所有包含key的节点的方法public void removeAllKey(int key) {//判断链表是否为空if (this.head == null) {System.out.println("链表为空，无法删除");return;}//判断是否有包含key的节点if (judgment(key)) {System.out.println("该链表中没有包含" + key + "的节点");return;}ListNode slow = this.head;ListNode fast = this.head.next;while (fast != null) {if (fast.val == key) {fast = fast.next;slow.next = fast;this.size--;}else {slow = fast;fast = fast.next;}}//处理头节点是包含key的节点的情况while (this.head != null && this.head.val == key) {this.head = this.head.next;this.size--;}}清空链表
要求：将链表清空。
思路：有两种方式，第一种是直接令头节点为null，size = 0，这种方式简单粗暴。第二种是将节点一个个置为null，这种比较温柔。第一种比较简单，这里举例第二种。
//清空链表public void clear() {ListNode cur = this.head;while (cur != null) {ListNode curN = cur.next;cur.next = null;cur = curN;}this.head = null;this.size = 0;}到这里我们就实现了一个简单的单链表，完整代码如下：
public class SingleLinkedList {ListNode head; //定义的头节点int size; //用于记录元素的个数，即节点个数//展示链表，这个方法用于测试的！public void display() {ListNode cur = this.head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next; //向后遍历，一直到最后一个节点}System.out.println();}//给定初始链表方法public void func() {//创建节点ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);//将节点串起来this.head = node1; //标记头节点head.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;}//得到单链表的长度方法public int size() {return this.size;}//头插法public void addFirst(int data) {ListNode cur = new ListNode(data);cur.next = this.head;head = cur;this.size++;}//尾插法public void addLast(int data) {ListNode cur = new ListNode(data);if (this.head == null){this.head = cur;this.size++;return;}else {ListNode pre = this.head;while (pre.next != null) {pre = pre.next;}pre.next = cur;this.size++;}}//查找是否包含数据key的方法public boolean contains(int key) {ListNode cur = this.head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}//判断位置是否合法private void isIllegal(int index) {if (index < 0 || index > this.size) {throw new LocationException("插入位置非法！");}}//在任一位置插入的方法public void addIndex(int index,int data) {try {isIllegal(index);//处理在前端插入if (index == 0) {addFirst(data);return;}//处理在后端插入if (index == this.size) {addLast(data);return;}//处理中间插入ListNode newNode = new ListNode(data);ListNode pre = find(index);newNode.next = pre.next; //cur.next 表示插入位置的原节点pre.next = newNode;this.size++;}catch (LocationException e) {e.printStackTrace();}}//获取插入位置的前一个节点private ListNode find(int index) {ListNode cur = this.head;int k = 0;while (k < index - 1) {cur = cur.next;k++;}return cur;}//删除第一次出现的数据key的节点方法public void remove(int key) {//判断链表是否为空if (this.head == null) {System.out.println("链表为空，无法删除");return;}//判断是否有包含key的节点if (judgment(key)) {System.out.println("该链表中没有这个节点");return;}//第1种情况if (this.head.val == key) {this.head = this.head.next;this.size--;return;}//第2种情况ListNode pre = find1(key);pre.next = pre.next.next;this.size--;}//判断是否有包含key的节点的方法private boolean judgment(int key) {ListNode cur = this.head;while (cur != null) {if (cur.val == key) {return false;}cur = cur.next;}return true;}//寻址删除节点的前一个节点的方法private ListNode find1(int key) {ListNode cur = this.head;while (cur.next != null) {if (cur.next.val == key) {return cur;}cur = cur.next;}return cur;}//删除所有包含key的节点的方法public void removeAllKey(int key) {//判断链表是否为空if (this.head == null) {System.out.println("链表为空，无法删除");return;}//判断是否有包含key的节点if (judgment(key)) {System.out.println("该链表中没有包含" + key + "的节点");return;}ListNode slow = this.head;ListNode fast = this.head.next;while (fast != null) {if (fast.val == key) {fast = fast.next;slow.next = fast;this.size--;}else {slow = fast;fast = fast.next;}}//处理头节点是包含key的节点的情况while (this.head != null && this.head.val == key) {this.head = this.head.next;this.size--;}}//清空链表public void clear() {ListNode cur = this.head;while (cur != null) {ListNode curN = cur.next;cur.next = null;cur = curN;}this.head = null;this.size = 0;}
}
感谢您的阅读，如有错误，还请指出！