リンクされたリストの長さを調べる JavaScript プログラム

リンク リストは、長さを可変できる線形データ構造です。リンク リストの長さは変更できます。これは、配列内の配列の長さが変化するという問題です。変えられない。この記事では、コードを実装し、エッジ ケースをチェックすることで、指定されたリンク リストの長さを調べます。この記事では while ループとクラスの概念を使用します。

問題の紹介

この問題では、リンク リストが与えられています。まず、クラスを使用してリンク リストを作成し、次に、指定されたリンク リストの長さを見つける必要があります。リンク リストの長さは変化する可能性があるため、特定のコード ポイントでのリンク リストの長さを調べます。

2 つの方法を使用します。1 つは while ループを使用した直接反復方法、もう 1 つは指定されたリンク リストの長さを見つけるための再帰的方法です。

反復方法

このメソッドでは、最初にクラスを使用してリンク リストを作成し、リンク リストの構造を提供します。ヘッダーとデータを渡すだけでリンク リストに値を追加するプッシュ関数などのいくつかの関数を定義します。

このプロセスでは、while ループ、リンク リストの先頭または開始ノード、およびリンク リスト内のノードの数 (指定されたリンク リストの長さ) をカウントする変数を使用します。

上記の方法では、余分なスペースを使用せず、リンク リストを 1 回だけ走査します。したがって、上記の方法の時間計算量は O(N) (N はリンク リストのサイズ)、上記の方法の空間計算量は O(1) です。

再帰的メソッド

このメソッドでは、上記のメソッドと同じ手順に従ってリンク リストを作成します。主要なタスクでは再帰的メソッドを使用します。

関数自体とは異なるパラメーターと特定の基本条件を指定して同じ関数を呼び出すことを再帰と呼びます。このメソッドでは、リンク リストの先頭を使用して関数を呼び出し、その関数から現在のノードの次のノードを引数として関数を再度呼び出します。再帰呼び出しの場合は戻り値として 1 が返され、最初の呼び出しで結果が返されます。コードを見てみましょう -

時間と空間の複雑さ

再帰的手法の時間計算量は O(N) です。ここで、N は指定されたリンク リストに存在するノードの数です。合計 N 回の呼び出しがあり、呼び出しごとに現在のノード スタックを維持する必要があるため、上記のコードの空間複雑さは O(N) です。

このチュートリアルでは、コードを実装し、エッジケースを研究することによって、指定されたリンク リストの長さを見つける方法を学びました。最初のメソッドではこの記事の while ループとクラスの概念を使用し、2 番目のメソッドでは長さを求めるために再帰的メソッドを使用しました。どちらのメソッドの時間計算量は O(N) (N はリンク リストの長さ) ですが、再帰的メソッドの空間計算量はスタック サイズのため O(N) です。

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