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でランナーコンテナを構成する方法

推薦する

MySQL 8.0.20 インストール チュートリアル (画像とテキスト付き) (Windows 64 ビット)

1: mysql公式サイトからダウンロードhttps://dev.mysql.com/downlo...

jsオブジェクトの読み取り速度の詳細な例

1. リテラルとローカル変数へのアクセスは最も高速ですが、配列要素とオブジェクト メンバーへのアクセ...

nginxプロキシsocket.ioサービスの落とし穴の詳細な説明

目次Nginx は 2 つの socket.io サーバーをプロキシします。 socket.ioの動...

Dockerイメージをプルしてバージョンを確認する方法

イメージのバージョンとタグを確認するには、docker hubで確認する必要があります。アドレスは次...

ApplicationHost.config (IIS ストレージ構成領域ファイル) の概要

新しく作成された Web サイトの場合は、ASP.NET MVC5 を例に挙げます。セッションを処理...

Ubuntu 18.04 Server バージョンのインストールと使用方法 (画像とテキスト)

1 システムのインストール手順OSバージョン:1804イメージのダウンロード: http://cd...

シンプルなカルーセルの最も完全なコード分析を実装するJavaScript(ES6オブジェクト指向)

この記事では、シンプルなカルーセルを実装するためのJavaScriptの具体的なコードを参考までに紹...

Vueはカルーセルのフレームレート再生を実装します

この記事の例では、カルーセルのフレームレート再生を実現するためのVueの具体的なコードを参考までに共...

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

この記事ではMySQL 8.0.15のインストールと設定方法を参考までに記録します。具体的な内容は以...

Vueはページの部分的なリフレッシュを実装します(ルータビューのページリフレッシュ)

Vue でprovide+inject組み合わせを使用するまず、App.vue を変更する必要があ...

dockerを使用してTomcatをデプロイし、Skywalkingに接続する

目次1. 概要2. dockerを使用してTomcatをデプロイし、Skywalkingに接続する要...

MySQLの外部結合と内部結合クエリの違い

外部結合の構文は次のとおりです。フィールド名を選択FROM テーブル名 1 LEFT|RIGHT|F...

サーバーから返される14の一般的なHTTPステータスコードの詳細な説明

HTTP ステータス コードステータス コードは 3 桁の数字と理由フレーズ (最も一般的なもの: ...

MySQL の結合クエリとサブクエリの問題

目次複数テーブル結合の基本構文クロス結合と直積現象クロスコネクトデカルト積現象内部結合外部結合左外部...

高度な CSS の 3 つの方法を使用して複数行の省略を実装するサンプル コード

序文これは古くからの要望ですが、オンラインで解決策を探している人はまだ多く、特に検索結果の上位にラン...