JavaScript は単一のリンクリストプロセス分析を実装します

序文：

複数の要素を格納するために、配列は最も一般的に使用されるデータ構造ですが、配列には多くの欠点もあります。

配列の作成には通常、連続したメモリ空間が必要であり、サイズは固定されているため、現在の配列が容量要件を満たせない場合は、拡張する必要があります（通常は、より大きな配列を適用し、元の配列の要素をその配列にコピーすることによって）。
配列要素の先頭または中間にデータを挿入するとコストが非常にかかり、多数の要素をシフトする必要があります。

したがって、複数の要素を格納するための別のオプションは、リンクリストです。配列とは異なり、リンクリスト内の要素はメモリ内で連続したスペースである必要はありません。リンクリストの各要素には、要素自体と次の要素への参照を格納するノードがあります。
リンクリストには配列に比べていくつかの利点があります。

メモリ空間は連続している必要がないため、コンピュータのメモリを最大限に活用し、柔軟で動的なメモリ管理を実現できます。
リンクリストは作成時にサイズを指定する必要がなく、無制限に拡張できます。
リンクリストにデータを挿入したり削除したりする場合、イベントの複雑さは O(1) に達する可能性があり、これは配列よりもはるかに効率的です。

リンクリストには、配列に比べていくつかの欠点があります。

リンクリスト内の任意の位置にある要素にアクセスする場合は、先頭から開始する必要があり、添え字を介して要素に直接アクセスすることはできません。

1. 単方向リンクリストとは何か

では、単方向リンクリストとは一体何でしょうか?

これは電車のようなもので、機関車はノードに接続され、ノードには乗客がいて、このノードは次のノードに接続され、以下に示すように続きます。

リンクリストの構造は次のとおりです。

直感的なリンクリストを理解したので、単一リンクリストのコードをカプセル化してみましょう。

2. 単方向リンクリストのカプセル化

まず、リンクリスト構造を表すNodeListクラスをカプセル化します。このクラスでは、各ノードの情報 (データと次のノードへの参照) をカプセル化するために、内部クラス Node をカプセル化します。次に、 NodeListクラスに 2 つの属性を保存します。1 つはリンクリストの長さ、もう 1 つはリンクリストの先頭ノードです。

以下のように表示されます。

 関数LinkedList(){
            this.length = 0;
            this.head = null;
            //内部クラス関数 Node(data){
                this.data = データ;
                this.next = null;
            }
        }

3. 単連結リストの一般的な操作

次に、単一リンクリストのよく使用される操作を追加します。主なものは次のとおりです。

append（element) : リストの末尾に項目を追加する
insert(position,element) : リスト内の特定の位置に項目を挿入する
get(position) : 対応する位置にある要素を取得します
indexOf(element) : リスト内の要素のインデックスを返します。要素がリストに存在しない場合は -1 を返します。
update(position，ele) : 特定の位置にある要素を変更する
removeAt(position) : リスト内の指定された位置から項目を削除します
remove(element) : リストから項目を削除する
isEmpty() : リンクリストに要素が含まれていない場合は true を返し、リンクリストの長さが 0 より大きい場合は false を返します。
size() : 配列のlengthプロパティに関連するリンクリスト内の要素数を返します。
toString() : リスト項目はNodeクラスを使用するため、要素の値を出力するにはJavaScriptオブジェクトから継承されたデフォルトのtoStringメソッドをオーバーライドする必要があります。

次に、それらを1つずつ実装します。

1. append(element) メソッド-----リストの末尾に項目を追加する

リンクリストの末尾にデータを追加する場合、次の 2 つの状況が考えられます。

リンクリスト自体は空で、新しく追加されたデータが唯一のノードである
リンクリストは空ではなく、ノードは他のノードの後に追加される必要がある

したがって、判断する必要があります。リンクリストが空の場合は、ヘッドノードのポインタを新しいノードに直接ポイントします。
リンクリストが空でない場合は、一時ノードを作成し、それを先頭ノードと等しくして判定します。それが指すノードのポインタフィールドが空の場合は、末尾ノードです。新しく追加されたノードを末尾に追加します。つまり、末尾ノードのポインタが新しく追加されたノードを指すようにします。指すノードのポインタフィールドが空でない場合は、この一時ノードのポインタフィールドを次のノードにポイントさせ、このノードのポインタフィールドが空になるまで (つまり、末尾のノードになるまで) ループを続けます。次に、ノードを追加するたびに、リンクリストの長さを 1 ずつ増やします。

