JavaScriptは双方向リンクリストプロセス分析を実装します

JavaScriptは双方向リンクリストプロセス分析を実装します

1. 二重連結リストとは何か

単一リンク リストは、先頭から末尾、または末尾から先頭 (一般的には先頭から末尾) の方向のみをたどることができることがわかっています。つまり、リンク リストを接続するプロセスは一方向であり、実装の原則は、前のリンク リストに次のリストを指す参照があることです。さらに明らかな欠点があります:

次のノードへは簡単に到達できますが、前のノードに戻るのは困難です。しかし、実際の開発では、前のノードに戻る必要がある状況に遭遇することが多く、ここで双方向のリンクリストが必要になります。

いわゆる二重リンクリストは、先頭から末尾、末尾から先頭まで走査できるリンクリストです。ただし、二重リンクリストにも欠点があります。たとえば、ノードが挿入または削除されるたびに、2 つではなく 4 つのノード参照を処理する必要があります。単一のリンクリストと比較すると、より多くのメモリを消費します。ただし、これらの欠点は、使用の利便性と比較すると無視できるほど小さいものです。
二重リンクリストの構造図を見てみましょう。以下のように表示されます。

ここに画像の説明を挿入

二重リンクリストの特徴:

  • head と tail を使用して、それぞれヘッド ノードとテール ノードを指すことができます。
  • 各ノードは、前のノードへのポインタ(prev)、保存された要素(data)、次のノードへのポインタ(next)の3つの部分で構成されています。
  • 二重リンクリストの最初のノードの prev が null です
  • 二重リンクリストの最後のノードの次のノードはnullです

これを抽象化すると次のようになります。

ここに画像の説明を挿入

二重リンクリストの構造を理解した上で、二重リンクリストのカプセル化を見てみましょう。

2. 二重リンクリストのカプセル化

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

関数DoublyLinkedList(){
	 this.head = null;
	 this.tail = null;
	 this.length = 0;
	 関数 Node(データ){
		 this.data = データ;
		 this.prev = null;
		 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() : 配列の長さプロパティに関連するリンクリスト内の要素数を返します。

toString() : リスト項目はNodeクラスを使用するため、要素の値を出力するにはJavaScriptオブジェクトから継承されたデフォルトのtoStringメソッドをオーバーライドする必要があります。

forwardString() : 前方走査のノード文字列形式を返します。

backwardString() : 逆方向に走査されたノードの文字列形式を返します。

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

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

この方法は、単一リンク リスト メソッドに似ています。まず、新しいリストを作成し、リンク リストが空かどうかを判断します。空の場合は、リンク リストの先頭が、新しく作成されたリンク リストを直接指すようにします。空でない場合は、新しいノードの先行ポインターがリンク リストの末尾を指すようにし、リンク リストの末尾のノードが新しいリンク リストを指すようにします。

Doubly.prototype.append = function(data){
                var newNode = 新しいノード(データ);
                長さが 0 の場合
                    ノードを新規作成します。
                }それ以外{
                    newNode.prev = this.tail;
                    this.tail.next = 新しいノード;
                    }
                this.tail = newNode;
                this.length += 1;
            }

2. リンクリストを文字列に変換する

1. toString(): 要素の値を順方向に出力する

このメソッドは主に各要素を取得するために使用されます。デフォルトでは、リンク リストの要素は最初のノードから始まる必要があるため、先頭ノードから開始し、各ノードをループして要素を取り出し、それを文字列に連結して、文字列を返すことができます。具体的な方法は、一時ノードcurrentを作成し、この一時ノードが二重リンクリストの先頭を指すようにし、次にnextポインターを介して順番に逆方向にトラバースし、各トラバースから取得したデータをつなぎ合わせます。

DoublyLinkedList.prototype.tostring = function(){
                var 現在の = this.head;
                var str = '';
                while(現在){
                    str += 現在のデータ + ' ';
                    現在の = 現在の.次;
                }
               str を返します。
            }

2. forwardString(): 前方走査のノード文字列形式を返す

このメソッドは双方向リンク リストの順方向印刷と出力も実装しているため、ここで前のメソッドを直接呼び出すことができます。

DoublyLinkedList.prototype.forwardString = function(){
               this.toString() を返す
            }

3. backwardString(): 逆方向のトラバーサルのノード文字列形式を返す

このメソッドは、主に後ろから前へトラバースして各要素を取得して印刷するため、末尾のノードから開始し、各ノードをループして要素を取り出し、それを文字列に連結して、文字列を返すことができます。具体的な方法は、一時ノードcurrentを作成し、この一時ノードが二重リンクリストの末尾を指すようにし、次にprevポインターを介して順番に前方にトラバースし、各トラバースから取得したデータを結合することです。

 DoublyLinkedList.prototype.backwardString = function(){
                var 現在の値 = this.tail;
                var str = '';
                // 順番に前へ進み、各ノードを取得します while(current){
                    str += 現在のデータ +' ';
                    現在の = 現在の.前の;
                }
                str を返します。
            }

