JavaScript データ構造の単一リンク リストと循環リンク リストの例を共有する

この記事では、JavaScript の単一リンク リストと循環リンク リストのデータ構造を中心に、JavaScript がどのように実装しているのかについても詳しく紹介していますので、興味のある方はぜひ参考にしてください。

本題に入り、リンク リストのデータ構造に関する知識を簡単に紹介します。

リンク リストは、物理ストレージ ユニット内の非線形かつ不連続なデータ構造です (データ ロジックでは線形です)。その A ノードは、データ フィールドとポインター フィールドの 2 つのフィールドで構成されます。実際のデータはデータ フィールドに格納され、ポインタ フィールドにはリンク リスト内の次の要素または前の要素を指すポインタ情報が格納されます。ポインタが存在するからこそ、連結リストの格納は物理単位で不連続となる。

リンクリストの長所と短所も同様に明らかです。線形リストと比較すると、リンク リストは、要素の移動が必要な線形リスト (配列) とは異なり、ポインタ情報を変更するだけで操作を完了できるため、ノードの追加と削除がより効率的です。同様に、リンクされたリストの長さは理論的には無限で (メモリ容量の範囲内で)、長さは動的に変更できるため、線形リストに比べて大きな利点があります。 同様に、線形テーブルはノードにランダムにアクセスできず、リンク リストに沿ったポインター トラバーサル クエリを通じてのみアクセスできるため、データ要素へのアクセス効率は比較的低くなります。

以下は、JS 部分にカプセル化された一般的なメソッドと説明です

:

Method	Description
append(element)	リンクされたリストの最後にノード要素を追加します
insert (position, element)	位置positionにノード要素を挿入
removeAt(position)	インデックス値positionに従ってノードを削除
remove(element)	指定されたノード要素を検索して削除します
remove()	リンクリストの最後のノードを削除
indexOf(element)	指定されたノード要素のインデックス値を見つけて返す
isEmpty()	リンクされたリストは空です
size()	リンクされたリストの長さを取得します
toString()	文字列出力に変換します
getHead()	ヘッドノードを取得します
getTail ()	Get Tail ノード

一般的に使用されるさまざまなメソッドのアルゴリズムの説明は、結局のところ、非常に基本的な知識なので、誰でも簡単に読んで理解できると思います。

単一リンクリスト:

function LinkedList(){ 
 /*节点定义*/ 
 var Node = function(element){ 
  this.element = element; //存放节点内容 
  this.next = null; //指针 
 } 
 
 var length = 0, //存放链表长度 
  head = null; //头指针 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; //操作所用指针 
 
  if (!head){ 
   head = node; 
  }else { 
   current = head; 
 
   while(current.next){ 
    current = current.next; 
   } 
 
   current.next = node; 
  } 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if (position >= 0 && position <= length) { 
   var node = new Node(element), 
    current = head, 
    previous, 
    index = 0; 
 
   if(position === 0){ 
    node.next = current; 
    head = node; 
   }else{ 
    while(index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
    node.next = current; 
    previous.next = node; 
   } 
 
   length++; 
   return true; 
  }else{ 
   return false; 
  } 
  }; 
 
 this.removeAt = function(position){ 
  if(position > -1 && position < length){ 
   var current = head, 
    previous, 
    index = 0; 
 
   if (position === 0) { 
 
    head = current.next; 
 
   }else{ 
 
    while (index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = current.next; 
   }; 
 
   length--; 
   return current.element; 
  }else{ 
   return null; 
  } 
 }; 
 
 this.remove = function(element){ 
  var current = head, 
   previous; 
 
  if(element === current.element){ 
   head = current.next; 
   length--; 
   return true; 
  } 
  previous = current; 
  current = current.next; 
 
  while(current){ 
   if(element === current.element){ 
    previous.next = current.next; 
    length--; 
    return true; 
   }else{ 
    previous = current; 
    current = current.next; 
   } 
  } 
  return false; 
 }; 
 
 this.remove = function(){ 
  if(length < 1){ 
   return false; 
  } 
 
  var current = head, 
  previous; 
 
  if(length == 1){ 
   head = null; 
   length--; 
   return current.element; 
  } 
 
  
  while(current.next !== null){ 
   previous = current; 
   current = current.next; 
  } 
 
  previous.next = null; 
  length--; 
  return current.element; 
 }; 
 
 this.indexOf = function(element){ 
  var current = head, 
   index = 0; 
 
  while(current){ 
   if(element === current.element){ 
    return index; 
   } 
   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; 
 } 
  
}

循環リンクリスト: 単一リンクリストに基づいて、末尾ノードのポインタを先頭ノードに向けて循環リンクリストを形成します。循環リンク リスト内の任意のノードから開始して、リンク リスト全体をたどることができます。

function CircularLinkedList(){ 
 var Node = function(element){ 
  this.element = element; 
  this.next = null; 
 } 
 
 var length = 0, 
  head = null; 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; 
 
  if (!head) { 
   head = node; 
   node.next = head; 
  }else{ 
   current = head; 
 
   while(current.next !== head){ 
    current = current.next; 
   } 
 
   current.next = node; 
   node.next = head; 
  }; 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if(position > -1 && position < length){ 
   var node = new Node(element), 
    index = 0, 
    current = head, 
    previous; 
 
 
   if (position === 0) { 
 
    node.next = head; 
    head = node; 
 
   }else{ 
 
    while(index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = node; 
    node.next = current; 
 
   }; 
 
   length++; 
   return true; 
  }else{ 
   return false; 
  } 
 }; 
 
 this.removeAt = function(position){ 
  if(position > -1 && position < length){ 
   var current = head, 
    previous, 
    index = 0; 
 
   if (position === 0) { 
 
    head = current.next; 
 
   }else{ 
 
    while (index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = current.next; 
   }; 
 
   length--; 
   return current.element; 
  }else{ 
   return null; 
  } 
 }; 
 
 this.remove = function (element){ 
  var current = head, 
   previous, 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   if(current.element === element){ 
    if(indexCheck == 0){ 
     head = current.next; 
     length--; 
     return true; 
    }else{ 
     previous.next = current.next; 
     length--; 
     return true; 
    } 
   }else{ 
    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; 
   length--; 
   return current.element; 
  } 
 
  while(indexCheck++ < length){ 
   previous = current; 
   current = current.next; 
  } 
  previous.next = head; 
  length--; 
  return current.element; 
 }; 
 
 this.indexOf = function(element){ 
  var current = head, 
   index = 0; 
 
  while(current && index < length){ 
   if(current.element === element){ 
    return index; 
   }else{ 
    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;, 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   string += current.element; 
   current = current.next; 
   indexCheck++; 
  } 
 
  return string; 
 };  
 
}

使用方法:

クラス外の拡張メソッド:

関連推奨事項:

JavaScriptデータ構造における二重リンクリストの使用定義の例

JavaScriptデータ構造における優先キューと循環キュー

JavaScriptのデータ構造の二分探索木の定義と表現方法を詳しく解説

以上がJavaScript データ構造の単一リンク リストと循環リンク リストの例を共有するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。