実装の種類は？

Question

私はしばらく解決しようとしていましたが、正しい実装を理解するのが難しいという疑問があります。それぞれが製品名、型式、シリアル番号、小売価格などからなる何千ものレコードを操作するプログラムを書く場合、以下のそれぞれのケースで、使用する抽象データ型（キュー、スタック、並べ替えられていないソート済みリスト） 、およびどの実装（配列またはリンクされた構造）が含まれます。あなたの選択肢を簡単に正当化します。

1）レコードは、格納されたのと同じ順序で取得されます。処理されるレコード数とその方法は、事前には知らされていません。

• 私たちが最初にレコード数を知らない、と彼らはので、保存されている彼らも可能とすることができるリンクされなければならないとデータが取得されますので、リンクリストの実装を使用し、この目的のためにソートされていないリストを好みますQueueやStackのようなADTでは配列の実装を使用するため、メモリ割り当ての問題が発生します。

2）すべてのレコードは、先頭に1回、特定の順序で挿入されません。シリアル番号に基づいて頻繁に検索されます。

• レコードのすべてのデータを一度に印刷する場合でも、並べ替えられていないリストでも可能です。

3）大量ではあるが未知数の製品レコードが、必要に応じて挿入されます。彼らはめったに個別に検索されません。ほとんどの操作は、すべてのレコードを一度に処理すること、例えばすべてを印刷することからなる。

• は、しかし、ここでソートし、ソートされていないリストを使用するより効率があったが、それはその効率を低下させるソートに時間がかかるので、私は、ソートされていないリストを好みます。

あなたはどう思いますか？

Answer 1

それぞれのデータ構造が何を意図しているのかを考えてください。質問で提供されたアクセスパターンと1つと2つの答えが自明になります。 3つはややこしいですが、あなたが持っている情報は、すべてのデータが使用される可能性が高い以外に、このデータの使用方法に関する情報がないということです。

キュー

キューはパイプです。スタッフは片方を行き来し、同じ順番で先に出てきます（先入れ先出し、AKA FIFO）。キューには、出てこないアイテム以外のものが表示される場合と表示されない場合があります。つまり、キュー内の次のアイテムを見るだけで、現在のアイテムを削除する必要があります。検索は非常に悪い考えです。なぜなら、すべてを取り出して、それをすべて元に戻すことができない可能性が高いからです。

スタック

スタックはそれだけです。ものの山。あなたは積み重ねの上にものを置いて、次に積み重ねたものを取る。スタックに入れられたものとは逆の順序でスタックから出てきます。これはファーストイン、ラストアウト、またはFILOです。繰り返しますが、スタックの一番上のアイテム以外は表示できない場合があります。次のアイテムを取得するには、上のアイテムを削除する必要があります。検索はキューと同じ理由で悪い考えです。

無題リスト

どこにでも置くことができます。あなたがそれがどこに行くのか気にしないので、リストに物を入れるのはすごいです。リスト内のものを見つける...それはバカだ。文字通り、探しているものが見つかるまで、各アイテムを1つずつ（線形検索）調べなければなりません。あなたがリストにあるものを気にかけずに検索する必要がない場合、これはあなたのデータ構造です。少なくともあなたが収集して使用統計を取得し、いくつかの最適化を見つけるまで。

ソートリスト

すべては、指定されたスキーマに従って配置されています。これは愚かなものを見つけるのを簡単にします。あなたが探しているアイテムにまっすぐ行くことができますし、そうでない場合は、アイテムが片側にない場合は反対側（バイナリ検索）にする必要がありますので、 。発見は簡単ですが、挿入するものは慎重に置かなければならず、これはかなり高価になる可能性があります。しかし、リストを一度構築してからそれを繰り返し検索すると、ほとんど常に先に出てきます。