リンクされたリストから k 番目のインデックスを 1 回のパスで削除する おかえりなさい。別の問題を解決する必要があります。今日は、リンクされたリストとその要素の削除を扱います。リンク リストとは何かについて少し説明し、リンク リストを作成して、そこから要素を削除する方法を見ていきます。 始める前に、通常の免責事項を述べておきます。 これらの問題は、購読できる素晴らしいニュースレター「Dailycoding 問題」によって提供されます。 。ぜひチェックして、あなたの課題も解決してみてください！ ここ 私は専門プログラマーではありません。自分のショットを共有するのが好きなただの人です。アルゴリズムに対してより優れた、またはより高速なソリューションがある場合は、コメント欄に送信してください。これについてもう少し詳しく知りたいです! 面倒なことはもう十分です。問題に移りましょう！ この問題は最初に Amazon によって尋ねられました を指定すると、リストの末尾から k 番目のノードを削除し、リストの先頭を返します。 リンク リストと整数 k   はリストの長さより小さいことが保証されます。 k これを 1 回のパスで実行します。 それでは、ここで何が起こっているのかを少し説明しましょう。リンクされたリストと、リストから削除するインデックス要素 が与えられています。その後、リンクされたリストの先頭を返す必要があります。 k 最後に、これらすべてを 1 回のパスで実行する必要があります。つまり、リストを複数回ループすることはできません。 また、インデックス がリストに ことも保証されているため、インデックス k がリストの実際の長さを超えているかどうかをチェックする必要はありません。 k 含まれている  Go の構文はこの種の作業に最適であり、同時に非常に理解しやすいため、今日は Go を使用してアルゴリズムを構築します。 最初から始めましょう。単純なリンクされたリストを作成します。 リンクされたリスト リンク リストの背後にある概念は非常に単純です。リンク リストはオブジェクト (通常は と呼ばれます) で構成されるリストであり、各ノードには (ノードに実際に含まれる何か) と次のノードへの 少なくとも 2 つのプロパティが必要です。 ノード 値 リンクという 通常、 、あるノードから別のノードにジャンプするためのリンクとして使用されます。 ポインタは また、リストの最初のノードは通常リストの と呼ばれ、問題によって返されるように求められるノードでもあります。 先頭 以下にグラフィカルな例を示します。  左側の最初のノードはリストの先頭であり、その値 v0 とリストを次のノード にリダイレクトするメモリ ポインタ が含まれています。次のノード には、その値と次のノードへのポインタ などが含まれます。 n1 P(n1) n₁ P(n₂) もちろん、最後のノードには指すものが何もないため、そのポインターの値は になります。 null 作成するコードを見てみましょう。   https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true コードは非常に単純です。内部ノード用とリンク リスト用の 2 つの構造を作成します。 先ほど見たように、ノードには 2 つのプロパティがあります。つまり、プロパティ と、次のノードへのポインタとして タイプを保持するプロパティ です。 Value *Node Next リンク リスト。リンク リストを「初期化」するための構造。リストの というプロパティが 1 つだけあります。 Head その後、メイン関数でリストを初期化し、その頭にランダム値 10 のノードを与えます。 リンク リストを理解するための重要な点は、  ノードはタイプ 、本質的に プロパティ これに次のノードが含まれるという です。この最後のノードには、次のノードにジャンプするための プロパティが設定されます。 Head Node であるため Next を持ち 、 Head Next いくつかのノードをリストに追加すると、すべてがより明確になるので、実際にやってみましょう。選択肢は 2 つあります。 面倒な作業である手動で行うか、リンク リスト クラスのメソッドを作成してノードを追加するかのどちらかです。それをチェックしよう！ 非常に ノードの追加: 変装した可変リスト プログラミング経験がほとんどない場合でも、ほぼすべてのプログラミング言語で、最初に聞いたことがある概念の 1 つは、 と リストの違いです。 可変リスト 不変 名前が示すように、 。代わりに、不変 。しかし、なぜそうなるのでしょうか？ 変更可能なリストは、操作して要素を追加できるリストです のサイズは固定されており、新しい要素を追加することはできません 不変リストは ます。つまり、その要素は 。3 つの要素のリストの場合、最初の要素が 0x00 に格納されている場合、2 番目の要素は 0x01 に、最後の要素は 0x02 に格納されます。 メモリ内で連続してい メモリに順番に格納されます  CPU がメモリ インデックスを 1 つずつ呼び出すだけなので、Python で固定配列、不変リスト、またはタプルを反復処理するのが非常に速いのはこのためです。 一方、可変リストは最初に初期化されたときのみメモリ内で連続します。その時点で、要素が追加されると、それらはもはや連続的ではなくなります。では、どうすればそれらをループできるでしょうか? 、それによって to 要素が追加されるなどです。 最初の開始の最後の要素には、その要素の後に追加されたポインタがあり はい、可変リストは実際には、偽装されたリンク リストであることがよくあります。 それでは、コードを見てみましょう。   https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true リンク リストのメソッドにメソッド 追加しました。ノードを追加するプロセスは次のようになります。 AddNode まず、  値を という変数に保存します。 Head current 次に、次のノードが null になるまで、毎回次のノードで 変数を更新するリンク リストをループします。 current 現在いるノードに null ポインターがあると、リストの最後のノードにいることがわかります。 最後に、この最後のノードを新しいノードと新しい値で更新します (この新しいノードの ポインターを空白のままにすると、null に設定されます)。 Next このプロセスを図的に表すと次のようになります。   main 関数でこのメソッドが正しく機能していることを確認し、リンク リスト内のノードの値を出力します。 ノードの削除 ここで最後の部分と問題の解決策を説明します。正しいインデックスを持つノードを削除します。まず、リンク リストからノードを削除するとはどういう意味でしょうか?考えてみると、 。 リンク リスト内のノードは、前のノードに接続されている場合にのみ存在します たとえば、n-1ᵗʰ の 値に null を与えると、nᵗʰ 値をリストから切り離すことができます。  Next 削除したい要素が最後の要素ではない場合はどうすればよいでしょうか?そうですね、 できます。  前の要素を次の要素に接続することで、要素のリンクを解除 したがって、kᵗʰ 要素を削除するには、k-1ᵗʰ 要素を見つけて、それを k+1ᵗʰ ノードにリンクする必要があります。 を保存する必要があります。 前のノード (k-1ᵗʰ) 明らかに、 。linkedlist  のようなものを試してみると、エラーが発生するだけです。ただし、これを考慮すると、リストの先頭をインデックス 0、次のノードをインデックス 1 などとみなすことができ、以前と同様にノードをループすることもできます。 リストに直接インデックスを付けることはできません linkedlist[n] そこで私たちができることは、現在いるノードを追跡する を実装することです。 カウンター それではコーディングしましょう。   https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true   属性を受け入れる 関数を見てみましょう。その後、3 つの変数を初期化します。 index RemoveNode    、前のノードを保持します previousNode  、ループ中に現在いるノードを保持します。 current    、最初は 0 に等しく、リスト上の位置を保持します。 counter ここでは最初の if ブロックをスキップし、代わりに for ループに集中しましょう。  変数が より厳密に小さくなるまでループを開始します。各ループはその後 counter index 、前のノードを現在のノードで更新し、現在のノードとカウンタの更新に進みます。     。次へ ループが中断すると、 目的のインデックスの直前のノードにいることを意味します。 必要なのは、前のノードのポインタ prev.Next 、リスト内のこのノードの次のノードで更新することだけです。 current.Next になります 。最後に、リンクされたリストの先頭を返します。 ここで、削除するインデックスが 0 のインデックスを持つヘッドである場合はどうなるでしょうか?ループは および で開始されるため決して開始されず、条件は即座に false になります。この最初のケースは、先頭の if ブロックで管理できます。 counter = 0 index = 0 基本的に、インデックスが 0 の場合、リンクされたリストの先頭をその隣のノードで直接更新して返すことができます。特に 31 行目に注目してください。 Go は、他の多くの言語と同様に、  。これは、関数が、渡し の を保持することを意味します。 。 value によって属性を関数に渡します ている実際のオブジェクトではなく、渡されたオブジェクト コピー この概念は、次の例で明確に示されています。   package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited. 属性として渡された値のメモリアドレスを出力する関数を作成します。次に、main 関数で変数 a を作成し、そのメモリ アドレスを出力します。次に、同じ変数を関数に渡し、そのメモリ アドレスを出力します。 ご覧のとおり、試してみると結果は異なります。これは、属性が値として関数に渡されるためです。つまり、関数に渡すためだけに のコピーが作成されることになります。 a リンク リストに戻って、上記と同じ問題の実際の先頭を取得するには、ポインターを使用する必要があります。   に到達するには を呼び出し、  必要があります したがって、「実際の」 ll.Node 、そのポインタ *ll.Node *ll.Node = *ll.Node.Next を使用してさらに移動する 。  main 関数では、メソッドの呼び出し (たとえば、  および の呼び出し) を追加し、ノード 0 とノード 2 が欠落している結果を確認できます。 ll.RemoveNode(0) ll.RemoveNode(2) 結論 最後までやり遂げました！ ここまで読んでいただいた方には、心より感謝申し上げます。 1 つか 2 つの「いいね！」を残して記事を共有していただければ、一日が楽しくなり、記事を書き続けるのに役立ちます。 それではまた次の記事でお会いしましょう。いつも読んでいただきありがとうございます。 ニコラ

Read My Stories

このオーディオは、ストーリーの元の言語で制作されています。

毎日のコーディングの問題: 1 回のパスでリンクされたリストから k 番目のインデックスを削除する

About Author

コメント

ラベル

この記事は

Related Stories

海を航海する: データレイクを使用した本番環境レベルの RAG アプリケーションの開発

暗号通貨の成長: 効果的なユーザーペルソナの作成

ユニークなエコシステムを支えるビットコインUTXOのモデル

Claude Sonnet 3.5 システムプロンプトの漏洩: 法医学的分析

海を航海する: データレイクを使用した本番環境レベルの RAG アプリケーションの開発

暗号通貨の成長: 効果的なユーザーペルソナの作成

ユニークなエコシステムを支えるビットコインUTXOのモデル

Claude Sonnet 3.5 システムプロンプトの漏洩: 法医学的分析

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps