Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. JavaScript
Code

JavaScriptによるデータ構造:片方向リンクリストと二重リンクリスト

by
Length:LongLanguages:
This post is part of a series called Data Structures in JavaScript.
Data Structures With JavaScript: Stack and Queue
Data Structures With JavaScript: Tree

Japanese (日本語) translation by Hakima Madani (you can also view the original English article)

Final product image
What You'll Be Creating

2 つの最も一般的にコンピューター科学のデータ構造は、リンクリストと二重にリンクされたリスト教えた。

これらのデータ構造を教えていた、私はそれらを概念化する類似の私の同等者を尋ねた。 何を聞いていた食料品や電車の一覧など、いくつかの例。 私は最終的に学んだ、これらの類似した正確です。 食料品のリストがより類似していたキュー列車はより配列に類似していた。

私は最終的に一重リンクのリストと二重にリンクされたリストを正確に記述の類似性を発見するより多くの時間が経つにつれ: スカベン ジャー ハント。 スカベン ジャー ハントとリンクのリストとの関係について興味のある方は場合、下記をお読みの答え!

シングル リンク リスト

コンピューター サイエンスの一重リンクのリストは、リンクされたノードのシーケンスを保持するデータ構造です。 ターンでは、各ノードには、データと別のノードをポイントすることができます、ポインターが含まれています。

一重リンクのリストのノードは、スカベン ジャー ハントの手順に非常に似ています。 各ステップにはメッセージが含まれています (例:「に達したフランス」) とステップ (例えば、「これらの緯度と経度の座標を訪問」) へのポインター。 私たちはステップのシーケンスを形成するこれらの個々 のステップのシーケンスを起動、スカベン ジャー ハントをつくっています。

一重リンクのリストの概念モデルがあるので、一重リンクのリストの操作を見てみましょう。

一重リンクのリストの操作

片方向リンクリストにはノードが含まれているため、片方向リンクリストとは別のコンストラクタにすることができるため、NodeSinglyListの両方のコンストラクタの操作について概説します。

Node

  • dataは値を格納します。
  • nextはリスト内の次のノードを指します。

SinglyList

  • _lengthはリスト内のノード数を取得します。
  • headはノードをリストの先頭として割り当てます。
  • add(value) は、リストにノードを追加します。
  • searchNodeAt(position) は、n 位置の私達のリストのノードを検索します。
  • remove(position) は、リストからノードを削除します。

一重リンクのリストの実装

この実装では、最初にNodeという名前のコンストラクタを定義し、次にSinglyListという名前のコンストラクタを定義します。

Nodeの各インスタンスには、データを格納する機能と別のノードを指す機能が必要です。 この機能を追加するために、datanextの2つのプロパティをそれぞれ作成します。

次に、我々 は SinglyListを定義する必要があります。

SinglyListの各インスタンスには、_lengthheadの2つのプロパティがあります。 前者が割り当てられます。 リスト内のノード数リストの頭に後者の点-リストの先頭にあるノード。 SinglyListのすべての新しいインスタンスはノードを含まないので、headのデフォルト値はnullで、_lengthのデフォルト値は0です。

シングル リンク リストのメソッド

必要があります追加できるメソッドを定義する、検索し、一覧からノードを削除します。 ノードを追加することをから始めましょう。

3 の 1: add(value)

素晴らしい、今リストにノードを追加する機能を実装してみましょう。

私たちのリストにノードを追加すると、多くのステップが含まれます。 私たちは私たちのメソッドの先頭から始めましょう。 add(value)の引数を使用して、nodeという名前の変数に割り当てられるNodeの新しいインスタンスを作成します。 我々 はまた currentNode をという名前の変数を宣言し、私達のリストの _head に初期化します。 一覧にノードがない場合、headの値は null です。

これ以降のコードでは、2 つのユース ケースを取り扱っています。

最初の使用例は、空のリストにノードを追加すると見なします。 headがノードを指していない場合は、nodeをリストの先頭として割り当て、リストの長さを1つ増やしてnodeを返します。

2 つ目の使用例は、空でないリストにノードを追加すると見なします。 whileループに入り、各繰り返しの間に、currentNode.nextが別のノードを指しているかどうかを評価します。 (最初のイテレーションの中に currentNode は、リストの先頭を指す常に)。

答えが「いいえ」の場合、nodecurrentNode.nextに割り当ててnodeを返します。

