配列と連結リスト

Nov 06 2022
ゼロからヒーローまでのアルゴリズムとデータ構造
要素のリストをメモリに保存する必要がある場合があります。経費を管理するアプリを作成しているとします。

要素のリストをメモリに保存する必要がある場合があります。経費を管理するアプリを作成しているとします。経費をリストとしてメモリに保存します。

配列またはリンクされたリストを使用する必要がありますか? 把握しやすいので、最初に経費を配列に格納しましょう。配列を使用すると、すべての経費がメモリに連続して (隣り合って) 格納されます。

ここで、4 番目の経費を追加するとします。しかし、次の引き出しが取り上げられます。

それは、友達と出かけて座る場所を見つけたのに、別の友達があなたに加わって、彼らのための場所がないようなものです. 全員が合う新しい場所に移動する必要があります。この場合、コンピュータに 4 つの費用を収めることができる別のメモリ チャンクを要求する必要があります。次に、すべての費用をそこに移動する必要があります。

そして、これは、より多くの友達があなたに参加するとすぐにループになりますが、念のためにいつでも追加のスロットを追加できることを確認してください. これは良い回避策ですが、いくつかの欠点に注意する必要があります。

  • 要求した余分なスロットは必要ないかもしれませんが、そのメモリは無駄になります。
  • 経費リストに 10 を超えるアイテムを追加することができ、とにかく移動する必要があります。

リンクされたリスト

リンクされたリストは、メモリ内の物理的な配置によって順序が指定されないデータ要素の線形コレクションです。代わりに、各要素は次の要素を指します。

リンクされたリストを使用すると、アイテムをメモリ内のどこにでも置くことができます。

シーケンシャル アクセスとランダム アクセス

シーケンシャル アクセスとは、5 番目の要素にアクセスするコストが最初の要素にアクセスするコストの 5 倍であるか、少なくともセット内の要素の位置に関連するコストが増加することを意味します。これは、セットの 5 番目の要素にアクセスするには、最初に 1 番目、2 番目、3 番目、4 番目の要素を見つける操作を実行する必要があるため、5 番目の要素にアクセスするには 5 つの操作が必要です。

ランダム アクセスとは、セット内の任意の要素にアクセスするコストが、セット内の他の要素と同じであることを意味します。セットの 5 番目の要素を見つけることは、まだ 1 回の操作で済みます。

配列とLinkedList

配列では、配列の各要素のアドレスを知っています。上の画像でわかるように、5 つのメモリ ユニットを持つ配列があり、この配列には 3 つの要素が含まれています。これは、要素が連続したメモリ位置に格納されているためです (配列内の要素には番号が付けられ、この番号は 0 から始まります)。始まりと終わり。

要素の位置はそのインデックスと呼ばれるため、「8 は位置 1 にある」と言う代わりに、正しい用語は「8 はインデックス 1 にある」です。

配列内の任意の要素を即座に検索できるため、ランダムな要素を読み取りたい場合は、配列が最適です。

リンクされたリストでは、各アイテムはリスト内の次のアイテムのアドレスを格納します。一連のランダムなメモリ アドレスがリンクされています。

宝探しのようなものです。最初の住所に行くと、「次のアイテムは住所 008 にあります」と表示されます。アドレス 008 に行くと、「次のアイテムはアドレス 002 にあります」などと表示されます。

リンクされたリストに項目を追加するのは簡単です。メモリ内の任意の場所に貼り付けて、次の前の項目と共にアドレスを保存します。

リンクされたリストを使用すると、アイテムを移動する必要がありません。また、別の問題も回避できます。

友達4人と人気の映画を見に行ったとしましょう。5人で座る場所を探すが、映画館は満員。一緒に5席はありません。

まあ、これは配列で時々起こります。配列に対して 40,000 個のスロットを見つけようとしているとしましょう。メモリには 40,000 スロットがありますが、合計で 40,000 スロットではありません。配列用のスペースを確保できません!

リンクされたリストは、「別れて映画を見よう」と言っているようなものです。メモリにスペースがある場合は、リンク リスト用のスペースがあります。

リンクされたリストが挿入にはるかに優れている場合、配列は何に適していますか?

配列

リスト内のアイテムにアクセスしようとする場合、配列はリンクされたリストよりも優れています。

リンクされたリストの最後から 2 番目の項目を読み取りたいとします。それがどのアドレスにあるのかわからないので、それを読むことはできません。

最後から 2 番目の項目に到達するまで、項目 #2 のアドレスを取得するために項目 #1 に移動する必要があります。

一度にすべての項目を 1 つずつ読む場合は、リンクされたリストが最適です。しかし、あちこち飛び回るつもりなら、リンクされたリストはひどいものです。

配列は異なります。配列内のすべての項目のアドレスを知っているので、どの項目にもすぐにアクセスできます。

リストの途中に挿入する

経費リストをカレンダーのように機能させたいとします。以前は、リストの最後に物を追加していました。

次に、それらを実行する順序で追加します。

途中に要素を挿入したい場合、配列と連結リストのどちらが良いでしょうか? リンクされたリストを使用すると、前の要素が指すものを変更するのは簡単です。

ただし、配列の場合は、残りの要素をすべて下にシフトする必要があります。

スペースがない場合は、すべてを新しい場所にコピーする必要があります。途中に要素を挿入したい場合は、リストの方が適しています。

削除

要素を削除したい場合はどうしますか? 繰り返しになりますが、前の要素が指すものを変更するだけでよいため、リンクされたリストの方が優れています。配列では、要素を削除するときにすべてを上に移動する必要があります。

配列とリストに対する一般的な操作の実行時間:

通常、リンクされたリストの最初と最後のアイテムを追跡するため、挿入と削除は O(1) 時間であり、追加または削除には O(1) しかかかりません。

配列とリンクされたリストのどちらがより多く使用されていますか? 明らかに、それはユースケースに依存します。しかし、配列はランダム アクセスを許可するため、多くの用途があります。

演習

顧客の注文を受けるスーパー マーケット向けのアプリを構築しているとします。アプリは注文のリストを保存する必要があります。顧客はこのリストに注文を追加し続け、従業員はリストから注文を取り出して作成します。これは注文待ち行列です。顧客は注文を待ち行列の最後に追加し、従業員は最初の注文を待ち行列から取り出して準備します。

このキューを実装するには、配列または連結リストを使用しますか? (ヒント: — リンクされたリストは挿入/削除に適しています。配列はランダム アクセスに適しています。ここではどちらを実行しますか?)

配列と連結リストは、他のデータ構造の実装にも使用されます。

⬅️記憶のしくみ| 目次| スタック➡️

© Copyright 2021 - 2022 | hachiwiki.com | All Rights Reserved