お気楽 Lua プログラミング超入門

はじめに

今回は簡単な例題として、「連結リスト (Linked List)」という基本的なデータ構造を作ってみましょう。なお、今回のプログラムは拙作のページ「お気楽 Python プログラミング入門第 5 回」の "連結リスト" を Lua で書き直したものです。内容は重複していますが、あしからずご了承ください。

連結リストはデータを一方向につなげたデータ構造です。リストを操作するプログラミング言語では Lisp が有名ですが、Lisp で扱うリストが連結リストです。図 1 に連結リストの構造を示します。

(1)変数
  ┌─┐    ┌─┬─┐  ┌─┬─┐  ┌─┬─┐  
  │・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(null)
  └─┘    └─┴─┘  └─┴─┘  └─┴─┘  

(2)ヘッダセル
  ┌─┬─┐    ┌─┬─┐  ┌─┬─┐  ┌─┬─┐  
  │  │・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(null)
  └─┴─┘    └─┴─┘  └─┴─┘  └─┴─┘  

                図 1 : 連結リスト

連結リストはセル (cell) というデータを繋げて作ります。セルにはデータを格納する場所と、次のセルを指し示す場所から構成されます。図 1 でいうと、箱がひとつのセルを表していて、左側にデータを格納し、右側に次のセルへの参照を格納します。リストの終わりを示すため、最後のセルの右側には特別な値（たとえば null）を格納します。そして、図 1 (1) のように先頭セルへの参照を変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、図 1 (2) のようにヘッダセルを用意する方法もあります。

●コンストラクタの定義

それではプログラムを作りましょう。まずは、セル Cell と連結リスト List のコンストラクタを作成します。

リスト 8 : コンストラクタの定義

-- セルの定義
Cell = {}

-- コンストラクタ
function Cell.new(data, link)
  return {data = data, link = link}
end

-- リストの定義
List = {}

-- コンストラクタ
function List.new(...)
  local obj = {top = Cell.new(nil, nil)}
  local cp = obj.top
  setmetatable(obj, {__index = List})
  for i = 1, select("#", ...) do
    local x = select(i, ...)
    cp.link = Cell.new(x, nil)
    cp = cp.link
  end
  return obj
end

Cell.new はセルを作成します。フィールド data にデータを格納し、フィールド link に接続するセルへの参照を格納します。List.new は連結リストのオブジェクトを生成します。今回は図 1 (2) の方法でプログラムします。List が生成したインスタンスのフィールド top にはヘッダーセルを格納します。List.new は可変個の引数を受け取るようにすると便利です。可変引数式から要素 x を取り出し、連結リストの最後尾に x を追加していきます。

●メソッドの定義

あとはメソッドを定義するだけです。今回作成するメソッドを表 1 に示します。

プログラムは次のようになります。

リスト 9 : メソッドの定義 (1)

-- 作業用メソッド : n 番目のセルを返す
function List:_nth(n)
  local cp = self.top
  local i = 0
  while cp do
    if n == i then
      return cp
    else
      cp = cp.link
      i = i + 1
    end
  end
  return nil
end

-- n 番目の要素を返す
function List:at(n)
  local cp = self:_nth(n)
  if cp then
    return cp.data
  else
    return nil
  end
end

-- n 番目の要素を書き換える
function List:set(n, x)
  local cp = self:_nth(n)
  if cp then
    cp.data = x
    return x
  else
    return nil
  end
end

-- n 番目にデータを挿入
function List:insert(n, x)
  local cp = self:_nth(n - 1)
  if cp then
    cp.link = Cell.new(x, cp.link)
    return x
  else
    return nil
  end
end

-- n 番目の要素を削除
function List:remove(n)
  local cp = self:_nth(n - 1)
  if cp and cp.link then
    local data = cp.link.data
    cp.link = cp.link.link
    return data
  else
    return nil
  end
end

-- 巡回
function List:foreach(func)
  local cp = self.top.link
  while cp do
    func(cp.data)
    cp = cp.link
  end
end

-- イテレータ
function List:each()
  return coroutine.wrap(
    function()
      self:foreach(function(x) coroutine.yield(x) end)
      return nil
    end)
end