LinkedList.prototype.append = function(data){
                var newNode = 新しいノード(データ);
                // リンクリストが空かどうかを判定します // 1. 空の場合 if (this.length === 0) {
                    ノードを新規作成します。
                }それ以外{
                    //空ではありません var current = this.head;
                    if(現在.次){
                        現在の = 現在の.次;
                    }
                    現在のノードの次。
                }
                this.length += 1;
            }

2. toStringメソッド ----- 要素の値を出力する

これは比較的簡単です。主なことは、各要素を取得することです。リンクリストの要素を取得するには、最初のノードから開始する必要があるため、先頭ノードから開始し、各ノードをループして、その中のelementを取り出し、それを文字列に連結して、文字列を返すことができます。

LinkedList.prototype.toString = 関数(){
                var 現在の = this.head;
                var ListStr = '';
                while(現在){
                    ListStr += 現在のデータ + ' ';
                    現在の = 現在の.次;
                }
                ListStr を返します。
            }

検証: いくつかの新しいノードを作成し、印刷します

 var list = 新しい LinkedList();
        リストに追加します('a');
        リストに追加します('b');
        リストに追加します('c');
        リストに追加します('d');
        リストに追加します('e');
        アラート(リスト);

印刷結果は次のとおりです。

3. 挿入メソッド ----- リスト内の特定の位置に項目を挿入する

任意の位置にデータを挿入する方法を実装するには、まず挿入位置が範囲外かどうかを判断し、範囲外ではない場合を 2 つのケースに分けます。最初の位置に挿入された場合は、新しく追加されたノードがヘッドであることを意味します。その後、元のヘッドノードを新しいノードの次のノードとして使用し、ヘッドが新しいノードを指すようにします。他の位置に挿入する場合は、まずループを介してノードの位置を見つけ、ループ中に前のノードと次のノードを保存する必要があります。正しい位置を見つけた後、新しいノードのNext次のノードにポイントし、前のノードのnextノードを新しいノードにポイントします。

コードは次のとおりです。

 LinkedList.prototype.insert = function(位置,データ){
                if(位置<0 || 位置 >this.length){
                   false を返します。
               }
                var newNode = 新しいノード(データ);
                var インデックス = 0;
              if(位置 == 0){
                Node.next = this.head;
                ノードを新規作成します。

              }それ以外{
                    while(インデックス++ < 位置){
                        var 現在の = this.head;
                        var 前 = null;
                        前 = 現在;
                        現在の = 現在の.次;
                    }
                    現在のノードを次に示します。
                    previous.next = 新しいノード;
                }
                this.length += 1;
                true を返します。
                }

検証: 最初の位置に xl を挿入し、2 番目の位置に wh を挿入します。

リストを挿入(1,'xl')
       リストを挿入(2,'wh')
        アラート(リスト)

4. 取得メソッド-----対応する位置の要素を取得する

この方法は比較的単純です。まず、 positonが範囲外かどうかをチェックし、次にリンクリストを一時ノードを介してトラバースしてターゲットの位置に到達し、その位置にある要素を取得します。

LinkedList.prototype.get = function(位置,データ){

                var 現在の = this.head;
                var インデックス = 0;
                if(位置 < 0 || 位置 >= this.length){
                    null を返します。
                }それ以外{
                    while(インデックス<位置){
                        現在の = 現在の.次;
                        インデックス++;
                    }
                    現在のデータを返します。
                }
            }

検証: 3 番目の位置にある要素を取得します。

アラート(リスト.get(3));

5. indexOf() メソッド ----- リスト内の要素のインデックスを返します

