乐趣区

关于前端:数据结构使用JS实现链表双向链表

jiezi

前言

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

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

链表

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

链表特点

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

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

链表复杂度

工夫复杂度

Access Search Insertion Deletion
O(n) O(n) O(1) O(1)

空间复杂度

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。而后在这个根底构造进行增删改查。
缓缓了解之后, 会感觉很简略。

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

其余链接

上述示例代码仓库

退出移动版