首頁 > 文章 > web前端 > JavaScript實作雙向鍊錶（程式碼範例）

JavaScript實作雙向鍊錶（程式碼範例）

藏色散人原創: 2019-04-12 10:50:031965瀏覽

在本篇文章中，我們將介紹如何在JavaScript中實現雙向鍊錶，希望對需要的朋友有所幫助！

什麼是雙向鍊錶?

在雙向鍊錶中，每個節點都有對前一個節點和下一個節點的引用。上一個和下一個的開始和結束節點應該指向null。

JavaScript實作雙向鍊錶（程式碼範例）

雙向鍊錶的實作

我們使用的是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實作雙向鍊錶（程式碼範例）

相關文章