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

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 メソッド-----リストの指定された位置から項目を削除します

まず、削除された項目の位置が範囲外かどうかを判断します。範囲外ではない場合は、 previouscurrent 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 をよろしくお願いいたします。

以下もご興味があるかもしれません:
  • JavaScript で完全に機能する単方向リンク リストを実装する方法
  • JavaScript データ構造: 単方向リンクリストと循環リンクリスト
  • Node.js 環境下で JavaScript に単一リンク リストと二重リンク リスト構造を実装する

<<:  CSS3は、Transformを使用して動く2D時計を作成します。

>>:  Dockerでランナーコンテナを構成する方法

推薦する

ネイティブjsは9マスグリッドのドラッグアンドドロップを実現します

ネイティブJSを使用して9つの正方形のグリッドを記述し、9つのグリッドの位置をドラッグして変更する効...

CSS3 のメディアクエリと rem レイアウトを組み合わせてモバイル画面に適応

CSS3 構文: (750 ピクセルのデザインの場合、1rem = 100 ピクセル) @media...

docker run によって起動されたコンテナがハングしてデータが失われた場合の対処方法

シナリオの説明あるシステムでは、機能サービスはdocker stack deploy xxxで起動し...

Reactのコンポーネント共同利用実装

目次ネスティング親子コンポーネント通信ブラザーコンポーネント通信撤回するReact の Linked...

MySQL 8.0.24 バージョンのインストールと設定方法のグラフィックチュートリアル

この記事ではMySQL 8.0.24バージョンのインストールと設定方法を記録し、皆さんと共有しますM...

Youdaの新しいプチビューの実装

目次序文導入ライブ使いやすいルートスコープマウント要素の指定ライフサイクルコンポーネントグローバル状...

Webpack ファイル パッケージ化エラー例外

webpack をパッケージ化する前に、次の作業が完了していることを確認する必要があります。 1) ...

MySQLは文字列関数のSQL文をインターセプトします

1. left(name,4)は左の4文字をインターセプトしますリスト: SELECT LEFT(2...

MySQLで最新のトランザクションIDを照会する方法

前に書いた内容: ビジネス ロジックの判断を行うために、最新のトランザクション ID を表示する必要...

Windows10にmysql5.7.18をインストールするチュートリアル

このチュートリアルでは、MySQL 5.7.18のインストールと設定方法を参考までに紹介します。具体...

WebページでjQueryを参照する方法

CDN(コンテンツ配信ネットワーク)を通じて参照できます。 jQuery は Google と Mi...

dockerでnginxを実行するときにdaemon offが使用される理由についての簡単な説明

とても嬉しいです。この問題に遭遇したとき、私はDockerコンテナのプロセス原理について話さなければ...

コードをセマンティックにする HTML のヒント

HTML のセマンティクスはありふれた問題のようです。Google で検索すると、セマンティクスに関...

PDO を使用して SQL インジェクションを防ぐ原理の分析

序文この記事では、SQL インジェクションを回避するために pdo の前処理メソッドを使用します。詳...

Docker を使用してイメージをローカルにパッケージ化してデプロイする方法

初めてDockerを使用してイメージをローカルにパッケージ化してデプロイするまず、私のラップトップシ...