While の体内に入る我々 の答えが yes の場合ループ。 体の中に currentNode.next を currentNode 再割り当ています。 CurrentNode.next はもはや別のノードを指すまで、このプロセスが繰り返されます。 つまり、currentNode 最後の私達のリストのノードを指します。

While ループをブレークします。 最後に、nodecurrentNode.nextに代入し、_lengthを1つ増やしてからnodeを返します。

3 の 2: searchNodeAt(position)

私たちのリストにノードを追加できますが、我々 は私達のリスト内の特定の位置にあるノードを検索できません。 この機能を追加して、positionという名前の引数を受け入れるsearchNodeAt(position)という名前のメソッドを作成しましょう。 引数は、n-positionの私達のリストのノードを示す整数をされる予定です。

ifステートメントは最初のユースケースをチェックします。無効な位置が引数として渡されます。

SearchNodeAt(position) が有効で、我々 は 2 番目の使用例を達するインデックスが渡された場合、while ループします。 whileループを繰り返すたびに、currentNode(最初はheadを指す)がリスト内の次のノードに再割り当てされます。 この繰り返しは、count が配置されるまで続けています。

ループが最終的に壊れる currentNode が返されます。

3 の 3: remove(position)

我々 が作成されます最後のメソッドは、remove(position) という名前です。

Remove(position) の実装には、3 つのユース ケースが含まれます。

  1. 無効な位置が引数として渡されます。
  2. (リストのhead) の 1 つの位置が引数として渡されます。
  3. 存在しない位置 (最初の位置ではなく) が引数として渡されます。

最初と 2 番目の使用例を処理する最も簡単であります。 最初のシナリオに関しては、リストが空または存在しない位置が渡された場合、エラーがスローされます。

2番目のユースケースは、リスト内の最初のノードの削除を処理します。これもheadです。 これは、場合は、次のロジックが発生します。

  1. headcurrentNode.nextに再割り当てされます。
  2. deletedNode が指す currentNode
  3. currentNodenullに再割り当てされます。
  4. リストの_lengthを1つ減らします。
  5. deletedNode が返されます。

3 番目のシナリオは理解困難です。 複雑さはwhileループの各繰り返しの間に2つのノードを追跡する必要性から生じます。 ループの各反復処理の中には、削除するノードの前にノードと削除するノードの両方を追跡します。 ループに達する位置のノードを削除したい、ループが終了します。

この時点で、我々 は 3 つのノードへの参照を保持する: beforeNodeToDeletenodeToDelete、および deletedNodenodeToDeleteを削除する前に、nextの値をbeforeNodeToDeleteの次の値に代入する必要があります。 この手順の目的が不明確と思われる場合、自分自身を思い出させる我々 がリンクされているノードのリストを持っています。だけのノードの削除は、一覧の最初のノードからのリンク リストの最後のノードを分割します。

次に、我々 は nodeToDeletedeletedNode を割り当てます。 その後、我々 は null、リストの長さを 1 だけデクリメントし deletedNode を返す nodeToDelete の値を設定します。

一重リンクのリストの完全な実装

私たちのリストの完全な実装はこちらです。

単独に二重

素晴れらしい、一重リンクのリストの実装は完了です。 追加、削除、およびメモリの連続領域を占めるリスト内のノードを検索するデータ構造を使用できます。

ただし、現時点で全事業はリストの先頭から開始し、リストの末尾に実行します。 言い換えれば、彼らは双方向です。

双方向に私たちの操作し場合があります。 このユース ケースを考慮する場合は、二重にリンクされたリストをだけ説明が。

二重にリンクされたリスト

二重にリンクされたリストは、一重リンクのリストのすべての機能を受け取り、リスト内の双方向運動のため拡張します。 私たちことができますを通過する他の言葉では、リストの最後のノードに一覧の最初のノードからのリンクのリスト我々 は、一覧の最初のノードにリストの最後のノードからたどることができます。

このセクションでは、二重にリンクされたリストと一重リンクのリストの違いについて主に私たちの焦点を維持します。

二重にリンクされたリストの操作

リストには、NodeDoublyListの2つのコンストラクタが含まれます。 業務の概要を説明しましょう。

Node

  • dataは値を格納します。
  • nextはリスト内の次のノードを指します。
  • previousは、リスト内の前のノードを指します。

