リンクされたリストにノードを挿入する JavaScript プログラム

#リンク リストはさまざまな長さのデータ構造であり、任意のノードを削除したり、リンク リストに追加したりできます。このチュートリアルでは、空間と時間の計算量を伴うリンク リストにノードを挿入するための完全なプログラムを実装します。まず問題文を理解しましょう。

問題の紹介

この問題では、リンク リストが与えられており、リンク リスト内のノードを追加または削除することでリンク リストのサイズを変更できるため、リンク リストにノードを追加または挿入します。

リンク リストでは、3 つの異なる場所 (先頭ノード、最後のノードの後、リンク リストの中央) に新しいノードを追加できます。たとえば、指定されたリンク リストは -

です。

1 -> 2 -> 3 -> 4 -> 5 -> null の場合、値 9 のランダムなノードを追加する必要があります。したがって、 -

など、ノードを追加する必要がある状況が数多くあります。

• 先頭にノードを追加 - 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

• 中間にノードを追加 - 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null

• 最後にノードを追加 - 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null

次のタスクを達成する方法を見てみましょう -

リンクリストの先頭にノードを追加します

＃＃＃例＃＃＃

リンク リストの先頭にノードを追加するには、新しいノードを作成し、リンク リストの先頭を次のノードとして新しいノードに渡し、次に先頭を新しいノードに移動して、新しいノードを追加する必要があります。ノード リンクされたリストの先頭にノードを追加します。

リーリー

上記のコードの時間計算量は O(1) です。これは、ポインターを移動するだけで済み、追加のスペースが使用されないため、スペース計算量は O(1) になります。

リンクリストの途中にノードを追加します

＃＃＃例＃＃＃

リンク リストの途中にノードを追加するには、リンク リストの新しいノードを新しいノードの次のノードとして追加する前に、新しいノードを作成してそのノードを渡す必要があります。これにより、新しいノードを中央のリンクリストに追加します。

リーリー

新しいノードを追加する必要があるノードに移動する必要があるため、上記のコードの時間計算量は O(N) です。余分なスペースを使用していないため、上記のプロセスのスペース複雑さは O(1) です。

リンクリストの最後にノードを追加します

＃＃＃例＃＃＃

リンク リストの最後にノードを追加するには、新しいノードを作成し、末尾ノードの後に​​そのノードを追加し、末尾ノードを次のノードに移動する必要があります。

リーリー

上記のコードの時間計算量は O(1) です。これは、ポインターを移動するだけで済み、追加のスペースが使用されないため、スペース計算量は O(1) になります。

＃＃＃結論は＃＃＃

上記のチュートリアルでは、3 つの可能な方法で既存のリンク リストに新しいノードを追加する方法を学びました。説明と時間と空間の複雑さを伴う正しいコードを見てきました。リンク リストの中央にノードを追加するには O(N) 時間がかかりますが、他の 2 つの場合の時間計算量は O(1)、3 つの可能性すべてで空間計算量は O(1) です。

以上がリンクされたリストにノードを挿入する JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。