JavaScript实现双向链表（代码示例）

什么是双向链表?

在双向链表中，每个节点都有对前一个节点和下一个节点的引用。上一个和下一个的开始和结束节点应该指向null。

双向链表的实现

我们使用的是es6类，在下面的代码中，我们创建了一个辅助类Node，其中包含三个属性data，prev，next。

class Node {

  constructor(data){
    this.data = data; // data
    this.prev = null; // 引用prev节点
    this.next = null; // 引用next节点
  }}

data:我们需要添加到节点中的数据。

prev:引用前面的节点。

next:引用下一个节点。

主算法开始

class DoublyLinkedList{

   constructor(){
        this.head = null;
        this.tail = null;
        this.length = null;
  }}

在上面的代码中，我们创建了一个具有head、tail和length三个属性的DoublyLinkedList类。

head:它是列表中的第一个节点。

tail:列表中的最后一个节点。

length:列表中有多少节点?

让我们将这些功能添加到我们的双向链表中

Push方法

Push方法帮助我们在链表的末尾添加新节点。

push(data){

    const node = new Node(data);

    if(!this.head){
      this.head = node;
      this.tail = node;
    }else{
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;

    }

    this.length++;
  }

1.在上面的代码中，我们首先声明一个新变量并调用节点构造函数。

2.如果没有this.head那么this.head和this.tail将成为我们在步骤1中创建的新节点。

3.如果已经有节点

new node.prev属性应该是this.tail

this.tail.next应该是一个新节点

更新tail。

4.将长度增加1。

pop方法

帮助我们从列表中删除最后一个节点。

在双向链表中，很容易从列表中删除最后一个节点，因为在tail属性中有对前一个节点的引用。

pop(){

    if(!this.head) return null

    // tail是最后一个节点，因此我们从tail中提取prev属性
    const prevNode = this.tail.prev    
    if(prevNode){
       prevNode.next = null;
       this.tail = prevNode; // 更新tail
    }else{
      // 如果prev属性为null，则表示只有一个节点
      this.head = null;
      this.tail = null;
    }
     this.length--; 
  }

1.在上面的代码中，我们首先声明了一个新变量并存储了tail的前一个属性。

2.如果找到前一个节点。

删除最后一个节点

更新tail。

3.如果前一个节点为空，则表示只有一个节点

this.head和this.tail应为null。

4.将长度减少1。

insertBeginning

insertBeginning方法帮助我们在列表的开头插入新节点。

insertBeginning(data){

    // 创建新节点
    const node = new Node(data);

    // 如果没有节点
    if(!this.head) {
      this.head = node;
      this.tail = node;
    }else{
      this.head.prev = node
      node.next = this.head;
      this.head = node;
    }
    // 增加长度
    this.length++;

  }

removeFirst方法

removeFirst方法帮助我们从链表中删除第一个节点。

removeFirst(){

    if(!this.head) return null

    // 存储第二个节点
    const node = this.head.next;

    if(node){
     // 删除前一个节点
      node.prev = null
     // 更新head
      this.head = node    
      }else{
      // 只有一个节点，所以我们将head和tail更新为null
      this.head = null
      this.tail = null
    }
     this.length--;

  }