数据结构（4）：链表的原理和实现
- 2019 年 10 月 4 日
- 筆記
上、简单的单端链表
完整代码向下拉
链表是一种常用的数据结构，在插入和移除操作中有着优秀的表现，同为数据结构的数组哭晕，其实数组的访问效率比链表高多了有木有。
我们先看一下链表的样子
有同学可能要说了，这不就是我们生活中的交通工具——火车，没错链表的结构和下图简直就是一个模子刻出来的。(咳咳，忽略这灵魂的画法)
通过火车示意图可以观察到，火车由火车头和n节车厢组成，每节车厢都与下一节车厢相连，能理解这句话，链表你就掌握一半了。
以小学掌握的物品分类知识来对上图进行面向对象抽象，火车整体可以认为是链表，火车又由车厢组成的，同样可以理解链表是由节点组成的，链表起到了组合节点的作用。
1、创建节点(车厢)
车厢都有哪些特点呢？车厢能存放物品，车厢与下一节车厢相连。
public class Node { public Object data;//存放的数据 public Node next;//指向下一个节点 public Node(Object value) { this.data = value; } //展示节点数据 public void display() { System.out.print(data+" "); } }2、创建链表（将车厢组合）
在现实中我们要想查看整个火车由一个十分暴力的方法，那就是找到火车头，找到火车头后沿着每节车厢向后查找就可以完整的查看整辆火车。
public class LinkList { private Node first;//第一个节点 }在代码中 Node 类已经声明了指向下一个节点的属性，所以只需要找到第一个节点，调用next属性即可无限向后查找。
3、判断链表是否为空
第一个节点为空即为链表为空
public boolean isEmpty() { return first == null; }4、添加数据到链表的头部
添加数据到链表头部，就是将新节点的next指向原来的首节点，再将新节点标记为first即可。
public void addFirst(Object value) { Node newNode = new Node(value);//创建新节点 if (isEmpty()) { first = newNode;//没有节点时直接标记为首节点 } else { newNode.next = first;//新节点next指向旧的首节点 first = newNode; } }5、移除首节点
并非真正意义上的移除，而是将first指向first.next的内存地址，而原来的first会被垃圾回收器回收。
public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first; first = first.next; return tmp; }6、查看链表
由于链表中的每个节点都有变量指向下一个节点，所有可以使用循环递进获取下一个节点实现遍历的效果。
public void display() { Node current = first;//先从首节点开始 while (current != null) { current.display();//节点不为空，则打印该节点信息 current = current.next;//获取当前节点的下个节点重新放入current中 System.out.println(); } }7、根据值查找链表中的节点
需要遍历节点，将每个节点的值都与要查找的值进行比对，如果值不相等就一直循环，直到最后一个节点为空时表示没有查到。
public Node find(Object value) { if (isEmpty()) { return null; } Node current = first; while (current.data != value) { if (current.next==null){ return null; } current = current.next; } return current; }8、根据值移除节点
移除时同样遍历所有节点，但要保存查到节点的之前节点(previous)，如果查到的节点是第一个节点，直接移除第一个，否则就将前一个节点指向要移除节点的下一个。
public Node remove(Object value){ if (isEmpty()) { return null; } Node current = first; Node previous = first; while (current.data != value) { if (current.next==null){ return null; } previous = current; current = current.next; } if (current==first){ removeFirst(); }else{ previous.next=current.next; } return current; }9、完整代码
public class LinkList { private Node first;//第一个节点 public void addFirst(Object value) { Node newNode = new Node(value);//创建新节点 if (isEmpty()) { first = newNode;//没有节点时直接标记为首节点 } else { newNode.next = first;//新节点next指向旧的首节点 first = newNode; } } public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first; first = first.next; return tmp; } public void display() { Node current = first;//先从首节点开始 while (current != null) { current.display();//节点不为空，则打印该节点信息 current = current.next;//获取当前节点的下个节点重新放入current中 System.out.println(); } } public Node find(Object value) { if (isEmpty()) { return null; } Node current = first; while (current.data != value) { if (current.next==null){ return null; } current = current.next; } return current; } public Node remove(Object value){ if (isEmpty()) { return null; } Node current = first; Node previous = first; while (current.data != value) { if (current.next==null){ return null; } previous = current; current = current.next; } if (current==first){ removeFirst(); }else{ previous.next=current.next; } return current; } public boolean isEmpty() { return first == null; } public static void main(String[] args) { LinkList linkList = new LinkList(); linkList.addFirst("a"); linkList.addFirst("b"); System.out.println("-0---"); linkList.remove("a"); linkList.display(); } public class Node { public Object data;//存放的数据 public Node next;//指向下一个节点 public Node(Object value) { this.data = value; } //展示节点数据 public void display() { System.out.print(data+" "); } } }单端链表还是有一些不足，比如我们要操作最后一个节点需要遍历整个链表，下一节咱们实现双端链表，提高操作最后一个节点的效率。
中、操作更简单的双端链表
上节文章中咱们了解了链表的结构及原理，但是还有些美中不足的地方，就是无法快速的访问链表中的最后一个节点。
在这节文章中咱们来解决这个问题，一起来吧。
首先先看如何快速访问尾节点，其实这个可以通过一个变量指向尾节点，在做插入、删除时更新尾节点即可。
1、创建节点
节点用于存储数据和下一个节点相连
public class Node { public Object data;//存放的数据 public Node next;//指向下一个节点 public Node(Object value) { this.data = value; } //展示节点数据 public void display() { System.out.print(data + " "); } }2、创建链表
操作节点和指向首尾两个节点
public class DoubleEndLinkList { private Node first;//第一个节点 private Node last;//最后一个节点 }3、向前添加节点
如果加入的节点是第一个节点，这个节点是首节点同时也是尾节点。如果已经有节点则让新节点指向原来的首节点，让首节点指向新节点。
public void addFirst(Object value) { Node newNode = new Node(value); if (isEmpty()) { //如果为空，尾节点指向此节点 last = newNode; } //更替新节点 newNode.next = first; first = newNode; }4、向后添加节点
和向前添加相反，因为链表中last始终指向最后一个节点，所以操作last节点。
public void addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) { //如果为空，首节点和尾节点指向此节点 first = newNode; last = newNode; return; } //更替尾节点 last.next = newNode; last = newNode; }5、移除首节点
移除首节点时将首节点的下一个节点标记为首节点即可，直到首节点与尾节点相同时(这时也意味这只剩一个节点)不再需要轮替，直接将首尾节点设置为null。
public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first; //仅剩一个节点时 if (first == last) { first = null; last = null; return tmp; } //无论有多少个节点都会轮替到first==last first = first.next; return tmp; }6、完整代码
package com.jikedaquan.datastruct; public class DoubleEndLinkList { private Node first;//第一个节点 private Node last;//最后一个节点 public void addFirst(Object value) { Node newNode = new Node(value); if (isEmpty()) { //如果为空，尾节点指向此节点 last = newNode; } //更替新节点 newNode.next = first; first = newNode; } public void addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) { //如果为空，首节点和尾节点指向此节点 first = newNode; last = newNode; return; } //更替尾节点 last.next = newNode; last = newNode; } public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first; //仅剩一个节点时 if (first == last) { first = null; last = null; return tmp; } //无论有多少个节点都会轮替到first==last first = first.next; return tmp; } public void display() { Node current = first;//先从首节点开始 while (current != null) { current.display();//节点不为空，则打印该节点信息 current = current.next;//获取当前节点的下个节点重新放入current中 System.out.println(); } } public boolean isEmpty() { return first == null; } public static void main(String[] args) { DoubleEndLinkList linkList = new DoubleEndLinkList(); linkList.addLast("e"); linkList.addFirst("a"); linkList.addFirst("b"); linkList.removeFirst(); linkList.removeFirst(); linkList.removeFirst(); linkList.display(); System.out.println("-0---"); linkList.addLast("c"); linkList.addFirst("1"); linkList.display(); System.out.println("-0---"); linkList.removeFirst(); linkList.removeFirst(); linkList.addLast(9); linkList.display(); System.out.println("-0---"); linkList.display(); } public class Node { public Object data;//存放的数据 public Node next;//指向下一个节点 public Node(Object value) { this.data = value; } //展示节点数据 public void display() { System.out.print(data + " "); } } }双端链表能同时向首尾添加新元素，用双端链表实现队列也成为了可能(比用数组实现效率更高)，但是如何快速移除最后一个元素(因为不能快速的追溯之前的元素)成为了一个新难题，请看下一节 双向链表！
下、方便高效的双向链表
单向链表每个节点指向下一个节点，而双向链表是指每个节点还指向了前一个节点。这样做的好处是可以快速的移除最后一个元素。
1、保存数据的节点
节点除了指向下一个节点还要指向前一个节点
public class Node { public Object data;//存放的数据 public Node previous;//指向前一个节点 public Node next;//指向下一个节点 public Node(Object value) { this.data = value; } //展示节点数据 public void display() { System.out.print(data + " "); } }2、创建链表指向首元素和尾元素
public class TwoWayLinkList { private Node first; private Node last; }3、向前添加元素
考虑到链表为空时，首元素和尾元素均指向新元素。
public void addFirst(Object value) { Node newNode = new Node(value); if (isEmpty()) { last = newNode; first = newNode; return; } //新首元素指向旧首元素 newNode.next = first; //旧首元素的前一个指向新首元素 first.previous = newNode; //更替首元素 first = newNode; }4、向后添加元素
由于是双向的，所以之前的引用和之后的引用都要更新
public void addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) { first = newNode; last = newNode; return; } //更替尾元素 newNode.previous = last; last.next = newNode; last = newNode; }5、移除首元素
如果过已是最后一个元素，直接将首尾设置为null，其他情况进行轮替。
public Node removeFirst() { Node removeNode = first; //如果当前已是最后一个元素 if (first.next == null) { first = null; last = null; return removeNode; } //首元素指向下一个元素 first = first.next; //将新首元素指向的之前的元素设为null first.previous = null; return removeNode; }6、移除尾元素
和移除首元素类似
public Node removeLast() { Node removeNode = last; if (last.previous == null) { first = null; last = null; return null; } //尾元素指向旧尾元素之前的元素 last = last.previous; //将新尾元素的下一个元素设为null last.next = null; return removeNode; }7、根据值移除节点
从第一个元素开始遍历，如果值不相同就一直遍历，没有元素匹配返回null，有元素相同时将之前的元素指向当前元素的下一个，将当前元素下一个指向前一个。
public Node remove(Object value) { if (isEmpty()){ return null; } Node current = first; while (current.data != value) { if (current.next == null) { return null; } current = current.next; } current.previous.next = current.next; current.next.previous = current.previous; return current; }8、完整代码
package com.jikedaquan.datastruct; public class TwoWayLinkList { private Node first; private Node last; public void addFirst(Object value) { Node newNode = new Node(value); if (isEmpty()) { last = newNode; first = newNode; return; } //新首元素指向旧首元素 newNode.next = first; //旧首元素的前一个指向新首元素 first.previous = newNode; //更替首元素 first = newNode; } public void addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) { first = newNode; last = newNode; return; } //更替尾元素 newNode.previous = last; last.next = newNode; last = newNode; } public Node removeFirst() { Node removeNode = first; //如果当前已是最后一个元素 if (first.next == null) { first = null; last = null; return removeNode; } //首元素指向下一个元素 first = first.next; //将新首元素指向的之前的元素设为null first.previous = null; return removeNode; } public Node removeLast() { Node removeNode = last; if (last.previous == null) { first = null; last = null; return null; } //尾元素指向旧尾元素之前的元素 last = last.previous; //将新尾元素的下一个元素设为null last.next = null; return removeNode; } public Node remove(Object value) { if (isEmpty()){ return null; } Node current = first; while (current.data != value) { if (current.next == null) { return null; } current = current.next; } current.previous.next = current.next; current.next.previous = current.previous; return current; } public boolean isEmpty() { return first == null; } public void display() { Node current = first;//先从首节点开始 while (current != null) { current.display();//节点不为空，则打印该节点信息 current = current.next;//获取当前节点的下个节点重新放入current中 } System.out.println(); } public static void main(String[] args) { TwoWayLinkList linkList = new TwoWayLinkList(); linkList.addFirst("b"); linkList.addFirst("a"); linkList.display(); System.out.println("======"); while (!linkList.isEmpty()) { linkList.removeFirst(); linkList.display(); } System.out.println("======"); linkList.addLast("c"); linkList.addLast("d"); linkList.display(); System.out.println("======"); while (!linkList.isEmpty()) { linkList.removeLast(); linkList.display(); } System.out.println("======"); linkList.addFirst("e"); linkList.addLast("f"); linkList.addLast("g"); linkList.display(); System.out.println("======"); linkList.remove("f"); System.out.println("======"); linkList.display(); } public class Node { public Object data;//存放的数据 public Node previous;//指向前一个节点 public Node next;//指向下一个节点 public Node(Object value) { this.data = value; } //展示节点数据 public void display() { System.out.print(data + " "); } } } 9、总结
链表是节点中通过变量指向前一个节点和下一个节点实现了相连，链表在移除节点、首尾添加节点有着优越的性能，时间复杂度O(1)。数组在做同等操作需要O(n)，但在访问元素上优于链表，空间复杂度也小于链表，应在不同的场景选用不同的结构。
当然这些数据结构也不需要我们去实现的，java语言中已经有对应的实现。
