2020-02-17

Essay

13 分钟读完 (大约 1876 个字)

双向链表与双向循环链表

在之前的章节当中，我们介绍过了单链表和循环链表相关内容，今天我们就来看看它们的升级版本，也就是所谓的双向链表与双向循环链表

双向链表

在展开双向链表相关内容之前，我们先来了解一下为什么我们需要双向链表呢？我们从一个示例开始介绍，首先我们来思考这样一个问题，比如某个城市的地铁是一个环形的，就类似于我们的循环链表，比如使用下面这样的方式来表示站台与地铁行进的方向

1	A ==> B ==> C ==> D ==> E ==> A

现在我们假设某人从 A 站上车，最后到达了 E 站，但是他发现坐过站了，他其实要去的是 D 站，那么按照我们的循环链表的约定，他要经过的路线是

1	E ==> A ==> B ==> C ==> D

可以发现需要绕很大一圈，在这种情况，双向链表就可以派上用场了

双向链表结点结构

双向链表和普通链表的区别在于，在链表中一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的，一个链向下一个元素，另一个链向前一个元素，双向链表提供了两种迭代列表的方法，从头到尾，或者反过来从尾到头，在双向链表当中我们也可以访问一个特定节点的下一个或前一个元素，因为如果在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代，这也是双向链表的一个优点

结构如下

typedef struct DualNode {
  ElemType data;
  struct DualNode *prior;  // 前驱结点
  struct DualNode *next;   // 后继结点
} DualNode, *DuLinkList;

可以用下图来进行表示

同理，既然单链表可以有循环链表，那么双向链表当然也可以有

双向链表的插入操作

双向链表的插入方法与单链表相似，但需要设置新节点的 previous 属性，关于插入方式，有两种

尾节点插入，需将其的 previous 指向其前驱，其 next 指向它的前驱的 next，其前驱的 next 指向本身
普通节点的插入，多了一步，需要将其后继的 previous 指向其本身

但是特别需要注意，顺序很重要，千万不能写反了，流程如下图所示

大体的思路如下

s -> next = p;
s -> prior = p -> prior;
p -> prior -> next = s;
p -> prior = s;

这里特别需要注意的，在交换的过程中不要出现矛盾，例如第四步先被执行了，那么 p -> prior 就会提前变成 s，使得插入的工作出错

双向链表的删除操作

从双向链表删除一个元素，分为两证情况，即尾元素和普通元素

尾元素删除，需将其的 previous 指向 null，和其前驱的 next 指向 null
普通元素删除，和单向链表没有什么区别，只需将其前驱的 next 指向它的后继，将其后继的 previous 指向它的前驱，需要注意的一点是需将删除元素的 next、previous 都指向 null

原理如下

大体的思路如下

p -> prior -> next = p -> next;
p -> next -> prior = p -> prior;
free(p);

双向链表相对于单链表来说，是要更复杂一点，每个结点多了一个 prior 指针，所以在使用插入和删除操作的时候需要小心，不过，双向链表可以有效提高算法的时间性能，说白了就是用空间来换取时间，下面我们来看看如何用代码进行实现

代码实现

本质和单链表相似，要实现双向链表，首先需要给 Node 类增加一个 previous 属性

// 节点类
function Node(element) {
  this.element = element   // 当前节点的元素
  this.next = null         // 下一个节点链接
  this.previous = null     // 上一个节点链接
}

针对于 LinkedList 类，我们添加了一个反序的方法

// 链表类
function LList() {
  this.head = new Node('head')      // 头节点
  this.find = find                  // 查找节点
  this.findLast = findLast          // 查找尾节点
  this.insert = insert              // 插入节点
  this.remove = remove              // 删除节点
  this.display = display            // 显示链表
  this.dispReverse = dispReverse    // 反序
}

双向链表的 insert 方法与单链表相似，但需要设置新节点的 previous 属性，使其指向该节点的前驱，定义如下（这里使用的 find() 方法与我们之前的实现是一致的，具体实现可以参考最下方的整合代码）

// 插入节点
function insert(newElement, item) {
  var newNode = new Node(newElement)
  var currNode = this.find(item)
  newNode.next = currNode.next
  newNode.previous = currNode
  currNode.next = newNode
}

双向链表的删除 remove 方法比单链表效率高，不需要查找前驱节点，只要找出待删除节点，然后将该节点的前驱 next 属性指向待删除节点的后继，设置该节点后继 previous 属性，指向待删除节点的前驱即可

// 删除节点
function remove(item) {
  var currNode = this.find(item)
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next
    currNode.next.previous = currNode.previous
    currNode.next = null
    currNode.previous = null
  }
}

至于反序方法，同 display() 方法类似，只不过此次遍历的变成了前驱结点而已，下面是整合后的代码

// 节点
function Node(element) {
  this.element = element  // 当前节点的元素
  this.next = null        // 下一个节点链接
  this.previous = null    // 上一个节点链接
}

// 链表类
function LList() {
  this.head = new Node('head')      // 头节点
  this.find = find                  // 查找节点
  this.findLast = findLast          // 查找尾节点
  this.insert = insert              // 插入节点
  this.remove = remove              // 删除节点
  this.display = display            // 显示链表
  this.dispReverse = dispReverse    // 反序
}

// 查找元素
function find(item) {
  var currNode = this.head
  while (currNode.element != item) {
    currNode = currNode.next
  }
  return currNode
}

// 查找链表中的最后一个元素
function findLast() {
  var currNode = this.head
  while (!(currNode.next == null)) {
    currNode = currNode.next
  }
  return currNode
}

// 插入节点
function insert(newElement, item) {
  var newNode = new Node(newElement)
  var currNode = this.find(item)
  newNode.next = currNode.next
  newNode.previous = currNode
  currNode.next = newNode
}

// 显示链表元素
function display() {
  var currNode = this.head
  while (!(currNode.next == null)) {
    console.log(currNode.next.element)
    currNode = currNode.next
  }
}

// 反向显示链表元素
function dispReverse() {
  var currNode = this.findLast()
  while (!(currNode.previous == null)) {
    console.log(currNode.element)
    currNode = currNode.previous
  }
}

// 删除节点
function remove(item) {
  var currNode = this.find(item)
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next
    currNode.next.previous = currNode.previous
    currNode.next = null
    currNode.previous = null
  }
}

var fruits = new LList()

fruits.insert('111', 'head')
fruits.insert('222', '111')
fruits.insert('333', '222')
fruits.insert('444', '333')

fruits.display()
// 111
// 222
// 333
// 444

fruits.dispReverse()
// 444
// 333
// 222
// 111

至于双向循环链表和单链表相似，节点类型都是一样，唯一的区别是，在创建循环链表的时候，让其头节点的 next 属性执行它本身，即

1	head.next = head

这种行为会导致链表中每个节点的 next 属性都指向链表的头节点，换句话说，也就是链表的尾节点指向了头节点，形成了一个循环链表

# Essay