確認する:

たとえば、 append()メソッドを使用して、3 つのデータを含む二重リンク リストを作成し、それらをそれぞれ前方と後方に連結します。

var リスト = 新しい DoublyLinkedList();
         リストに追加します("a");
         リストに追加します("b");
         リストに追加します("c");
         リストに追加します("d");
         console.log('toString() メソッド: ' + list.toString());
         console.log('forwardString() メソッド: '+list.forwardString());
         console.log('backwardString() メソッド: ' + list.backwardString());

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

ここに画像の説明を挿入

検証に成功しました。

3. insert(位置,要素): リスト内の特定の位置に項目を挿入する

この方法は比較的複雑です。まず、挿入する位置が範囲外かどうかを判断します。範囲外ではない場合は、リンク リストの状況に応じて判断します。リンク リストが空の場合、挿入されるノードは最初の要素であり、先頭ノードと末尾ノードのポインタは新しく作成されたノードを直接指します。リンク リストが空でない場合、挿入位置には、最初の位置に挿入、最後に挿入、および中央に挿入の 3 つの状況があります。具体的な操作は以下のとおりです。

DoublyLinkedList.prototype.insert = function(位置,データ){
        var newNode = 新しいノード(データ);
         //範囲外の判定。満たされない場合は false を返す
         if(位置<0 || 位置>この長さ){
             false を返します。
         }それ以外{
             //再度判断する//リンクリストが空の場合は直接挿入するif(position==0){
                 ノードを新規作成します。
                 this.tail = newNode;
             }それ以外 {
             //リンクリストが空でない場合 //挿入位置が末尾にある場合 if(position == this.length){
                     this.tail.next = 新しいノード;
                     newNode.prev = this.tail;
                     this.tail = newNode;
                 }それ以外の場合(位置 == 0){
                     //挿入位置が最初のノードの場合 this.head.prev = newNode;
                     Node.next = this.head;
                     ノードを新規作成します。
                 }それ以外{
                     //挿入位置が中央にある場合 var index = 0;
                     var 現在の = this.head;
                     while(インデックス++ <位置){
                         現在の = 現在の.次;
                     }
                         現在のノードを次に示します。
                         newNode.prev = current.prev;
                         現在のノードを新しいノードに変更します。
                         現在のノードを新しいノードに変更します。
                 
             }
             this.length += 1;
         }
        
     }
 }

検証: 以下に示すように、位置 1 にxl挿入すると、

リストを挿入(1,'xl')
console.log(リスト.toString());

実行結果は次のとおりです。

ここに画像の説明を挿入

検証に成功しました。

4. get(position): 対応する位置にある要素を取得する

このメソッドは、まず位置が範囲外かどうかを判定します。範囲外ではない場合は、一時ノードとインデックスを定義し、一時ノードのポインタが先頭ノードを指すようにします。一時ノードをトラバースし、インデックスを増分します。トラバースしたノードの位置が取得する要素の位置と等しい場合は、一時ノードの対応する位置にある要素が取得する要素になります。

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

検証: 位置 = 2 の要素をクエリする

console.log('list.get(2):'+list.get(2));

