小編給大家分享一下JavaScript實(shí)現(xiàn)雙向鏈表的方法，希望大家閱讀完這篇文章后大所收獲，下面讓我們一起去探討吧！

花溪網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營維護(hù)。創(chuàng)新互聯(lián)從2013年開始到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

什么是雙向鏈表?

在雙向鏈表中，每個節(jié)點(diǎn)都有對前一個節(jié)點(diǎn)和下一個節(jié)點(diǎn)的引用。上一個和下一個的開始和結(jié)束節(jié)點(diǎn)應(yīng)該指向null。

雙向鏈表的實(shí)現(xiàn)

我們使用的是es6類，在下面的代碼中，我們創(chuàng)建了一個輔助類Node，其中包含三個屬性data，prev，next。

class Node {

  constructor(data){
    this.data = data; // data
    this.prev = null; // 引用prev節(jié)點(diǎn)
    this.next = null; // 引用next節(jié)點(diǎn)
  }}

data:我們需要添加到節(jié)點(diǎn)中的數(shù)據(jù)。

prev:引用前面的節(jié)點(diǎn)。

next:引用下一個節(jié)點(diǎn)。

主算法開始

class DoublyLinkedList{

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

在上面的代碼中，我們創(chuàng)建了一個具有head、tail和length三個屬性的DoublyLinkedList類。

head:它是列表中的第一個節(jié)點(diǎn)。

tail:列表中的最后一個節(jié)點(diǎn)。

length:列表中有多少節(jié)點(diǎn)?

讓我們將這些功能添加到我們的雙向鏈表中

Push方法

Push方法幫助我們在鏈表的末尾添加新節(jié)點(diǎn)。

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.在上面的代碼中，我們首先聲明一個新變量并調(diào)用節(jié)點(diǎn)構(gòu)造函數(shù)。

2.如果沒有this.head那么this.head和this.tail將成為我們在步驟1中創(chuàng)建的新節(jié)點(diǎn)。

3.如果已經(jīng)有節(jié)點(diǎn)

new node.prev屬性應(yīng)該是this.tail

this.tail.next應(yīng)該是一個新節(jié)點(diǎn)

更新tail。

4.將長度增加1。

pop方法

幫助我們從列表中刪除最后一個節(jié)點(diǎn)。

在雙向鏈表中，很容易從列表中刪除最后一個節(jié)點(diǎn)，因?yàn)樵趖ail屬性中有對前一個節(jié)點(diǎn)的引用。

pop(){

    if(!this.head) return null

    // tail是最后一個節(jié)點(diǎn)，因此我們從tail中提取prev屬性
    const prevNode = this.tail.prev    
    if(prevNode){
       prevNode.next = null;
       this.tail = prevNode; // 更新tail
    }else{
      // 如果prev屬性為null，則表示只有一個節(jié)點(diǎn)
      this.head = null;
      this.tail = null;
    }
     this.length--; 
  }

1.在上面的代碼中，我們首先聲明了一個新變量并存儲了tail的前一個屬性。

2.如果找到前一個節(jié)點(diǎn)。

刪除最后一個節(jié)點(diǎn)

更新tail。

3.如果前一個節(jié)點(diǎn)為空，則表示只有一個節(jié)點(diǎn)

this.head和this.tail應(yīng)為null。

4.將長度減少1。

insertBeginning

insertBeginning方法幫助我們在列表的開頭插入新節(jié)點(diǎn)。

insertBeginning(data){

    // 創(chuàng)建新節(jié)點(diǎn)
    const node = new Node(data);

    // 如果沒有節(jié)點(diǎn)
    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方法幫助我們從鏈表中刪除第一個節(jié)點(diǎn)。

removeFirst(){

    if(!this.head) return null

    // 存儲第二個節(jié)點(diǎn)
    const node = this.head.next;

    if(node){
     // 刪除前一個節(jié)點(diǎn)
      node.prev = null
     // 更新head
      this.head = node    
      }else{
      // 只有一個節(jié)點(diǎn)，所以我們將head和tail更新為null
      this.head = null
      this.tail = null
    }
     this.length--;

  }

看完了這篇文章，相信你對JavaScript實(shí)現(xiàn)雙向鏈表的方法有了一定的了解，想了解更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！