DoublyList

  • _lengthはリスト内のノード数を取得します。
  • headはノードをリストの先頭として割り当てます。
  • tailはノードをリストの末尾として割り当てます。
  • add(value) は、リストにノードを追加します。
  • searchNodeAt(position) は、n 位置の私達のリストのノードを検索します。
  • remove(position) は、リストからノードを削除します。

二重にリンクされたリストの実装

いくつかのコードを書きなさい!

実装するために、Nodeという名前のコンストラクタを作成します。

二重にリンクされたリストの双方向移動を作成するには、プロパティ リストの両方の方向を指す必要があります。 これらのプロパティには、previousnextという名前が付けられています。

次に、DoublyListを実装して、_lengthhead、およびtailの3つのプロパティを追加する必要があります。 一重リンクのリストとは異なり二重にリンクされたリスト リストの両方の開始とリストの末尾を参照しています。 DoublyListのすべてのインスタンスはノードなしでインスタンス化されるため、headtailのデフォルト値はnullに設定されています。

二重にリンクされたリストのメソッド

我々 は今以下の手法を探求する: add(value)remove(position)、および searchNodeAt(position)。 一重リンクのリストのために使用されたすべてのこれらのメソッドしかし、彼らは双方向動きに書き直す必要があります。

3 の 1: add(value)

このメソッドでは、2 つのシナリオがあります。 まず、リストが空の場合は、追加するノードのheadtailに割り当てます。 第二に、一覧にノードがある場合、リストの末尾を見つけるし、tail.next; 追加されるノードに割り当てる同様に、我々 は双方向運動のための新しい尾を構成する必要があります。 我々 は、つまり、元の尾に tail.previous を設定する必要があります。

3 の 2: searchNodeAt(position)

SearchNodeAt(position) の実装は、単一リンクのリストと同じです。 それを実装する方法を忘れてしまった場合下記私が含めました。

3 の 3: remove(position)

このメソッドは、最も挑戦的な理解になります。 私はコードを表示し、それを説明します。

remove(position) は、4 つのユース ケースを処理します。

  1. Remove(position) の引数として渡される位置非存在であります。 この場合、我々 は、エラーをスローします。
  2. Remove(position) の引数として渡される位置は、一覧の最初のノード (head) です。 この場合、deletedNodeheadに割り当ててから、headをリスト内の次のノードに再割り当てします。 この瞬間、私たちは私たちのリストにある 1 つ以上のノードを考慮しなければなりません。 答えがnoの場合、headnullに割り当てられ、if-else文のif部分に入ります。 ifの本体では、tailnullに設定する必要があります。つまり、空の二重リンクリストの元の状態に戻ります。 リストの最初のノードを削除し、リストに複数のノードがある場合は、if-else文のelseセクションに入ります。 この場合、headpreviousのプロパティを正しくnullに設定する必要があります。リストの先頭の前にノードはありません。
  3. Remove(position) の引数として渡される位置はリストの末尾です。 まず、deletedNodetailに割り当てます。 次に、tailはtailの前のノードに再割り当てされます。 3番目に、新しい末尾にはそれ以降にノードがなく、nextの値をnullに設定する必要があります。
  4. ロジックよりも、コードの各行に取り組みますので、多くはここで起きています。 currentNodeがremove(position)への引数として渡される位置にあるノードを指していると、whileループを中断します。 この瞬間、私たちは nodeToDelete 後のノードに beforeNodeToDelete.next の値を再割り当てし、逆に、我々 は afterNodeToDelete.previousnodeToDelete する前にノードの値を再割り当ています。 つまり、削除されたノードへのポインターを削除し、それらを正しいノードに再割り当ています。 次に、我々 は nodeToDeletedeletedNode を割り当てます。 最後に、我々 は nullnodeToDelete を割り当てます。

最後に、私たちは私たちのリストと戻り値の deletedNode の長さをデクリメントします。

二重にリンクされたリストの実装を完了します。

ここでは、全体の実装です。

結論

我々 は、この資料の情報の多くをカバーしています。 混乱のいずれかが表示された場合、もう一度、読んでし、コードで実験します。 最終的にあなたに理にかなって、誇りに感じてください。 シングル リンク リストと二重にリンクされたリストの謎を発見されているだけ。 これらのデータ構造を追加するにはあなたのコーディング ツール ベルトに!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.