data-structures - リンクされたリストとストリームの技術的な違いは何ですか?

Question

どちらも同じ方法で同じことを行っているようです。特定の、しかし必ずしもインデックス付けされていない順序での遅延操作であり、必ずしもバックトラックすることはできません。

Answer 1

リンクされたリストは、メモリ内のデータ要素のシーケンスを表す特定の方法であり、各要素は、シーケンス内の次の要素への種類のポインターとペアになっています。リンクされたリストを使用すると、サブシーケンスに対してさまざまな操作を実行できます。非常に低コストで、要素のチェーン全体を切り取ったり挿入したり、途中から要素を削除したりできます。

一方、ストリームは、データを順番にアクセスするための抽象化であり、メモリ内での表現に特定の要件はありません。リンクされたリストを使用してストリームを実装できますが、プレーン配列や循環配列バッファーなど、別のデータ構造を使用することもできます。

Answer 2

これは、リンゴとオレンジを比較しようとするのと少し似ていると思います。

リンク リストは、各ノードが別のノードを指すデータ構造です。リンクされたリストからの項目の挿入と削除は、より多くのシャッフルを割り当てる必要がある配列を使用するのではなく、ノードを再ポイントするだけの問題であるため、これらは便利な構造です。詳細については、 http://en.wikipedia.org/wiki/Linked_listを参照してください。

ストリームは、一連のバイトを表すために使用される抽象化されたオブジェクトです。ほとんどのフレームワーク (Java、.NET など) には、関連するソース (メモリ、ファイルなど) からバイト配列を読み取るために使用されるストリーム (メモリ ストリーム、ファイル ストリームなど) の具体的な実装がいくつかあります。

Answer 3

リンクされたリストは、各要素が次の要素へのポインタを持つデータ構造であり、おそらく反対方向でも同じです。循環リンクリストには、最後の要素から最初の要素へのポインター、およびその逆のポインターさえあります。これらのポインター (またはポインターを持たない言語の参照) は、データ構造を定義するものです。それらは特定の操作モードを暗示しますが、それを強制するものではありません。LinkedListたとえば、Javaのクラスは配列のように使用できますが、その場合はあまり効果的ではありません。また、呼び出す関数に応じて、(ダブルエンド) キューまたはスタックとして使用することもできます。

一方、ストリームはデータ構造としてではなく、要素のソースまたはシンクとして定義されます。これらの要素は、ファイル ストリーム、ソケット ストリーム、またはストリームをラップするリーダー/ライター クラスを考える場合、バイトまたは文字である可能性があります。ストリームによって提供される要素は、パーサーのトークンなど、より複雑になることもあります。その場合、ストリームは何らかの種類のキューを内部的に使用する可能性が高く、リンク リストまたは何らかの配列構造を使用して実装できます。

これら 2 つのことは、異なる抽象化レイヤーで定義されていることを必ず理解してください。リンクされたリストは内部でどのように機能するかについて定義されていますが、ストリームは外部でどのように機能するかについて定義されています。

Answer 4

読み取り専用の単一リンク リストと入力ストリームの間には共通の抽象化があり、C++ では次のように形式化されInputIteratorます。値を読み取ることができ、次に進むことができます。多くのストリーム API では、両方を同時に実行する必要がありますが、その API を考えると、1 つの値をキャッシュするラッパーを使用してそれらを分離する方法を理解するのはかなり簡単です。C++ はこのクラスを呼び出しますistream_iterator。

ただし、片方向リストには、ストリームに常にあるとは限らないプロパティがあり、C++ では次のように形式化されForwardIteratorます。現在の位置をコピーし、コピーを前方に移動しますが、元の位置の値を読み取ることができます。基になる I/O には「現在の位置」が 1 つしかないため、一般化されたストリームではこれを実行できません。リンクされたリストを使用すると、リスト内のさまざまなノードへの複数のポインターを問題なく使用できます。

一部のストリームは、マークおよびリセット、巻き戻し、シーク (シーク?) などを行うことができ、C++ の ForwardIterator や RandomAccessIterator に似た機能を追加します。

C++ を例として使用するのは、それが特に重要だからではなく、C++ の反復子の概念が、データ構造とストリームに共通の抽象化を提供するように設計されているためです。すべての言語がそのような共通の抽象化を持っているわけではありませんが、Python の別の例として、for x in y:ifyがコンテナ データ構造であるか、 ifyがファイルのようなオブジェクトであるか、または一般に ifyが「反復可能」であると記述できます。