結果は次のとおりです。

ここに画像の説明を挿入

検証に成功しました。

ただし、この検索方法には欠点があります。つまり、前から後ろにしか検索できないため、場合によっては非常に非効率的になります。そのため、両端から検索することができます。具体的な検索方法は、検索するノードの位置がリンクリストの長さの半分以下の場合は、前から後ろに検索できます。検索するノードの位置が長さの半分より大きい場合は、後ろから前に検索します。実装コードは次のとおりです。

    DoublyLinkedList.prototype.get = function(position){
        
        if(位置<0 || 位置>=this.length){
            false を返します。
        }それ以外{
            var len = Math.floor(this.length/2);
            if(位置<=長さ){
                var インデックス = 0;
                var 現在の = this.head;
                while(インデックス++ <位置){
                 現在の = 現在の.次;
                }
            }それ以外{
                var インデックス = this.length-1;
                var 現在の値 = this.tail;
                while(インデックス->位置){
                    現在の = 現在の.前の;
                }
            }
            現在のデータを返します。
        }
    }

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

一時ノードとインデックスを作成し、一時ノードを先頭ノードに向け、順に逆方向にトラバースして、インデックスを増やします。トラバースした一時ノードによって取得された要素が指定した要素と等しい場合、この時点での一時ノードの位置が目標位置となり、この位置のインデックスが目標値のインデックスとなります。

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

ここに画像の説明を挿入

検証に成功しました。

6. update(position, ele): 特定の位置にある要素を変更する

まず、変更する位置が範囲外かどうかを判断します。範囲外でない場合は、一時ノードとインデックスを定義し、一時ノードが先頭ノードを指すようにし、インデックス位置を 0 にして、一時ノードをトラバースし、この時点での一時ノードのインデックスが変更する要素の位置と等しいかどうかを判断します。等しい場合は、この時点での一時ノードの位置が変更する要素の位置であり、一時ノードのデータ領域で要素を直接変更できます。

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

検証: 位置0のデータrc置き換えます

リストを更新(0,'rc')
       console.log("list.update(0,'rc') は:");
       console.log(リスト.toString());

ここに画像の説明を挿入

検証に成功しました。

7. removeAt(position): リストの指定された位置から項目を削除します

このメソッドは、まず境界を越えたかどうかを判定する点でinsert()メソッドに似ています。境界を越えておらず、リンク リストにノードが 1 つしかない場合は、項目が直接削除され、リンク リストの先頭ノードと末尾ノードの両方が空を指すようになります。リンクリストに複数のノードがある場合は、3 つのケースに分けられ、操作は次のようになります。

DoublyLinkedList.prototype.removeAt = function(position){
        if(位置<0 || 位置>=this.length){
            null を返します。
        }それ以外{
            var 現在の = this.head;
            if(this.length === 1){
            //リンクリストの長さは1です
                this.head = null;
                this.tail = null
            }else{//リンクリストの長さが1ではない
                if(位置 === 0){
                // 最初の場所を削除します this.head.next.prev = null;
                    this.head = this.head.next;
                }そうでない場合(位置 === this.length-1){
                    this.tail.prev.next = null;
                    this.tail = this.tail.prev;
                }それ以外{
                    var インデックス = 0;
                    while(インデックス++ <位置){
                        現在の = 現在の.次;
                    }
                    現在のページを次に示します。
                    現在の次の前;
                }
            }
            this.length -=1;
            現在のデータを返します。
        }
    }

検証: 位置 3 のデータを削除します。

リスト.削除(3)
       console.log("list.removeAt(3) は:");
       console.log(リスト.toString());

結果は次のとおりです。

ここに画像の説明を挿入

検証成功

8. remove(要素): リストから項目を削除する

indexOf(element)メソッドに従ってリンク リスト内の要素の位置を直接取得し、 removeAt(position)メソッドに従ってその要素を削除できます。

 DoublyLinkedList.prototype.remove = function(data){
        var index = this.indexOf(データ);
        this.removeAt(index) を返します。
    }

検証: データがrcであるノードを削除します。

