05_双向链表 - 《JavaScript数据结构和算法》

基本定义
双向链表常见的方法
在js中实现双向链表

基本定义

在计算机科学中，双向链表又被称为双链表，也属于链表，但是他每个节点都有两个指针，指向他前一个节点和后一个节点。我们学习单向链表的时候会发现，我们只能从前端遍历到尾端或者是尾端遍历到前端，因为单向链表正如其名：单向，所以说我们可以轻松的得到下一个节点，但是想回到上一个节点是很难的。但是双向链表就不一样的，他每个节点不单单保存着他下一个节点，还保存着他上一个节点，对于操作的方便程度是单向链表无法比拟的。当然，它占用的内存也会大一些

双向链表常见的方法

append：向链表后端新增一个节点
insert：在指定位置插入一个节点
get：返回指定位置的节点
indexOf：返回指定节点在链表的索引，找不到则返回-1
update：修改某个位置的节点
removeAt：移除指定位置的节点
remove：移除链表后端的节点
isEmpty：判断链表有没有节点，有则返回true，反之返回false
size：返回链表的节点个数
toString：输出链表的节点，因为实际上我们只需要节点的value，所以需要封装个方法打印出所有的value
forwarrdString：从前端遍历到后端，打印出所有节点的value
backwordString：从后端遍历到前端，打印出所有节点的value
getHead：返回链表前端的节点
getTail：返回链表后端的节点

在js中实现双向链表

前置工作

class Node {
  constructor(data) {
    //当前节点的value
    this.data = data;
    //保存上一个节点信息
    this.prev = null;
    //保存下一个节点信息
    this.next = null;
  }
}
class DoubleList {
  constructor() {
    //头部节点
    this.head = null;
    //尾部节点
    this.tail = null;
    //链表长度
    this.length = 0;
  }
}

先封装个节点类和双向链表类，每一个节点我们都是实例化一个Node类保存到链表的。

以下所有方法都在DoubleList类中实现

实现append方法

  // append方法：在链表后端插入一个节点
  append(data) {
    const node = new Node(data);
    //分情况处理：判断是否是第一个节点
    if (this.length === 0) {
      this.head = node;
      this.tail = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      node.prev = current;
      current.next = node;
      this.tail = node;
    }
    this.length++;
  }

append方法比较简单，只是在处理节点的时候需要考虑到上一个节点的保存，别忘记在新增后需要将length加1

实现 insert方法

  // insert方法：在指定位置插入元素
  insert(position, data) {
    if (position < 0 || position > this.length) return false;
    const node = new Node(data);
    let current = this.head;
    // 先判断插入第一个元素的情况
    if (position == 0) {
      this.head = node;
      node.next = current;
      current.prev = node;
    } else if (position === this.length) {
      //判断插入的是最后一个节点的情况
      while (current.next) {
        current = current.next;
      }
      current.next = node;
      node.prev = current;
      this.tail = node;
    } else {
      //在中间的情况
      let index = 0;
      let prive = null;
      while (index < position) {
        prive = current;
        current = current.next;
        index++;
      }
      prive.next = node;
      node.prev = prive;
      current.prev = node;
      node.next = current;
    }
    this.length++;
    return true;
  }

insert方法就比较麻烦，分的情况也比较多，首先需要考虑插入的是第一个节点的情况，先看图：

05_双向链表 - 图1

我们可以看到默认情况双向链表的结构，head会指向第一个节点，tail会指向最后一个节点，然后每个节点有个next属性指向下一个节点，也有一个prev属性指向上一个节点

05_双向链表 - 图2

我们会发现head指向value为4的节点，然后value为4的节点的next指向value为1的节点，然后节点value为1的节点的prev指向value为4的节点，也就是他上一个节点

当插入最后也是同理，value为3的节点的next属性指向value为4的节点，value为4的节点的prev属性指向value为3的节点，然后继续将tail指向最后一个节点，也就是value为4的节点。

实现get方法

  // get方法：获取指定位置的元素
  get(position) {
    if (this.length / 2 > position) {
      let index = 0;
      let current = this.head;
      while (index < position) {
        current = current.next;
        index++;
      }
      return current.data;
    } else {
      let index = 0;
      let current = this.tail;
      while (index < this.length - position - 1) {
        current = current.prev;
        index++;
      }
      return current.data;
    }
  }

get方法就比较简单，和单向链表相似，值得注意的是，如果我们链表中有大量数据，那么无论什么时候都从头找到尾明显不合适，所以可以判断一下需要找的元素的位置偏向前面还是偏向后面，决定我们从前开始找还是从后开始找，有点类似于二分查找，不过我们只分一次，这也是单向链表做不到的

实现indexOf方法

 // indexOf方法： 返回元素的索引，没有锗元素就返回-1
  indexOf(data) {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.data === data) {
        return index;
      } else {
        current = current.next;
        index++;
      }
    }
    return -1;
  }

实现update方法

  // update方法： 更新方法
  update(position, data) {
    if (position < 0 || position >= this.length) return false;
    let index = 0;
    let current = this.head;
    while (index < position) {
      current = current.next;
      index++;
    }
    current.data = data;
    return true;
  }

实现removeAt方法

 // removeAt方法：移除特定位置的元素
  removeAt(position) {
    if (position < 0 || position >= this.length) return false;
    let index = 0;
    let current = this.head;
    let prive = null;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
      return true;
    }
    //一样先判断在移除第一个节点的情况
    if (position === 0) {
      this.head = current.next;
      current.next.prev = this.head;
    } else if (position === this.length - 1) {
      //判断移除最后一个节点的情况
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    } else {
      //移除中间节点的情况
      while (index < position) {
        prive = current;
        current = current.next;
        index++;
      }
      prive.next = current.next;
      current.next.prev = prive;
      return true;
    }
    this.legnth--;
  }

removeAt方法稍微复杂一点点，大部分情况都是在考虑节点引用的问题，在移除最后一个节点的时候，也要注意移除顺序，如果我们选择现在将tail指向最后一个节点的上一个，那么我们找到倒数第二个节点的时候就找不到了，因为我们拿不到最后一个节点了，所以需要先将最后一个节点的上一个节点的next先置为空，然后在处理tail的指向。

实现remove方法

 // remove方法：移除某个元素
  remove(data) {
    const index = this.indexOf(data);
    return this.removeAt(index);
  }

先调用indexOf方法找到移除元素的索引，然后调用removeAt方法将索引传递进去接口

实现isEmpty方法

  // isEmpty方法： 判断链表是否为空，是则返回true，否则返回false
  isEmpty() {
    return this.legnth > 0 ? true : false;
  }

实现size方法

  // size方法： 返回链表的长度
  size() {
    return this.length;
  }

实现getHead方法

  // getHead方法： 返回列表前端元素
  getHead() {
    return this.head.data;
  }

实现getTail方法

  // getTail方法： 返回列表后端元素
  getTail() {
    return this.tail.data;
  }