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--;    }

相关推荐：《javascript教程》

以上就是JavaScript实现双向链表（代码示例）的详细内容，更多内容请关注技术你好其它相关文章！