1

単一リンクリストの各ノードは、データと次の項目へのポインター (リストの末尾の場合は null ポインター) です。

私が知っているネイティブのリスト型を持つすべての言語は、「空の」リストをサポートしており、通常は何らかのリテラル構文を使用しています。

これは、マシンのメモリでどのように表現されるでしょうか?

私はいくつかの方法を考えることができます：

  • 実行時の型情報 (つまり、型と値のペア) を持つ言語では、null 値項目を持つ「リスト」型である可能性があります。
  • リスト ノード内のデータ項目のヌル ポインター (ただし、これは、ノードのデータ構造に直接埋め込まれた値ではなく、「ポインター」型の場合にのみ機能します)
  • 特別な記号値

これは言語間で大きく異なりますか、それとも標準的な方法はありますか?

4

1 に答える 1

1

実装に依存します。

かなり標準的な単一のリンクリストの実装は次のようになると思います。

object List
  Node head

object Node
  Type data
  Node next

空のリストの場合List.headは、null ポインターになります。

別の方法として、空のリストは型のヌル ポインターである可能性がありますList(一部の言語では、これら 2 つの違いは重要です)。

List完全に削除してリストを として定義することもNodeできます。空のリストは次のいずれかになります。

  • 型の null ポインターNode(これも特定の言語には適していません)
  • とnull のNode両方を持つA (可能であれば、1 つの null 要素を持つリストと区別できない場合があります)datanext

一部の言語には null ポインターの概念がない場合がありますが、これを特別なオブジェクトと交換できるはずです。

于 2013-02-06T08:44:02.563 に答える