Lua のプログラミング : 11.3

この初版は Lua 5.0 用に執筆されました。以降のバージョンでも大半が引き続き関連していますが、いくつかの相違点があります。
第 4 版は Lua 5.3 を対象としており、Amazon などの書店で購入可能です。
また、書籍を購入することで Lua プロジェクトを支援することもできます。

プログラミング inLua

第 II 部テーブルとオブジェクト第 11 章データ構造

11.3 – リンクドリスト

テーブルは動的エンティティであるため、Lua でリンクドリストを実装するのは簡単です。各ノードはテーブルで表され、リンクは単なる、他のテーブルへの参照を含むテーブルフィールドです。たとえば、各ノードに next フィールドと value フィールドの 2 つのフィールドを持つ基本的なリストを実装するには、リストのルートとなる変数が必要です。

    list = nil

値 v を持つ要素をリストの先頭に挿入するには、以下のようにします。

    list = {next = list, value = v}

リストをトラバースするには、次のように書きます。

    local l = list
    while l do
      print(l.value)
      l = l.next
    end

二重リンクリストや循環リストなど、他の種類のリストも実装は簡単です。ただし、通常リストを使用せずにデータを表すより簡単な方法があるため、Lua ではこれらの構造が必要になることは稀です。たとえば、スタックは、先頭を指す n フィールドを持つ（境界のない）配列で表すことができます。