[Powered by Google Translate] プログラミングでは、私たちはしばしば、値のリストを表現する必要がある セクション内の生徒の名前など または最新のクイズでそのスコア。 

C言語では、配列を使用することができます宣言 リストを格納します。 それは、リストの要素を列挙するのは簡単だ 配列に格納され、あなたはアクセスする必要がある場合 またはi番目のリスト要素を変更する いくつかの任意のインデックスIのために、 それは、一定の時間で行うことができます しかし配列は、あまりにも欠点があります。 

我々は彼らを宣言するとき、我々は言っている必要 彼らがどのようにビッグアップフロント、 彼らは保存することができますどのように多くの要素、つまり、 とどのように大きなこれらの要素であり、その種類によって決定される。 例えば、int型ARR（10） 10個のアイテムを格納することができます それはint型のサイズです。 

我々は、宣言の後に配列のサイズを変更することはできません。 我々はより多くの要素を格納したい場合は、新しい配列を作らなければなりません。 この制限が存在する理由は、私たちのことである プログラムでは、配列全体を格納 メモリの連続するチャンクとして。 これは我々が配列に格納されたバッファであると言う。 他の変数があるかもしれません 配列のすぐ隣に位置して メモリ内に、私たちはできません 単に配列を大きくする。 

時には我々は、配列の高速なデータアクセス速度を犠牲にしたいのですが もう少し柔軟性を。 リンクリスト、別の基本的なデータ構造を入力してください あなたと同じように慣れていない場合があります。 高レベルでは、 リンクリストは、ノードのシーケンスにデータを格納 リンクで相互に接続されていること、 したがって、その名前 'リンクされたリスト。' デザインで我々が見ていくように、この差 別の長所と短所につながる 配列より。 

ここでは、整数の非常に単純なリンクリストのためのいくつかのCのコードは次のとおりです。 あなたは、私たちは、各ノードを代表してきたことがわかります 2つのことを含む構造体をリストとして、 'val'の呼ばれる格納する整数 リスト内の次のノードへとリンク 我々はと呼ばれるポインタとして表す '隣接しています。' このように、我々は全体のリストを追跡することができます 第一のノードへのただ一つのポインタを使用して、 それから私達は次のポインタをたどることができ 第二のノードに、 第三のノードに、 第四ノードに、 というように、我々はリストの最後に到達するまで。 

あなたは、これがあります1の利点を見ることができるかもしれません 静的な配列構造上 - リンクされたリストを使用して、 我々は完全にメモリの大きな塊を必要としません。 リストの第一のノードは、メモリ内のこの場所に住むことができる そして第二ノードはこっちすべての方法かもしれない。 メモリにそれらがどこにいる我々は、すべてのノードに関係なく取得することはできません 第一のノードから開始されるため、各ノードの次のポインタ 次に行き場所を正確に教えてくれる。 

さらに、我々は前を言う必要はありません どのように大きなリンクリストは、我々は静的な配列で行う方法になるだろう 我々はリストにノードを追加し続けることができるので、 限りスペースが新しいノードのメモリのどこかに存在だとして。 したがって、リンクされたリストは、動的にサイズを変更するのは簡単です。 後でプログラムの中で我々はより多くのノードを追加する必要がある、と言う 私たちのリストに変換します。 その場で私たちのリストに新しいノードを挿入するには、 我々がしなければならないすべては、そのノードのメモリを割り当てている データ値のウンチ、 我々は適切なポインタを調整することによって、先をして、それを配置します。 

たとえば、我々はその間にノードを配置したい場合 リストの2番目と3番目のノードは、  我々はすべてで2nd、3rdのノードを移動する必要はありません。 我々はこの赤のノードを挿入していると言う。 私たちがしなければならないと思いますすべてが、新しいノードの次のポインタが設定されている 第三のノードを指すように その後第二のノードの次のポインタを配線し直す 私たちの新しいノードを指すように変更します。 だから、私たちはその場で私たちのリストのサイズを変更できます 我々のコンピュータは、インデックスに依存していないので、 むしろそれらを格納するポインタを使用してリンクする。 

しかし、欠点は、リンクリスト つまり、静的配列とは異なり、 コンピュータは、単にリストの途中にジャンプすることはできません。 コンピュータは、リンクリスト内の各ノードを訪問しなければならないので 次のいずれかに得るために、 それは、特定のノードの検索に時間がかかるために起こっている それが配列の場合と比べて。 リスト全体をトラバースするに比例して時間がかかる リストの長さと、 またはO（n）の漸近記法インチ 平均して、任意のノードに到達 また、nに比例する時間がかかる。 

