JavaScript實現雙向鏈表的方法

小編給大家分享一下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實現雙向鏈表的方法有了一定的了解，想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！