JavaScriptのデータ構造のリンクリストの実装方法（画像とテキスト）の紹介

リンクリストは一般的なデータ構造です。ストレージを動的に割り当てる仕組みです。この記事では主にJavaScriptデータ構造におけるリンクリストの実装について紹介します。これは参考価値があります。エディターで見てみましょう

前のポスターでは、データ構造スタックとキューの実装についてそれぞれ説明しましたが、その時点で使用されていたデータ構造はすべて配列を使用して実装されましたが、配列は最適なデータ構造ではない場合があります。たとえば、配列内の要素を追加または削除する場合、他の要素を移動する必要がありますが、JavaScript で spit() メソッドを使用する場合は、他の要素にアクセスする必要はありません。配列を使用すると速度が遅いと感じる場合は、リンク リストの使用を検討してください。

リンクリストの概念

リンクリストは一般的なデータ構造です。ストレージを動的に割り当てる仕組みです。リンクされたリストには、head で表される「ヘッド ポインタ」変数があり、要素を指すアドレスが格納されます。各ノードは、オブジェクトの参照を使用して後続ノードを指します。別のノードを指す参照はチェーンと呼ばれます。

配列要素は添字 (位置) によって参照され、リンクされたリスト要素はその関係によって参照されます。したがって、連結リストの挿入効率は非常に高くなります。次の図は、連結リスト ノード d の挿入処理を示しています。 NodeクラスとLinkedListクラスの2つのクラスがあり、Nodeはノードデータ、LinkedListはリンクリストを操作するためのメソッドを保存します。

まず Node クラスを見てみましょう:

function Node(element){
  this.element = element;
   this.next = null;
 }

要素はノード上のデータを保存するために使用され、next は次のノードを指すリンクを保存するために使用されます。

LinkedList クラス:

function LinkedList(){
     this.head = new Node('head');
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}

find() メソッド。ヘッド ノードから開始して、アイテムのコンテンツに等しい要素が見つかるまでリンク リスト ノードに沿って検索し、見つかった場合はノードが返され、それ以外の場合は空が返されます。

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据，没找到返回null
}

メソッドを挿入します。要素挿入の前述のデモからわかるように、挿入を実装するには 4 つの簡単な手順があります: 1. ノードを作成します

2. ターゲット ノードの次のポインティング リンクを変更します

4. 対象ノードの接続 挿入するノードのnext

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }

Remove()メソッドにポイントの次の値を代入します。ノードを削除するには、まず削除されたノードの前のノードを見つける必要があります。

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}

3 つの簡単な手順:

1. ノードを作成します。ターゲットノードの前のノード ノード

3. 変更された前のノードの次のノードは、削除されたノードの n 番目後のノードを指します

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }

Show() メソッド:

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}

テストプログラム:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

出力:

ダブルリンクリスト

リンクリストの先頭ノードから末尾ノードへのトラバースは非常に簡単ですが、場合によっては、後ろから前へトラバースする必要があります。この時点で、先行ノードへのリンクを保存する Node オブジェクトに

attribute

を追加できます。投稿者は、次の図を使用して、二重リンク リストの動作原理を説明します。

まず、フロント属性を Node クラスに追加します:

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }

もちろん、対応する insert() メソッドと Remove() メソッドにも対応する変更を加える必要があります:

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}

にリンクされたリストを表示します。逆順:

必須 最後のノードを見つけるためのメソッドを二重リンクリストに追加します。 findLast() メソッドはリンク リスト内の最後のノードを検索するため、チェーンを前から後ろにたどる必要がなくなります。

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

逆順出力の実現:

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}

テストプログラム:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());

出力:

循環リンクリスト

循環リンクリストは、リンクストレージ構造の別の形式です。その特徴は、リストの最後のノードのポインタ フィールドが先頭のノードを指しており、リンクされたリスト全体がリングを形成していることです。循環リンク リストは一方向リンク リストに似ており、ノード タイプは同じです。唯一の違いは、循環リンク リストを作成するときに、ヘッド ノードの次の属性がそれ自体を指すようにすることです。つまり、

この動作はリンク リスト内の各ノードに送信されるため、次の属性が各ノードの は、リンクされたリストの先頭ノードを指します。ポスターでは、循環リンク リストを表すために次の図を使用しています:

修正構築メソッド

:

function LinkedList(){
  this.head = new Node('head');//初始化
  this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
  this.find = find;
  this.frontNode = frontNode;
  this.insert = insert;
  this.remove = remove;
  this.show = show; 
}

这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!='head'){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据，没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

测试结果：

以上がJavaScriptのデータ構造のリンクリストの実装方法（画像とテキスト）の紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。