-- 空リストか
function List:isEmpty()
  return self.top.link == nil
end

_nth は n 番目のセルを求める作業用のメソッドです。at, set, insert, remove は _nth を使うと簡単にプログラムすることができます。詳しい説明は拙作のページ「お気楽 Python プログラミング入門第 5 回」 "連結リスト" をお読みください。

それでは、簡単な実行例を示しましょう。

> a = List.new()
> for x = 1, 5 do a:insert(1, x) end
> a
table: 0x7fffef67ff20
> a:at(1)
5
> a:at(5)
1
> a:foreach(print)
5
4
3
2
1
> for x in a:each() do print(x) end
5
4
3
2
1
> a:remove(1)
5
> a:foreach(print)
4
3
2
1
> a:set(1, 10)
10
> a:foreach(print)
10
3
2
1

正常に動作していますね。

●データの変換

このほかに、連結リストを配列に変換するメソッド toArray と文字列に変換するメソッド toString を定義すると便利です。リスト 10 を見てください。

リスト 10 : データの変換

-- 配列に変換
function List:toArray()
  local ary = {}
  self:foreach(function(x) table.insert(ary, x) end)
  return ary
end

-- 文字列に変換
function List:toString()
  return '(' .. table.concat(self:toArray(), ',') .. ')'
end

toArray はメソッド foreach を使うと簡単です。foreach で先頭から順番に要素にアクセスし、それを配列 ary に insert で追加するだけです。最後に配列を返します。

toString も簡単です。連結リストを toArray で配列に変換し、要素を関数 concat で連結します。各要素は concat で文字列に変換され、カンマ ( , ) をはさんで連結されます。

それでは簡単な実行例を示しましょう。

> a = List.new(1,2,3,4,5)
> print(table.unpack(a:toArray()))
1       2       3       4       5
> a:toString()
(1,2,3,4,5)

●プログラムリスト

--
-- linklist.lua : 連結リスト
--
--                Copyright (C) 2011-2019 Makoto Hiroi
--

-- セルの定義
Cell = {}

-- コンストラクタ
function Cell.new(data, link)
  return {data = data, link = link}
end

-- リストの定義
List = {}

function List.new(...)
  local obj = {top = Cell.new(nil, nil)}
  local cp = obj.top
  setmetatable(obj, {__index = List})
  for i = 1, select("#", ...) do
    local x = select(i, ...)
    cp.link = Cell.new(x, nil)
    cp = cp.link
  end
  return obj
end

-- メソッドの定義

-- 作業用メソッド : n 番目のセルを返す
function List:_nth(n)
  local cp = self.top
  local i = 0
  while cp do
    if n == i then
      return cp
    else
      cp = cp.link
      i = i + 1
    end
  end
  return nil
end

-- n 番目の要素を返す
function List:at(n)
  local cp = self:_nth(n)
  if cp then
    return cp.data
  else
    return nil
  end
end

-- n 番目の要素を書き換える
function List:set(n, x)
  local cp = self:_nth(n)
  if cp then
    cp.data = x
    return x
  else
    return nil
  end
end

-- n 番目にデータを挿入
function List:insert(n, x)
  local cp = self:_nth(n - 1)
  if cp then
    cp.link = Cell.new(x, cp.link)
    return x
  else
    return nil
  end
end

-- n 番目の要素を削除
function List:remove(n)
  local cp = self:_nth(n - 1)
  if cp and cp.link then
    local data = cp.link.data
    cp.link = cp.link.link
    return data
  else
    return nil
  end
end

-- 巡回
function List:foreach(func)
  local cp = self.top.link
  while cp do
    func(cp.data)
    cp = cp.link
  end
end

-- イテレータ
function List:each()
  return coroutine.wrap(
    function()
      self:foreach(function(x) coroutine.yield(x) end)
      return nil
    end)
end

-- 空リストか
function List:isEmpty()
  return self.top.link == nil
end

-- 配列に変換
function List:toArray()
  local ary = {}
  self:foreach(function(x) table.insert(ary, x) end)
  return ary
end

-- 文字列に変換
function List:toString()
  return '(' .. table.concat(self:toArray(), ',') .. ')'
end