数据结构 实现单链表
本节目标：
- 了解链表
- 实现一个简单的单链表
在实现单链表之前，我们先来了解一下链表是个什么东西。
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 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 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; }}感谢您的阅读，如有错误，还请指出！
