数据结构与算法之双向链表

前言

前文介绍了单向链表，相信大家也了解单向链表是一个怎样的数据结构，除了单向链表，链表还有双向链表。

从名字也可以看出来，双向链表就是不止于从前(头部)向后(尾部)寻址，还可以从后向前寻址，显而易见的是，这样的数据结构，在某些场景，比如从尾部插入，删除等，比单向链表更有效率，相应的，由于每一个结点中存储了两个结点的地址，所以，双向链表比单向链表需要更大的空间，其实，这便是数据结构中空间换时间的思想。

在实际的应用中，并没有绝对最好的数据结构这样的说法， 事实上，根据场景的不同，选择合适的数据结构，合理平衡空间与时间是最有益的。

双向链表

对于链表来说，仍然是理解结点以及结点寻址！

以下代码均由java实现：

/*** @program: thinking-in-all* @description: 双向链表* @author: Lucifinil* @create: -12-30**/public class TwoWayLinkedList<T> {}

Node

对于双向链表的结点，与单向链表的结点相比，其区别就是结点存储两个地址，分别指向前驱和后继。

使用java来实现：

private class Node {T value;Node precursor;Node successor;public Node(T value, Node precursor, Node successor) {this.value = value;this.precursor = precursor;this.successor = successor;}Node(T value) {this(value, null, null);}Node() {this(null, null, null);}@Overridepublic String toString() {return value.toString();}}

属性

从上图的结点，我们很容易能想象到双向链表的样子:

可以看到，有两个特殊结点head和tail，head只存储后继结点地址，而tail只存储前驱结点地址，中间的所有node都存储前驱和后继结点的地址。

同样的，头结点和尾结点我们可以使用虚拟结点来表示，这样做的好处是：避免了在空链表或者只有一个结点时，head和tail的重叠，以及创建和删除结点时的复杂操作。

我们可以看看其区别，没有虚拟头尾结点：

我们可以看到，添加一个第一个结点，第二个结点，以及第三个及以后结点是三种不同的情况，究其原因，便是我们需要对头尾结点进行单独处理，而有虚拟头尾结点：

我们无论添加多少个结点，都是从头尾结点中间添加，不涉及到对头尾结点的操作，唯一的缺点的是多占了两个node的空间，微乎不计…

下面，用代码来实现虚拟头结点和尾结点！

//虚拟头结点private Node dummyHead; //虚拟尾结点结点private Node dummyTail;

如此简单，如此美妙！

除此之外，元素数量是我们必不可少的属性！

//链表元素数量private int size;

构造器

其实，链表本身的构造器很简单，因为链表是真正意义上的动态数据结构，它的创建不需要预先设置一个大小，我们需要给其固有的属性赋予初始值，并且让头尾结点指向彼此形成空链表的初始状态：

public TwoWayLinkedList() {dummyHead = new Node();dummyTail = new Node();dummyHead.successor = dummyTail;dummyTail.precursor = dummyHead;size = 0;}

辅助函数

获取元素数量，判空，是否包含元素等是各个数据结构几乎都有的辅助函数：

获取元素数量：

//获取链表元素数量public int size() {return size;}

判断链表是否为空：

//获取链表是否为空链表public boolean isEmpty() {return size == 0;}

这两个函数很简单，获得元素数量，直接返回size就可以了，我们需要注意的是对size的维护，判断是否为空，只要判断size是否尾0。

是否包含元素e ：

//判断链表中是否包含元素epublic boolean contains(T e) {Node cur = dummyHead.successor;while (cur != null) {if (cur.value.equals(e)) {return true;}cur = cur.successor;}return false;}

这里我们需要注意的是，是否包含元素e这个方法，虽然双向链表相较于单向链表增加了尾结点，但事实上这个方法我们不知道元素e在链表更靠近头部还是尾部，所以，这里我沿用了单向链表的实现，从头部遍历，直到找到该元素或者遍历全部，当然，我们也可以选择从尾部遍历，甚至，两端一起遍历：

public boolean contains(T e) {Node cur1 = dummyHead.successor;Node cur2 = dummyTail.precursor;while (true) {if (cur1.value.equals(e)) {return true;}if (cur2.value.equals(e)){return true;}cur1 = cur1.successor;if (cur1.equals(cur2)){return false;}cur2 = cur2.precursor;}}

增加与删除结点

其实，看到这里，很容易可以想到双向链表的增删结点怎么完成的，无非是在单向链表的基础上，多改变一次结点的指向地址！

增加结点：