それでは、実際にいくつかのコードを書いてみよう それはリンクされたリストと連携して動作します。 それでは、例として、整数の連結リストが欲しいと言う。 我々は再び我々のリスト内のノードを表すことができます 2つのフィールドを持つ構造体として、 'val'の呼ばれる整数値 リストの次のノードへの、次のポインタ。 まあ、十分に簡単なように見える。 

Let 'sは、我々は関数を書きたいと言う 横断する外リストや版画 値は、リストの最後のノードに格納されている。 まあ、それは、我々は、リスト内のすべてのノードを横断する必要がありますことを意味し 最後の一つを見つけることが、我々は追加していないので か何かを削除すると、私たちは変更したくない リスト内の次のポインタの内部構造。 

そこで、我々は、トラバーサルのために特別にポインタが必要になるでしょう その我々は "クローラー"と呼んでいますよ それは、リストのすべての要素をクロールします 次のポインタのチェーンをたどって。 我々が保存されていたすべては、第一のノードへのポインタです。 リストまたは '頭'。 第一のノードに頭を指しています。 これは、型へのポインタノードの一つだ。 

リスト内の実際の第一のノードを取得するには、 我々は、間接参照するthisポインタを持っている 我々はそれを間接参照することができます前に、しかし、我々は確認する必要があります ポインタは最初のnullである場合。 それがnullである場合は、リストは空です そして我々は、リストが空であるため、メッセージをプリントアウトする必要があります 最後のノードがあるわけではありません。 しかし、みましょうリストが空でないと言う。 それがないなら、私たちは、リスト全体をクロールする必要があります 我々は、リストの最後のノードに到達するまで、 我々はリスト内の最後のノードを見ているかどうか、およびその方法を私たちは知ることができますか？ 

さて、ノードの次のポインタがnullである場合、 我々は終わりにしている知っている 最後に次のポインタが指すようにリスト内に、次のノードを持っていませんので。 それは、常にnullに初期化された最後のノードの次のポインタを保持すると良いでしょう 我々はリストの最後に到達したときに私たちに警告を標準化されたプロパティを持っています。 

だから、クローラー→次がnullである場合、 矢印構文は逆参照するためのショートカットであることを覚えている 構造体へのポインタは、次にアクセスして ぎこちないと同等、その隣にあるフィールド： （*クローラー）隣にあります。 かつて我々は、最後のノードを見つけた 我々は、クローラー→valを印刷したい 現在のノードの値 その我々が知っている最後のものである。 そうでなければ、我々はリスト内の最後のノードではまだいないのであれば、 我々は、リスト内の次のノードに移動する必要があります そして最後の一つだかどうかを確認します。 これを行うために、私達はちょうど私達のクローラー·ポインタを設定 現在のノードの次の値を指すように、 それは、リスト内の次のノードです。 これは、設定することによって行われ クローラー=クローラー→次へをクリックします。 その後、我々は、例えば、ループを使って、このプロセスを繰り返す 我々は最後のノードが見つかるまで。 だから、例えば、クローラーが頭を指していた場合、 我々は、クローラー→次を指すようにクローラを設定する これは、第一のノードの次のフィールドと同じです。 だから、今私達のクローラーは、第二ノードを指している そして、再び、我々は、ループでこれを繰り返す 我々は最後のノードを発見するまで、つまり、 どこのノードの次のポインタはnullに向いています。 そして我々はそれをそこに持っている、 我々は、リスト内の最後のノードを見つけた、その値を出力する 私達はちょうどクローラー→valを使用しています。 

トラバースはそれほど悪くはありませんが、挿入はどうでしょうか？ 貸し付けは、我々は第四の位置に整数値を挿入したいと言う 整数のリストに表示されます。 つまり、現在の第三と第四のノードとの間にある。 再び、我々はちょうどにリストを横断しなければならない 第三要素は、我々は後に挿入しているものを取得する。 そこで、我々は、リストをトラバースするには、もう一度クローラのポインタを作成する 私たちの頭のポインタがnullであるかどうかを確認してください それがない場合には、ヘッドノードでクローラポインタを指す。 そこで、我々は第一要素にいる。 私たちは、挿入する前に、2以上の要素を前方に行かなければならない ので、我々は、forループを使用することができます int型私= 1;のi <3; i + +が そしてループの各反復において、 1ノードで前方クローラポインタを進め 現在のノードの次のフィールドがnullかどうかをチェックすることによって、 それがないならば、次のノードにクローラポインタを移動 現在のノードの次のポインタと等しい値に設定することによって。 だから、私たちのためのループがそれをすると言うので、 二回、 私たちは、第三のノードに到達しました そして一度クローラポインタが後にノードに達している 私達は私達の新しい整数を挿入したい、 どのように我々は実際に挿入すればよいですか？ 