まず、検索対象の要素の位置が存在するかどうかを判断します。存在しない場合は -1 を返します。存在する場合、2 つのケースがあります。返された要素が最初の位置にある場合、最初の位置のインデックスが直接返されます。返された要素が別の位置にある場合は、最初にループを介してノードの位置を見つける必要があります。このプロセス中、インデックスはトラバーサルの数だけ増加する必要があります。正しい要素の位置を見つけた後、印刷されたインデックスがターゲットの位置になります。

LinkedList.prototype.indexOf = function(data){
                var インデックス = 0;
                var 現在の = this.head;
                while(現在){
                    現在のデータ == データの場合
                        インデックスを返します。
                    }
                    それ以外{
                        現在の = 現在の.次;
                    インデックス++;
                    }
                }
                -1 を返します。
            }
        }

検証: c のインデックスを取得します。

アラート(リストのインデックス('c'));

6. 更新方法-----特定の位置にある要素を変更する

このメソッドは get メソッドと非常によく似ています。後方にトラバースします。index index値がpositionと等しい場合、ターゲットの位置が見つかり、日付がターゲットの値に変更されることを意味します。

LinkedList.prototype.update = function(position,ele){
                if(位置<0 || 位置>=this.length){
                    false を返します。
                }それ以外{
                    var インデックス = 0;
                    var 現在の = this.head;
                    while(インデックス++ <位置){
                        現在の = 現在の.次;
                    }
                    現在のデータ = ele;
                    true を返します。
                }
            }

検証: 位置0の要素をbearに変更します

 リストを更新(0,'クマ')
      アラート(リスト)

7. removeAt メソッド-----リストの指定された位置から項目を削除します

まず、削除された項目の位置が範囲外かどうかを判断します。範囲外ではない場合は、 previousとcurrent 2 つの一時ノードを指定します。 previous 、前のcurrentの値を保存するために使用されます。インデックス位置がターゲット位置に等しくなるまで、先頭ノードからトラバースを開始します。一時ノード current がターゲット位置までトラバースし、一時ノードの previous next が次の next を指すようにします。

LinkedList.prototype.removeAt = function(位置,データ){
                var 現在の = this.head;
                var 前 = null;
                var インデックス = 0;
                if(位置<0 || 位置>=this.length){
                    false を返します。
                }それ以外{
                    while(インデックス++ <位置){
                        前 = 現在;
                        現在の = 現在の.次;
                    }
                    前の.次の = 現在の.次の;
                    this.length -= 1;
                    true を返します。
                }
            }
        }

検証: 3 番目の位置にある要素を削除します。

リスト.削除(3)
      アラート(リスト)

8. Removeメソッド - リストから項目を削除する

まず、削除する要素がリンクリスト内にあるかどうかを判断します。ない場合は、 falseを返します。それ以外の場合は、リンクリストをトラバースするための一時ノードを構築します。一時ノードのデータ値が削除する要素と等しい場合は、トラバースを停止し、一時ノードの前のnextが次の next を指すようにします。ここで、以前のcurrent値を格納するための一時ノードを構築できます。

LinkedList.prototype.remove = function(ele){
                var 現在の = this.head;
                var 前 = null;
                var インデックス = 0;
                while(current.data !== ele){
                    前 = 現在;
                    現在の = 現在の.次;
                    インデックス++;
                }
                前の.次の = 現在の.次の;
            }

検証: 値が xl の要素を削除します。

 リストを削除します('xl')
      アラート(リスト)

9. isEmpty メソッド-----リンクリストが空かどうかを判定する

length判断により、リンクリストに要素が含まれていない場合はtrueを返し、リンクリストの長さが0より大きい場合はfalseを返します。

LinkedList.prototype.isEmpty = 関数(){
                    this.length == 0 を返します。
                }

確認する：

 アラート(リストが空です())

9. Sizeメソッド ----- リンクリストに含まれる要素の数を返します

直接返される要素のlengthはその番号です。

LinkedList.prototype.size = 関数(){
                    this.length を返します。
                }

確認する：

   アラート(リスト.サイズ())

これで、JavaScript による単一リンクリストプロセス解析の実装に関するこの記事は終了です。JavaScript による単一リンクリストコンテンツの実装に関する関連情報については、123WORDPRESS.COM の以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。

以下もご興味があるかもしれません: