前言

上文中简略介绍了数据结构-应用JS实现链表-单链表;本篇作为一个续集呈现.通过实现双向链表进一步加深对于链表的一些概念与实现。

coding局部采取javascript进行实现。残缺代码在开端链接

链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，别离指向间接后继和间接前驱。所以，从双向链表中的任意一个结点开始，都能够很不便地拜访它的前驱结点和后继结点。个别咱们都结构双向循环链表。【百度百科】

链表特点

• 用一组任意的内存空间去存储数据元素（这里的内存空间能够是间断的，也能够是不间断的）
• 每个节点(node)都由数据自身,一个指向上一个节点,一个指向后续节点的指针组成
• 整个链表的存取必须从头指针开始，头指针指向第一个节点。尾指针完结,尾指针指向最初一个节点。

JS中并没有指针，上述节点的指针只是借用的C语言中的概念。

链表复杂度

工夫复杂度

空间复杂度

O(n)

根底操作实现

节点构造

//  与单链表区别在于多了之前节点的指向class DoublyLinkedListNode {  constructor(value, next = null, previous = null) {    this.value = value;    this.next = next;    this.previous = previous;  }}

链表初始化

class DoublyLinkedList {  constructor() {    this.head = null;     this.tail = null; //多了尾部  }}

Add 插入 (头部和尾部)

// 增加致头部prepend(value) {    // 节点增加至头部    const newNode = new DoublyLinkedListNode(value, this.head);    // 如果有头部节点,那么设置为头部节点先前(previous)节点的援用    // 将头部节点设置为新节点    if (this.head) {      this.head.previous = newNode;    }    this.head = newNode;    // 如果没有尾部节点,把新节点设置为尾部节点.    if (!this.tail) {      this.tail = newNode;    }    return this;}// 增加致尾部append(value) {    const newNode = new DoublyLinkedListNode(value);    // 同样判断 如果没有头部节点,那么将新节点设置为头部节点。    // 同时也是尾部节点    if (!this.head) {      this.head = newNode;      this.tail = newNode;      return this;    }    // 如果存在头部节点(当然也存在尾部节点)    // 将头部节点增加至链表的尾部    this.tail.next = newNode;    // 转换思考一下,以后新节点上一个个节点(previous)也就是以后this指向的尾部    newNode.previous = this.tail;    // 将新节点设置为链表的尾部    this.tail = newNode;    return this;}

删除

为了浏览体验,此处局部非关键代码省略,能够去仓库进行查看。前面会贴链接。

delete(value) {    if (!this.head) {      return null;    }    let deletedNode = null;    let currentNode = this.head;while (currentNode) {  if (currentNode.value === value) { // 仓库引入了一个比对js.逻辑很简略    deletedNode = currentNode;        // 想想其实就是解决3种状况        //1. 如果删除的节点是头部节点 须要做什么操作        //2. 如果删除的节点是尾部节点 须要坐什么操作        //3. 如果不是头部和尾部而是两头节点 须要做什么操作    if (deletedNode === this.head) {     // 如果删除的节点是头部节点     // 那么将头设置到第二个节点，该节点将成为新头     // 设置心头的previous为null      this.head = deletedNode.next;      if (this.head) {        this.head.previous = null;      }      if (deletedNode === this.tail) {        this.tail = null;      }    } else if (deletedNode === this.tail) {     // 如果删除是尾部节点,将tail设置为倒数第二个节点，这将成为新的tail      this.tail = deletedNode.previous;      this.tail.next = null;    } else {      // 如果要删除两头节点      const previousNode = deletedNode.previous;      const nextNode = deletedNode.next;      previousNode.next = nextNode;      nextNode.previous = previousNode;    }  }  currentNode = currentNode.next;}    return deletedNode;}

遍历链表

coding实现局部在删除中有体现,可自行提取。

 // 思路简略来说就是value值比对 while(){     // 正向遍历,如果以后没有顺次找next 直到尾部     // 反之 如果没有顺次previous 直到头部。 }

结语

做个简略总结,双向链表构造简略了解就是一个节点外面 蕴含以后value,上个previous, 下个next。 而后初始化就是一头一尾 head,tail。而后在这个根底构造进行增删改查。
缓缓了解之后,会感觉很简略。

最初不要忘了要在理论场景中多加分割。

其余链接

上述示例代码仓库