JavaScriptの二重リンクリストと二重循環リンクリストについて詳しく解説

この記事では、JavaScript データ構造の二重リンク リストと二重循環リンク リストの実装を主に紹介します。興味のある方は参考にしてください。

二重リンク リストと通常のリンク リストの違いは、リンク リストです。 , ノードには次のノードへのリンクしかありませんが、二重リンク リストではリンクは双方向であり、1 つのリンクは次の要素へ、もう 1 つは前の要素へのリンクです。

二重リンクリストでは、リストを反復する 2 つの方法 (最初から最後まで、またはその逆) が提供されます。特定のノードの次または前の要素にアクセスすることもできます。一方向リンクリストでは、リストの反復中に探している要素を見逃した場合、リストの開始点に戻って反復を再度開始する必要があります。これは二重リンクリストの利点です。

二重リンク リスト: 一方向リンク リストはリンク リスト ノードを一方向にのみ走査できますが、ノード ポインター フィールドに前方ポインターが追加された二重リンク リストは両方向にノードを走査できます。これにより、二重リンク リストが任意のノードでリンク リスト全体を横断できるようになります。

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

双方向循環リンク リスト: 双方向リンク リストの先頭ポインタと末尾ポインタを接続して、双方向循環リンク リストを形成します。この種のリンク リストは、どのノードからでも同時に 2 方向にノードをトラバースでき、ノードへのクエリの速度も最速になります。

rreee

以上が皆さんのためにまとめたもので、今後皆さんのお役に立てれば幸いです。

関連記事:

親ノードが選択されたときに無効にした子ノードも選択されるようにJstreeで実装する方法

vue.jsのmint-uiにカルーセルチャートを統合する方法

In AngularJS コレクションデータのトラバーサル表示の実装方法

以上がJavaScriptの二重リンクリストと二重循環リンクリストについて詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。