从上图可以看到，增加结点，无论是头部还是尾部增加，都是改变新增结点的前驱结点和后继结点的地址指向，只不过与单向链表不同的是，它是改变两个地址，而且它的遍历是可选择的，不再是一定要通过头部来寻址，它也可以通过尾部来寻址。

越靠近头部的便从头部开始遍历，越靠近尾部的便从尾部开始遍历，这样可以保证寻址效率更高：

public void add(int index, T e) {if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed.Illegal index.");}if (index <= size / 2) {Node prev = dummyHead;for (int i = 0; i < index; i++) {//获得新增结点的前驱prev = prev.successor;}//创建新增结点Node node = new Node(e);//获得新增结点的后继Node succ = prev.successor;//为了结构清晰，这里把新增操作的三个结点都表示出来//使新增结点的后继指向succnode.successor = succ;//使新增结点的前驱指向prevnode.precursor = prev;//此刻新增结点已经添加进去了，但是其前驱和后继的地址还有待修正//修正前驱结点，使其后继指向node，而非succprev.successor = node;//修正后继结点，使其前驱指向node，而非prevsucc.precursor = node;} else {Node succ = dummyTail;for (int i = size - 1; i > index; i--) {//同上，只是从尾部开始寻址！succ = succ.precursor;}Node node = new Node(e);Node prev = succ.precursor;node.precursor = prev;node.successor = succ;succ.precursor = node;prev.successor = node;}size++;}

代码中的关键步骤，已经给出说明，这里不再赘述！其实上述代码是可以简化的，数据结构与算法的学习，在前期不太熟悉的时候，写清晰每一步，有助于我们的理解！不过，我们很容易地观察到，除了找到三个相关结点(新增结点，前驱后继)的方式有所差异，后续操作完全相同，优化后的代码为：

public void add(int index, T e) {if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed.Illegal index.");}Node prev;//创建新增结点Node node = new Node(e);Node succ;if (index <= size / 2) {prev = dummyHead;for (int i = 0; i < index; i++) {//获得新增结点的前驱prev = prev.successor;}//获得新增结点的后继succ = prev.successor;} else {succ = dummyTail;for (int i = size; i > index; i--) {//同上，只是从尾部开始寻址！//获得新增结点的后继succ = succ.precursor;}//获得新增结点的前驱prev = succ.precursor;}//为了结构清晰，这里把新增操作的三个结点都表示出来//使新增结点的后继指向succnode.successor = succ;//使新增结点的前驱指向prevnode.precursor = prev;//此刻新增结点已经添加进去了，但是其前驱和后继的地址还有待修正//修正前驱结点，使其后继指向node，而非succprev.successor = node;//修正后继结点，使其前驱指向node，而非prevsucc.precursor = node;size++;}

删除结点：

从图片可以看到，被删除结点，所有与其相关引用全部置空，其前驱与后继建立相互引用！

代码如下：

public T remove(int index){if (isEmpty()) {throw new IllegalArgumentException("Remove failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed.Illegal index.");}if (index <= size / 2) {Node prev = dummyHead;for (int i = 0; i < index; i++) {//获得待删除结点的前驱prev = prev.successor;}//获得待删除结点Node node = prev.successor;//获得待删除结点的后继Node succ = node.successor;//同样的，我们获得删除操作所涉及的三个结点，更加清晰地进行结点的删除操作//将待删除结点的前驱结点的后继指向待删除结点的后继结点//这句话需要好好理解，也就是说前驱结点跳过了待删除结点指向后继结点，在图中可以看到prev.successor = succ;//同样的，将待删除结点的后继结点的前驱指向待删除结点的前驱结点//经过这样两步，这样结点就在链表中被"剔除"了succ.precursor = prev;//由于java的内存是GC管理，但存在引用的对象，是可能继续占用内存的//养成良好的编码习惯，将不适用的对象引用置空node.precursor = null;node.successor = null;size--;return node.value;}else {Node succ = dummyTail;for (int i = size - 1; i > index; i--) {//同理succ = succ.precursor;}Node node = succ.precursor;Node prev = node.precursor;node.precursor = null;node.successor = null;prev.successor = succ;succ.precursor = prev;size--;return node.value;}}

代码中的关键步骤已经用注释说明，这样我们需要注意的是，对于链表中管理索引的步骤，应当小心警惕！

另外，经过观察可以看到，文中有大量重复代码，经过优化后：

public T remove(int index) {if (isEmpty()) {throw new IllegalArgumentException("Remove failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed.Illegal index.");}//我们获得删除操作所涉及的三个结点，更加清晰地进行结点的删除操作Node prev;Node node;Node succ;if (index <= size / 2) {prev = dummyHead;for (int i = 0; i < index; i++) {//获得待删除结点的前驱prev = prev.successor;}//获得待删除结点node = prev.successor;//获得待删除结点的后继succ = node.successor;} else {succ = dummyTail;for (int i = size-1 ; i > index; i--) {//同理succ = succ.precursor;}node = succ.precursor;prev = node.precursor;}//将待删除结点的前驱结点的后继指向待删除结点的后继结点//这句话需要好好理解，也就是说前驱结点跳过了待删除结点指向后继结点，在图中可以看到prev.successor = succ;//同样的，将待删除结点的后继结点的前驱指向待删除结点的前驱结点//经过这样两步，这样结点就在链表中被"剔除"了succ.precursor = prev;//由于java的内存是GC管理，但存在引用的对象，是可能继续占用内存的//养成良好的编码习惯，将不适用的对象引用置空node.precursor = null;node.successor = null;size--;return node.value;}

代码的优化，说明了一个关键点，从图中我们也能观察到这个结论，那就是删除结点，除了遍历方式不同，删除结点的方式，修正前驱后继结点引用的方式都是相同的！

查改元素

到了这样，我觉得小伙伴们想到修改与查询元素是very easy滴，上图！

从图上，我们可以看到双向链表的修改与单向链表几乎是一样的，不同的只是双向链表寻址的方式可以从尾部开始遍历，结合上文的增删结点，我们可以得到查改的代码：

查询：

public T get(int index ){if (isEmpty()) {throw new IllegalArgumentException("Get failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Get failed.Illegal index.");}Node cur;if (index <= size / 2) {cur = dummyHead.successor;for (int i = 0; i < index; i++) {cur = cur.successor;}} else {cur = dummyTail.precursor;for (int i = size-1; i >index ; i--) {cur = cur.precursor;}}return cur.value;}

修改：

public void set(int index, T e) {if (isEmpty()) {throw new IllegalArgumentException("Set failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Set failed.Illegal index.");}Node cur;if (index <= size / 2) {cur = dummyHead.successor;for (int i = 0; i < index; i++) {cur = cur.successor;}} else {cur = dummyTail.precursor;for (int i = size-1; i >index ; i--) {cur = cur.precursor;}}cur.value = e;}

头尾操作

既然双向链表头部和尾部的操作效率都是O(1),我们可以利用其特性，复用上文实现的函数，实现对头尾的crud操作：

头部操作：

public void addFirst(T e){add(0,e);}public T removeFirst(){return remove(0);}public T getFirst(){return get(0);}public void setFirst(T e){set(0,e);}

尾部操作：

public void addLast(T e) {add(size , e);}public T removeLast() {return remove(size-1);}public T getLast() {return get(size-1 );}public void setLast(T e) {set(size-1 , e);}

因为添加操作是在index所在位置添加，在尾部添加其实是对一个不存在的元素进行添加，该位置是index等于size的地方！

我相信，小伙伴们对这种头部和尾部的操作一定不会陌生！因为栈，队列等结构便是涉及头部尾部的操作！

我们可以使用双向链表封装自己的栈和队列等！

完整代码

以下代码已经经过测试，小伙伴们放心食用，不要忘了点赞哟！–来自帅帅的路西菲尔：）

package com.lucifer.linkedlist;/*** @program: thinking-in-all* @description: 双向链表* @author: Lucifinil* @create: -12-30**/public class TwoWayLinkedList<T> {private class Node {T value;Node precursor;Node successor;Node(T value, Node precursor, Node successor) {this.value = value;this.precursor = precursor;this.successor = successor;}Node(T value) {this(value, null, null);}Node() {this(null, null, null);}@Overridepublic String toString() {return value.toString();}}//虚拟头结点private Node dummyHead;//虚拟尾结点结点private Node dummyTail;//链表元素数量private int size;public TwoWayLinkedList() {dummyHead = new Node();dummyTail = new Node();dummyHead.successor = dummyTail;dummyTail.precursor = dummyHead;size = 0;}//获取链表元素数量public int size() {return size;}//获取链表是否为空链表public boolean isEmpty() {return size == 0;}public boolean contains(T e) {Node cur1 = dummyHead.successor;Node cur2 = dummyTail.precursor;while (true) {if (cur1.value.equals(e)) {return true;}if (cur2.value.equals(e)) {return true;}cur1 = cur1.successor;if (cur1.equals(cur2)) {return false;}cur2 = cur2.precursor;}}public void add(int index, T e) {if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed.Illegal index.");}Node prev;//创建新增结点Node node = new Node(e);Node succ;if (index <= size / 2) {prev = dummyHead;for (int i = 0; i < index; i++) {//获得新增结点的前驱prev = prev.successor;}//获得新增结点的后继succ = prev.successor;} else {succ = dummyTail;for (int i = size; i > index; i--) {//同上，只是从尾部开始寻址！//获得新增结点的后继succ = succ.precursor;}//获得新增结点的前驱prev = succ.precursor;}//为了结构清晰，这里把新增操作的三个结点都表示出来//使新增结点的后继指向succnode.successor = succ;//使新增结点的前驱指向prevnode.precursor = prev;//此刻新增结点已经添加进去了，但是其前驱和后继的地址还有待修正//修正前驱结点，使其后继指向node，而非succprev.successor = node;//修正后继结点，使其前驱指向node，而非prevsucc.precursor = node;size++;}public T remove(int index) {if (isEmpty()) {throw new IllegalArgumentException("Remove failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed.Illegal index.");}//我们获得删除操作所涉及的三个结点，更加清晰地进行结点的删除操作Node prev;Node node;Node succ;if (index <= size / 2) {prev = dummyHead;for (int i = 0; i < index; i++) {//获得待删除结点的前驱prev = prev.successor;}//获得待删除结点node = prev.successor;//获得待删除结点的后继succ = node.successor;} else {succ = dummyTail;for (int i = size-1 ; i > index; i--) {//同理succ = succ.precursor;}node = succ.precursor;prev = node.precursor;}//将待删除结点的前驱结点的后继指向待删除结点的后继结点//这句话需要好好理解，也就是说前驱结点跳过了待删除结点指向后继结点，在图中可以看到prev.successor = succ;//同样的，将待删除结点的后继结点的前驱指向待删除结点的前驱结点//经过这样两步，这样结点就在链表中被"剔除"了succ.precursor = prev;//由于java的内存是GC管理，但存在引用的对象，是可能继续占用内存的//养成良好的编码习惯，将不适用的对象引用置空node.precursor = null;node.successor = null;size--;return node.value;}public void set(int index, T e) {if (isEmpty()) {throw new IllegalArgumentException("Set failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Set failed.Illegal index.");}Node cur;if (index <= size / 2) {cur = dummyHead.successor;for (int i = 0; i < index; i++) {cur = cur.successor;}} else {cur = dummyTail.precursor;for (int i = size - 1 ; i > index; i--) {cur = cur.precursor;}}cur.value = e;}public T get(int index) {if (isEmpty()) {throw new IllegalArgumentException("Get failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Get failed.Illegal index.");}Node cur;if (index <= size / 2) {cur = dummyHead.successor;for (int i = 0; i < index; i++) {cur = cur.successor;}} else {cur = dummyTail.precursor;for (int i = size - 1; i > index; i--) {cur = cur.precursor;}}return cur.value;}public void addFirst(T e) {add(0, e);}public T removeFirst() {return remove(0);}public T getFirst() {return get(0);}public void setFirst(T e) {set(0, e);}public void addLast(T e) {add(size, e);}public T removeLast() {return remove(size - 1);}public T getLast() {return get(size - 1);}public void setLast(T e) {set(size - 1, e);}@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append("head [ ");Node cur = dummyHead.successor;for (int i = 0; i < size; i++) {res.append(cur.toString()).append(" <-> ");cur = cur.successor;}res.append("tail ]");return res.toString();}}

总结

链表的形式多种多样，不止于此，除了这样的双向链表，还有单向环链表，双向环链表等等。

除了前文提到的使用循环遍历来寻址，链表和树这样的动态结构，是具有递归性质的，我们可以使用递归来实现。

其实，就算是基础的数据结构，我们在剖析与实现的过程中，也会学习到一些思想，对于双向链表来说，以空间换时间就是对于单向链表效率的进一步提升，当然，除了这样的思路，数据结构和算法，还有许许多多的方法和技巧，我觉得这就是数据结构与算法 的魅力所在。

最后，今天是的最后一天，希望我与小伙伴们以及我爱的人们都能身体健康，万事如意！也期待未来的一年能得到更好的发展，能将学习作为自己的事业坚持下去！

我是帅气的路西菲尔，期待与你一同成长：）

如有不正，敬请指出，原文来自路西菲尔/csdn_1364491554/article/details/103768706！