データ構造の学習: JavaScript を使用したリンク リスト操作の実装 (詳細な例)

この記事では、JavaScript を使用してデータ構造学習でリンク リストを実装する方法に関する関連知識を提供します。お役に立てば幸いです。

リンクされたリストには次の特徴があります:

• スペースは動的に拡張できます (js でも同じです)は arrays に当てはまりますが、一部の言語では配列の長さが固定されており、動的に追加できません (C 言語など)

• #ヘッド ノードが必要です

• 要件 次のノードのアドレスを知っていること

リンクされたリスト内の各ノードはオブジェクトと見なすことができます。オブジェクトには 2 つの属性があり、1 つはノードの値、もう 1 つはノードの次のノードのアドレスです (二重リンク リストの場合は、前のノード アドレスの属性を追加します)

Toノードを追加する操作を実装します:

1 末尾ノードにノードを追加します。

 //在尾节点处添加节点
        function append(element){
        let node = new node(element);
        let current;
        if(head == null){
            current = node
        }else{
            while(current.next){
                current = current.next;
            }
            current.next = node
        }
            length++;
        }

コード分析:

受信要素に基づいてノードを定義します。この要素はこのノードの値として使用されます。
• 現在のノードを表す変数を定義します。
• #それにヘッドが含まれているかどうかを判断します。ヘッド ノードがない場合は、リンク リストに値がないことを意味し、渡される値はヘッド ノードとして使用されます。それ以外の場合は、リンク リストを走査し、最後のノードを見つけて、その次の属性を割り当てます。新しいノード
• リンク リストの長さ 1

2. 任意の位置にノードを追加します

分析:

この位置にある前のノードの次の属性をこのノードに割り当て、元の次のノードを保存して、それをこのノードの次の属性に割り当てます

function insert(position,element){
        let node = new Node(element);
        let current = head;
        let previous;//当前节点的前一个节点，在position处添加节点，就是在previos和current之间添加
        if(position = 0){
          node.next = head;
          head = node;
        }else{
          for(let i = 0;i< position;i++){
            pervious = current;
            current = current.next;
          }

          pervious.next = node;
          node.next = current;
        }
        length++;
        return true;
      }

コード分析:

位置が範囲外かどうかを確認し、範囲外である場合はノードを作成します
• 現在のノードを表す変数を定義し、ヘッド ノードとして初期化すると、ヘッド ノードからトラバースすることを意味します。変数は次のことを表します。現在のノードの前のノード。ノードを挿入するときに前のノードを見つけやすくするために使用されます。
• ヘッド ノードの前に追加するかどうかを決定し、追加する場合は、ヘッド ノードを次の属性に割り当てます。ノードの先頭ノードをこのノードに変更します。そうでない場合は、この位置のノードをトラバースし、この位置のノードの前にノードを挿入します。
• リンク リストの長さ 1

ノードの削除操作を実現する

#分析: ノードの削除操作は、ノードを削除する前にノードを削除することです。ターゲット ノード。ポインタはターゲット ノードの後のノードを指します

1. 指定されたノードを削除します

function removed(element){
    
      let node = new Node(element);
      let pervious;
      let nextNode;
      let current = head;

    if(head != null){
      while (current != node){
        pervious = current;
        current = current.next;
        nextNode = current.next;
      }  

      pervious.next = nextNode;
      length--;
      return true;
    }else{
      return false;
    }    
    }

2. 指定された位置のノードを削除します

function removedAt(position){
        let current = head;
        let pervious;
        let nextNode;
        let i = 0;

        while(i < position){
          pervious = current;
          current = current.next;
          nextNode = current.next;
        }

        pervious.next = nextNode;
        length--;
        return true;
      }

ノードのクエリ操作を実装する

分析: ノードのクエリはノードの削除と似ており、どちらもトラバースして対応するノードまたは対応する場所を見つけ、操作を実行します

1.特定の位置がどのノードであるかを問い合わせる

function searchElement(element){
      //输入元素，找到该元素后返回该元素的位置
      if(head != null){
        let node = new Node(element);
        let current;
        let index = 0;
        if(head == node){
          return 0;
        }else{
          current = head;
          while(current != node){
            current = current.next;
            index++;
          }
          return index;
        }
      }else{
        return -1;
      }
    }

2. 特定のノードがどの位置であるかを問い合わせる

function searchPosition(position){
        let i = 0;
        let current = head;
        while(i< position){
          current = current.next;
          i++;
        }
        return current;
    }

アイデアのまとめ

リンク リストには多くの操作があり、少し複雑です。リンク リストには、二重リンク リスト (ノードの初期化時に前のノードを追加する) と循環リンク リスト (末尾ノードの次のノードが先頭ノード) も含まれます。これらのリンクされたリストの操作は js を使用して実装することもできるため、ここでは詳しく説明しません。要約すると、リンク リストの核心は、

リンク リスト内のノードは 2 つの属性値 (1 つはノード値、もう 1 つはポインタ) を持つオブジェクトと見なすことができるということです
• リンク リストの追加と削除が変更です。ポインタが
• リンク リスト検索を指すと、フォーカスは current = current.next

[関連する推奨事項:

JavaScript 学習チュートリアル]

以上がデータ構造の学習: JavaScript を使用したリンク リスト操作の実装 (詳細な例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。