JavaScript雙向鍊錶和雙向循環鍊錶的實現-js教程-PHP中文網

首頁

web前端

js教程

JavaScript雙向鍊錶和雙向循環鍊錶的實現

小云云

Dec 07, 2017 pm 03:51 PM

javascript js 實現

雙向鍊錶和普通鍊錶的區別在於，在鍊錶中，一個節點只有鏈向下一個節點的鏈接，而在雙向鍊錶中，鏈接是雙向的：一個鏈向下一個元素，另一個鏈向前一個元素。雙向鍊錶提供了兩種迭代列表的方法：從頭到尾，或者反過來。我們也可以存取一個特定節點的下一個或前一個元素。在單向鍊錶中，如果迭代列表時錯過了要找的元素，就需要回到列表起點，重新開始迭代。這是雙向鍊錶的一個優點。本文主要介紹JavaScript資料結構之雙向鍊錶與雙向循環鍊錶的實作。

雙向鍊錶：單向鍊錶只能向一個方向遍歷鍊錶節點，而在節點指標域中增加了前向指標的雙向鍊錶，則可以向著兩個方向遍歷節點。這使得雙向鍊錶也可以在任何一個節點遍歷整個鍊錶。

function DoublyLinkedList() { 
  var Node = function(element) { 
    this.element = element; 
    this.next = null; 
    this.prev = null; 
  }; 
 
  var length = 0, 
    head = null, 
    tail = null; 
 
  this.append = function(element){ 
    var node = Node(element), 
      current, 
      previous; 
     
    if(!head){ 
      head = node; 
      tail = node; 
    }else{ 
      current = head; 
      while(current){ 
        previous = current; 
        current = current.next; 
      } 
 
      node.next = current; 
      current.prev = node; 
      previous.next = node; 
      node.prev = previous; 
    } 
 
    length++; 
    return true; 
  } 
 
  this.insert = function(position,element){ 
    if(position > -1 && position < length){ 
      var node = new Node(element), 
        current = head, 
        previous, 
        index = 0; 
 
      if(position === 0){ 
 
        if(!head){ 
          head = node; 
          tail = node; 
        }else{ 
          node.next = current; 
          current.prev = node; 
          head = node; 
        } 
 
      }else if (position === length -1){ 
        current = tail; 
        current.next = node; 
        node.prev = current; 
      }else { 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
        node.next = current; 
        previous.next = node; 
        current.prev = node; 
        node.prev = previous; 
      } 
 
      length++; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.removeAt = function(position){ 
    if(position > -1 && position < length){ 
      var current = head, 
        index = 0, 
        previous; 
 
      if (position === 0) { 
        head = current.next; 
 
        if(length === 1){ 
          tail = null; 
        }else{ 
          head.prev = null; 
        } 
      }else if(position === length - 1){ 
        current = tail; 
        tail = current.prev; 
        tail.next = null; 
      } else{ 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        previous.next = current.next; 
        current.next.prev = previous; 
      }; 
      length-- ; 
 
      return current.element; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.remove = function(element){ 
    var current = head, 
      previous; 
 
    if(current.element === element){ 
      head = current.next; 
    } 
    previous = current; 
    current = current.next; 
 
    while(current){ 
      if (current.element = element) { 
        previous.next = current.next; 
        current.next.prev = previous; 
      }else{ 
        previous = current; 
        current = current.next; 
      } 
    } 
    return false; 
  }; 
 
  this.remove = function(){ 
    if (length === 0) { 
      return false; 
    }; 
 
    var current = head, 
      previous; 
 
    if(length === 1){ 
      head = null; 
      tail = null; 
      length--; 
      return current.element; 
    } 
 
    while(current){ 
      previous = current; 
      current = current.next; 
    } 
 
    previous.next = null; 
    length--; 
    return current.element; 
  }; 
 
  this.indexOf = function(element){ 
    var current = head, 
      index = 0; 
 
    while(current && index++ < length){ 
      if (current.element === element) { 
        return index; 
      }; 
      current = current.next; 
    } 
 
    return false; 
  }; 
 
  this.isEmpty = function(){ 
    return length === 0; 
  }; 
 
  this.size = function(){ 
    return length; 
  }; 
 
  this.toString = function(){ 
    var current = head, 
      string = &#39;&#39;; 
 
    while(current){ 
      string += current.element; 
      current = current.next; 
    } 
    return string; 
  }; 
 
  this.getHead = function(){ 
    return head; 
  }; 
 
  this.getTail = function(){ 
    return tail; 
  }; 
}

登入後複製

雙向循環鍊錶：將雙向鍊錶的頭尾指標相連，就構成了雙向循環鍊錶。這種鍊錶從任一節點都可以同時向兩個方向進行節點遍歷，查詢節點的速度也是最快的。

/*双向循环链表*/ 
function DoublyCircularLinkedList(){ 
  var Node = function(element){ 
    this.element = element; 
    this.next = null; 
    this.prev = null; 
  }; 
 
  var length = 0, 
    head = null, 
    tail = null; 
 
  this.append = function(element){ 
    var node = new Node(element), 
      current, 
      previous; 
 
    if (!head) { 
      head = node; 
      tail = node; 
      head.prev = tail; 
      tail.next = head; 
    }else{ 
      current = head; 
 
      while(current.next !== head){ 
        previous = current; 
        current = current.next; 
      } 
 
      current.next = node; 
      node.next = head; 
      node.prev = current; 
    }; 
 
    length++; 
    return true; 
  }; 
 
  this.insert = function(position, element){ 
    if(position >= 0 && position <= length){ 
      var node = new Node(element), 
        index = 0, 
        current = head, 
          previous; 
 
      if(position === 0){ 
         
        if(!head){ 
 
          node.next = node; 
          node.tail = node; 
          head = node; 
          tail = node; 
 
        }else{ 
 
          current.prev = node; 
          node.next = current; 
          head = node; 
          node.prev = tail; 
 
        } 
         
      }else if(position === length){ 
        current = tail; 
 
        current.next = node; 
        node.prev = current; 
        tail = node; 
        node.next = head; 
      }else{ 
 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        current.prev = node; 
        node.next = current; 
        previous.next = node; 
        node.prev = previous; 
 
      } 
 
      length++; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.removeAt = function(position){ 
    if(position > -1 && position < length){ 
 
      var current = head, 
        index = 0, 
        previous; 
 
      if(position === 0){ 
 
        current.next.previous = tail; 
        head = current.next; 
 
      }else if(position === length - 1){ 
 
        current = tail; 
 
        current.prev.next = head; 
        head.prev = current.prev; 
        tail = current.prev; 
      }else{ 
 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        previous.next = current.next; 
        current.next.prev = previous; 
 
      } 
 
      length--; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.remove = function(element){ 
    var current = head, 
      previous, 
      indexCheck = 0; 
 
    while(current && indexCheck < length){ 
      if(current.element === element){ 
        if(indexCheck === 0){ 
          current.next.prev = tail; 
          head = current.next; 
        }else{ 
          current.next.prev = previous; 
          previous.next = current.next; 
        } 
        length--; 
        return true; 
      } 
 
      previous = current; 
      current = current.next; 
      indexCheck++; 
    } 
 
    return false; 
  }; 
 
  this.remove = function(){ 
    if(length === 0){ 
      return false; 
    } 
 
    var current = head, 
      previous, 
      indexCheck = 0; 
 
    if(length === 1){ 
      head = null; 
      tail = null; 
      length--; 
      return current.element; 
    } 
 
    while(indexCheck++ < length){ 
      previous = current; 
      current = current.next; 
    } 
 
    previous.next = head; 
    tail = previous.next; 
    length--; 
    return current.element; 
  }; 
 
  this.indexOf = function(element){ 
    var current = head, 
      index = 0; 
 
    while(current && index++ < length){ 
      if(current.element === element){ 
        return index; 
      } 
      current = current.next; 
    } 
 
    return false; 
  }; 
 
  this.toString = function(){ 
    var current = head, 
      indexCheck = 0, 
      string = &#39;&#39;; 
 
    while(current && indexCheck < length){ 
      string += current.element; 
      indexCheck++; 
      current = current.next; 
    }   
 
    return string; 
  }; 
 
  this.isEmpty = function(){ 
    return length === 0; 
  }; 
 
  this.getHead = function(){ 
    return head; 
  }; 
 
  this.getTail = function(){ 
    return tail; 
  }; 
 
  this.size = function(){ 
    return length; 
  }; 
}

登入後複製

熱AI工具

Undresser.AI Undress

人工智慧驅動的應用程序，用於創建逼真的裸體照片

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

免費脫衣圖片

Clothoff.io

AI脫衣器

Video Face Swap

使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！

熱工具

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

中文版，非常好用

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

gmail信箱登陸入口在哪裡

7804

Java教學

1645

CakePHP 教程

1402

Laravel 教程

1300

PHP教程

1236

Related knowledge

華為手機如何實現雙微信登入？ Mar 24, 2024 am 11:27 AM

華為手機如何實現雙微信登入？隨著社群媒體的興起，微信已成為人們日常生活中不可或缺的溝通工具之一。然而，許多人可能會遇到一個問題：在同一部手機上同時登入多個微信帳號。對於華為手機用戶來說，實現雙微信登入並不困難，本文將介紹華為手機如何實現雙微信登入的方法。首先，華為手機自帶的EMUI系統提供了一個很方便的功能－應用程式雙開。透過應用程式雙開功能，用戶可以在手機上同

建議：優秀JS開源人臉偵測辨識項目 Apr 03, 2024 am 11:55 AM

人臉偵測辨識技術已經是一個比較成熟且應用廣泛的技術。而目前最廣泛的網路應用語言非JS莫屬，在Web前端實現人臉偵測辨識相比後端的人臉辨識有優勢也有弱勢。優點包括減少網路互動、即時識別，大大縮短了使用者等待時間，提高了使用者體驗；弱勢是：受到模型大小限制，其中準確率也有限。如何在web端使用js實現人臉偵測呢？為了實現Web端人臉識別，需要熟悉相關的程式語言和技術，如JavaScript、HTML、CSS、WebRTC等。同時也需要掌握相關的電腦視覺和人工智慧技術。值得注意的是，由於Web端的計

PHP程式設計指南：實作斐波那契數列的方法 Mar 20, 2024 pm 04:54 PM

程式語言PHP是一種用於Web開發的強大工具，能夠支援多種不同的程式設計邏輯和演算法。其中，實作斐波那契數列是一個常見且經典的程式設計問題。在這篇文章中，將介紹如何使用PHP程式語言來實作斐波那契數列的方法，並附上具體的程式碼範例。斐波那契數列是一個數學上的序列，其定義如下：數列的第一個和第二個元素為1，從第三個元素開始，每個元素的值等於前兩個元素的和。數列的前幾元

如何在華為手機上實現微信分身功能 Mar 24, 2024 pm 06:03 PM

如何在華為手機上實現微信分身功能隨著社群軟體的普及和人們對隱私安全的日益重視，微信分身功能逐漸成為人們關注的焦點。微信分身功能可以幫助使用者在同一台手機上同時登入多個微信帳號，方便管理和使用。在華為手機上實現微信分身功能並不困難，只需要按照以下步驟操作即可。第一步：確保手機系統版本和微信版本符合要求首先，確保你的華為手機系統版本已更新至最新版本，以及微信App

掌握Golang如何實現遊戲開發的可能性 Mar 16, 2024 pm 12:57 PM

在現今的軟體開發領域中，Golang（Go語言）作為一種高效、簡潔、並發性強的程式語言，越來越受到開發者的青睞。其豐富的標準庫和高效的並發特性使它成為遊戲開發領域的一個備受關注的選擇。本文將探討如何利用Golang來實現遊戲開發，並透過具體的程式碼範例來展示其強大的可能性。 1.Golang在遊戲開發中的優勢作為靜態類型語言，Golang正在建構大型遊戲系統

如何在Golang中實現精確除法運算 Feb 20, 2024 pm 10:51 PM

在Golang中實現精確除法運算是一個常見的需求，特別是在涉及金融計算或其它需要高精度計算的場景中。 Golang的內建的除法運算子「/」是針對浮點數計算的，並且有時會出現精度遺失的問題。為了解決這個問題，我們可以藉助第三方函式庫或自訂函數來實現精確除法運算。一種常見的方法是使用math/big套件中的Rat類型，它提供了分數的表示形式，可以用來實現精確的除法運算

PHP遊戲需求實作指南 Mar 11, 2024 am 08:45 AM

PHP遊戲需求實現指南隨著網路的普及和發展，網頁遊戲的市場也越來越火爆。許多開發者希望利用PHP語言來開發自己的網頁遊戲，而實現遊戲需求是其中一個關鍵步驟。本文將介紹如何利用PHP語言來實現常見的遊戲需求，並提供具體的程式碼範例。 1.創造遊戲角色在網頁遊戲中，遊戲角色是非常重要的元素。我們需要定義遊戲角色的屬性，例如姓名、等級、經驗值等，並提供方法來操作這些

js和vue的關係 Mar 11, 2024 pm 05:21 PM

js和vue的關係：1、JS作為Web開發基石；2、Vue.js作為前端框架的崛起；3、JS與Vue的互補關係；4、JS與Vue的實踐應用。

See all articles

JavaScript雙向鍊錶和雙向循環鍊錶的實現

熱AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

Video Face Swap

熱門文章

熱工具

記事本++7.3.1

SublimeText3漢化版

禪工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

熱門話題