数据结构（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语言中已经有对应的实现。

热门工具换一换