リストを削除します('rc');
       console.log("list.remove('rc') は:");
       console.log(リスト.toString());

ここに画像の説明を挿入

9. isEmpty(): リンクリストが空かどうかを判定する

リンク リスト内の要素数がゼロかどうかを直接判断します。ゼロの場合は空なので true を返します。それ以外の場合は空ではないので false を返します。

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

確認する:

console.log("リンクリストは空ですか: "+list.isEmpty());     

ここに画像の説明を挿入

10. size(): リンクリストに含まれる要素の数を返します

リンクリストの長さは要素の数です。

DoublyLinkedList.prototype.size = function(){
        this.length を返します。
    }

確認する:

 console.log("リンクリスト内の要素数は: "+list.size());

ここに画像の説明を挿入

以上がJavaScriptの双方向リンクリストの実装プロセス分析の詳細です。JavaScriptの双方向リンクリストの詳細については、123WORDPRESS.COMの他の関連記事に注目してください。

以下もご興味があるかもしれません:
  • JavaScript データ構造 双方向リンクリスト
  • JavaScript 双方向リンクリスト操作例の分析 [作成、追加、検索、削除など]
  • JS 双方向リンクリストの実装と使用例 (実装に前の属性を追加)
  • JavaScript データ構造における双方向リンクリストと双方向循環リンクリストの実装
  • JavaScript データ構造の双方向リンクリストの定義と使用例

<<:  CSS 水平方向の中央揃えと最大幅の制限

>>:  MySQL 接続とコレクションの簡単な分析

推薦する

面接官がmysqlのcharとvarcharの違いを尋ねたとき

目次charとvarcharの違いcharとvarcharの違い上記は、MySQL における cha...

CSS の新機能には、コントロールページの再描画と再配置の問題が含まれています

新しい CSS プロパティ contain を紹介する前に、読者はページの再描画と再配置が何であるか...

XHTML と CSS の Web ページ作成の問題に対する解決策

XHTML CSS ページ制作中に遭遇する問題の解決策は、解決策と呼ぶには少々大げさです。せいぜい、...

Vueモバイル端末は画面上で指をスライドさせる方向を判定する

vueモバイル端末は、画面上で指をスライドさせる方向を判断します。具体的な内容は次のとおりです。これ...

MySQLデータベース移行により、大量のデータを迅速にエクスポートおよびインポートできます

データベースの移行は、よく遭遇する問題です。データ量が少ない場合、移行は基本的に問題になりません。実...

QT が MYSQL データベースに接続するための詳細な手順

最初のステップは、対応するデータベースモジュール(sql)をプロジェクトファイル( .pro )に追...

KVM 仮想化のインストール、展開、管理のチュートリアル

目次1.kvmの展開1.1 kvmのインストール1.2 kvm Web管理インターフェースのインスト...

Linux lsof コマンドの使用方法の詳細な説明

lsof (開いているファイルのリスト) は、プロセスによって開かれたファイルを表示するツールです。...

CentOS7 システムでスワップを増やす方法の例

序文スワップは、ディスク上にある「仮想メモリ」の一部である特殊なファイル (またはパーティション) ...

React Routerの歴史について簡単に説明します

React Router を理解したいなら、まず歴史を理解する必要があります。より具体的には、Rea...

Linux コマンドで .sql ファイルをエクスポートおよびインポートする方法

この記事では、Linux コマンドを使用して .sql ファイルをエクスポートおよびインポートする方...

vue3 で vue-router を使用するための完全な手順

序文ルーティングの管理は、ほとんどのシングルページ アプリケーションにとって不可欠な機能です。 Vu...

nginxアクセス制御の実装例

高性能で軽量なウェブサービスソフトウェアであるNginxについて高い安定性 システムリソースの消費量...

Vueはアップロードコンポーネントを実装します

目次1. はじめに2. アイデアファイルをアップロードする2つの方法3. ライフサイクル4. コード...

LeetCode の SQL 実装 (177. 給与が N 番目に高い)

[LeetCode] 177. 最も高い給与従業員テーブルからn番目に高い給与を取得する SQL ...