さて、私たちの新しい整数がリストに挿入する必要があります 自身のノード構造体の一部として、 これは実際にノードのシーケンスであるためです。 それでは、ノードへの新しいポインタを作ってみましょう '、new_node'と呼ばれる そして我々は今割り当てているメモリを指すように設定してください ノード自体のヒープ上に、 そして我々が割り当てることがどのくらいのメモリが必要なのでしょうか？ さて、ノードのサイズ、 我々は、我々は挿入する整数へのvalフィールドを設定したい。 レッツは6と言う。 今では、ノードは、私たちの整数値が含まれます。 それは、新しいノードの次のフィールドを初期化することもお勧めします NULLを指している場合は、 しかし今何？ 

我々は、リストの内部構造を変更する必要が リストの既存の中に含まれ、次のポインタ 3番目と4番目のノード。 次のポインタは、リストの順序を決定するので、 そして私達は私達の新しいノードを挿入しているので、 右側のリストの真ん中に、 それは少しトリッキーなことができます。 覚えている、これは、我々のコンピュータであり、 のみリスト内のノードの位置を知っている 前のノードに格納された次のポインタのため。 そこで、我々はこれまで、これらの場所のいずれかのトラックを失った場合 、私達のリストの次のポインタのいずれかを変更することで言う 例えば、私たちは変更と言う 第三ノードの横にあるフィールド ここでいくつかのノードを指すように設定します。 我々はしないので、我々は、運が悪いのでしょうね ここで、リストの残りの部分を見つけるために、任意のアイデアを持っている そしてそれは明らかに本当に残念だ。 だから、私たちは順番については本当に注意しなければならない 採用された場合は、挿入時に我々の次のポインタを操作します。 

だから、これを簡素化する、と言ってみましょう 私たちの最初の4つのノード ポインタのチェーンを表す矢印で、A、B、C及びDと呼ばれています ノードを接続すること。 だから、我々は、新しいノードを挿入する必要が ノードCとDの間で それは、正しい順序でそれを行うことが重要だし、なぜ私はあなたを紹介します。 

最初にそれを行うには間違った方法を見てみましょう。 ねえ、私たちは新しいノードがCの後に右来ている知っている、 それでは、Cの次のポインタを設定しましょう new_nodeを指すように変更します。 よし、大丈夫だ、我々だけで今まで完了する必要があります Dへの新しいノードの次のポインタポイントを作って、 しかし、どのように我々はそれを行うことができますが、待つのか？ Dがあった場所を教えてことができる唯一の​​事、 次のポインタは、以前は、Cに格納されていました しかし、我々はちょうどそのポインタを書き直し 新しいノードを指すように、 ので、私たちはもはや、Dはメモリ内にある任意の手掛かりを持っていない そして我々はリストの残りの部分を失ってしまった。 全然良い。 

だから、私たちはこの権利をどのように行うのですか？ まず、Dの新しいノードの次のポインタを指す さて、両方の新しいノードのとCの次のポインタ 同じノードA、D、を指している それは大丈夫です。 今、私たちは、新しいノードでのCの次のポインタを指すことができます。 そこで、我々は、任意のデータを失うことなく、これをやった。 コー​​ドでは、Cは、現在のノードで トラバーサルポインタクローラは、を指していることを およびDは、現在のノードの次のフィールドが指すノードとして表され またはクローラー→次へをクリックします。 だから、我々は最初の新しいノードの次のポインタを設定 クローラーを指すように→次、 我々はnew_nodeの次のポインタがすべきだと述べたのと同じ方法 図のA〜Dのポイント。 そこで我々は、現在のノードの次のポインタを設定することができます 私たちの新しいノードに、 我々は、図面にnew_nodeためにCを指すように待たなければならなかったのと同じである。 これですべてがためにだ、と我々は失うことはありませんでした 任意のデータを追跡して、私達はちょうどすることができました リストの中に私たちの新しいノードをスティック 全体を再構築したり、任意の要素を移動させることなく、 方法は、我々は、固定長の配列でなければならなかっただろう。 

だから、リンクされたリストでは、基本的であるが、重要なのは、動的データ構造 そのメリットとデメリットの両方を持って 配列やその他のデータ構造に比べ、 そして、計算機科学ではよくあることですが、 それは、それぞれのツールを使用する際に知っておくことは重要です ので、右の仕事のための適切なツールを選ぶことができます。 

より多くの練習のために関数を記述しよう リンクされたリストからノードを削除する -  再配置される順序に注意する必要を覚え あなたのリストのチャンクを失わないことを保証するためにあなたの次のポインタ -  またはリンクされたリスト内のノード数をカウントする機能、 リンクされたリスト内のすべてのノードの順序を逆にしたり、楽しい1、。 

私の名前はジャクソンSteinkampですが、これはCS50です。