とにかく、リンクリストとは何ですか？[パート1]

Jun 20 2018

情報は私たちの周りにあります。ソフトウェアの世界では、情報を整理するために選択する方法は、戦いの半分です。

情報は私たちの周りにあります。

ソフトウェアの世界では、情報を整理するために選択する方法は、戦いの半分です。ただし、これが問題です。問題を解決する方法はたくさんあります。また、データの整理に関しては、その仕事に役立つツールがたくさんあります。秘訣は、どのツールを使用するのが適切かを知ることです。

コーディングを開始する言語に関係なく、最初に遭遇するものの1つはデータ構造です。これは、データを整理するためのさまざまな方法です。変数、配列、ハッシュ、およびオブジェクトはすべてタイプのデータ構造です。しかし、これらはデータ構造に関してはまだ氷山の一角にすぎません。もっとたくさんありますが、それらについて聞くほど、非常に複雑に聞こえ始めるものもあります。

私にとってこれらの複雑なことの1つは、常にリンクリストです。リンクリストについては数年前から知っていますが、頭の中でまっすぐに保つことはできません。技術面接の準備をしているとき（または、時には途中で）、誰かが私にそれらについて尋ねるときだけ、私はそれらについて本当に考えます。少し調べて、何を言っているのか理解できたと思いますが、数週間後にはまた忘れてしまいます。全体がかなり非効率的であり、それはすべて、それらが存在することを私が知っているという事実から生じていますが、私はそれらを根本的に理解していません！それで、それを変えて、質問に答える時が来ました：とにかく、リンクリストは一体何ですか？

線形データ構造

リンクリストの基本を本当に理解したいのであれば、それらがどのような種類のデータ構造であるかについて話すことが重要です。

リンクリストの特徴の1つは、線形データ構造であるということです。つまり、リストの作成方法とトラバース方法に順序と順序があります。石けり遊びのゲームのような線形データ構造を考えることができます。リストの最後に到達するには、リスト内のすべてのアイテムを順番に、または順番に調べる必要があります。ただし、線形構造は非線形構造の反対です。では非線形データ構造、アイテムは、我々は、データ構造をトラバースできることをその手段、の順に配置する必要はありません非順次。

線形データ構造と非線形データ構造

常に気付くとは限りませんが、私たちは皆、線形および非線形のデータ構造を毎日使用しています。データをハッシュ（辞書と呼ばれることもあります）に編成すると、非線形データ構造が実装されます。ツリーとグラフも、さまざまな方法でトラバースする非線形データ構造ですが、年内にさらに詳しく説明します。

同様に、コードで配列を使用する場合、線形データ構造を実装しています。配列とリンクリストは、データのシーケンス方法が類似していると考えると便利です。これらの構造の両方で、順序が重要です。しかし、配列とリンクリストの違いは何ですか？

メモリ管理

配列とリンクリストの最大の違いは、マシンでメモリを使用する方法です。Ruby、JavaScript、Pythonなどの動的型付け言語を使用する人は、抽象化レイヤーがいくつかあるため、コードを日常的に作成するときに配列が使用するメモリの量を考える必要はありません。メモリ割り当てについてまったく心配する必要はありません。

しかし、それはメモリ割り当てが行われていないという意味ではありません！抽象化は魔法ではありません。常に表示したり処理したりする必要のないものを隠すだけの単純さです。コードを書くときにメモリ割り当てについて考える必要がなくても、リンクリストで何が起こっているのか、そして何がそれを強力にするのかを真に理解したいのであれば、基本的なレベルに到達する必要があります。

バイナリと、データをビットとバイトに分割する方法については、すでに学習しました。文字、数字、単語、文がそれらを表すためにメモリのバイトを必要とするように、データ構造もそうです。

配列を作成するときは、一定量のメモリが必要です。配列に格納する必要のある7文字がある場合、その配列を表すために7バイトのメモリが必要になります。ただし、そのすべてのメモリが1つの連続したブロックに必要です。つまり、私たちのコンピュータは、空きになっている7バイトのメモリを1つの場所にまとめて配置する必要があります。

一方、リンクリストが作成される場合、7バイトのメモリをすべて1か所に配置する必要はありません。1バイトはどこかに存在する可能性があり、次のバイトはメモリ内の別の場所に完全に格納される可能性があります。リンクリストは、メモリの単一ブロックを占有する必要はありません。代わりに、彼らが使用するメモリは、全体に散らばることができます。

静的データ構造と動的データ構造でのメモリ割り当て

配列とリンクリストの基本的な違いは、配列は静的データ構造であるのに対し、リンクリストは動的データ構造であるということです。静的データ構造では、構造の作成時にすべてのリソースを割り当てる必要があります。これは、構造のサイズが拡大または縮小し、要素が追加または削除された場合でも、常に特定のサイズと量のメモリが必要であることを意味します。静的データ構造にさらに要素を追加する必要があり、十分なメモリがない場合は、たとえば、その配列のデータをコピーし、より多くのメモリを使用して再作成して、要素を追加できるようにする必要があります。それ。

一方、動的データ構造は、メモリ内で縮小および拡大する可能性があります。存在するために設定された量のメモリを割り当てる必要はなく、サイズと形状が変わる可能性があり、必要なメモリの量も変わる可能性があります。

ここまでで、配列とリンクリストの間にいくつかの大きな違いが見られるようになりました。しかし、これは疑問を投げかけます：リンクリストがそのメモリをいたるところに散らばらせることができるのは何ですか？この質問に答えるには、リンクリストがどのように構成されているかを調べる必要があります。

リンクリストの一部

リンクリストは小さい場合も大きい場合もありますが、サイズに関係なく、それを構成する部分は実際にはかなり単純です。リンクリストは、リストの要素である一連のノードで構成されています。

リストの開始点は、ヘッドと呼ばれる最初のノードへの参照です。これが事実上リストとそのすべての要素への唯一のエントリポイントであり、それがないとどこから始めればよいかわからないため、ほぼすべてのリンクリストに先頭が必要です。リストの最後はノードではなく、nullまたは空の値を指すノードです。

リンクリストの一部：実際には、それはすべて単なるノードの集まりです。

単一ノードも非常に単純です。データ、つまりノードに含まれる情報と、次のノードへの参照の2つの部分だけで構成されます。

これに頭を包むことができれば、私たちは途中です。ノードの動作方法は非常に重要であり、非常に強力であり、次のように要約できます。

ノードは、ノードに含まれるデータと、そのネイバーが誰であるかについてのみ認識します。

単一のノードは、リンクリストの長さを認識しておらず、開始場所や終了場所を必ずしも認識していない場合があります。関係するすべてのノードは、ノードに含まれるデータと、そのポインターが参照するノード（リスト内の次のノード）です。

そしてこれが、リンクリストが連続したメモリブロックを必要としない理由です。単一のノードには「アドレス」または次のノードへの参照があるため、要素が配列内にあるように、ノードが互いに隣接している必要はありません。代わりに、次のノードへのポインタ参照に頼ることでリストをトラバースできるという事実に頼ることができます。つまり、リストを表すためにマシンがメモリの単一のチャンクをブロックする必要はありません。

これは、プログラムの実行中にリンクリストが動的に拡大および縮小する理由の説明でもあります。リンクリストを使用してノードを追加または削除すると、配列の要素をコピーするのではなく、いくつかのポインタを再配置するのと同じくらい簡単になります。ただし、リンクリストにはまだ言及していないいくつかの欠点もありますが、来週はさらに多くの欠点があります。

今のところ、リンクリストがいかにクールであるかの栄光を浴びるだけです！

すべての形状とサイズのリスト

リンクリストの一部は変更されませんが、リンクリストの構造はまったく異なる場合があります。ソフトウェアのほとんどのものと同様に、解決しようとしている問題によっては、あるタイプのリンクリストが別のタイプよりも優れたツールになる場合があります。

単一リンクリストは、一方向にしか進まないという事実のみに基づいた、最も単純なタイプのリンクリストです。リストをトラバースできるトラックが1つあります。ヘッドノードから開始し、ルートから最後のノードまでトラバースします。最後のノードは空のnull値で終了します。

ただし、ノードが後続の隣接ノードを参照できるのと同様に、前のノードへの参照ポインターも持つことができます。各ノードには2つの参照が含まれているため、これを二重リンクリストと呼びます。次のノードと前のノードへの参照です。これは、単一のトラックまたは方向だけでなく、逆方向にもデータ構造をトラバースできるようにする場合に役立ちます。

たとえば、リストの最初に戻らずに1つのノードと前のノードの間をホップできるようにしたい場合、二重リンクリストは単一リンクリストよりも優れたデータ構造になります。ただし、すべてにスペースとメモリが必要なため、ノードに1つではなく2つの参照ポインタを格納する必要がある場合は、別の考慮事項になります。

さまざまな種類のリンクリスト

円形のリンクされたリストは、それがヌル値を指すノードで終わらないことが少し奇妙です。代わりに、（従来のヘッドノードではなく）リストのテールとして機能するノードがあり、テールノードの後のノードがリストの先頭になります。この組織構造により、最初の要素と最後の要素が相互にポイントするため、テール ノードでトラバースを開始できるため、リストの最後に何かを追加するのが非常に簡単になります。円形のリンクリストは、我々は、単一リンクのリストがあり、二重リンクリストの両方を有効にすることができますので、本当にクレイジー取得するために開始することができますに、円形のリンクリスト！

しかし、リンクリストがどれほど複雑であっても、ノードの基本とその動作、およびリスト内のさまざまなポインター参照の構造を覚えていれば、取り組むことができないリンクリストはありません。

来週、このシリーズのパート2では、リンクリストの時空間の複雑さと、それらがいとこである配列とどのように比較されるかについて説明します。私はそれが実際にそれが思っているよりずっと楽しいことを約束します！