[ruby-list:40192] Re: 求む，もっとましな連結リストの実装

原です。

>小波です。
>
>こういうネタを振っていいのか悩みましたが，まあまずいなら叱られて
>恥をかけばいいかと考えることにしました。
>
>http://www.cs.kyoto-wu.ac.jp/info-com/algorithm/sources/list.rb
>
>こういうふうに連結リストの実装を行ってみました。授業のアルゴリズ
>ムとデータ構造の教材です。しかし時間がなくて無理やり作ったソース
>で，自分でも気に入らないのです。

私は Ruby で、リスト構造を実装してみるというのは、アルゴリズム
のいい練習問題だと思います。「リスト構造なんて初歩的なものいま
さら」と思っている人は、是非試しに実装してみてください。かなり
難しいです。Ruby にポインタがないからかな。

Cell は List の内部クラスにすべきかとか、あるいは List < Cell
の継承関係をつけるとか、Cell 一本で List は使わないとか、番兵
を置く置かないとか、番兵の次は自分自身にするとか、空リストを例
外とするしない、とかいろんな選択肢があります。

小南さんのコードは、deleteにバグがありました。それから、@precell
というインスタンス変数の役割が不安定に思います。次のは、仕様は
なるべくそのままに、ダミーのトップセルをおいて、若干アルゴリズ
ムがシンプルになっていると思います。


class Cell
  attr_reader :data
  attr_accessor :pointer

  def initialize(data)
    @data = data
    @pointer = nil
  end
end

class List
  def initialize
    @root = @bottom = Cell.new(nil)
  end

  def add(x)
    @bottom = @bottom.pointer = Cell.new(x)
  end

  def each
    cell = @root
    while cell = cell.pointer
      yield cell
    end
  end

  include Enumerable

  def finddata(item)
    find{|cell| cell.data == item}
  end

  def show
    puts map{|cell| cell.data}.join("->") + "\n"
  end

  def insert(p, item)# p という内容のセルの後ろに item を追加する。
    if cell = finddata(p)
      newcell = Cell.new(item)
      newcell.pointer = cell.pointer
      cell.pointer = newcell
      @bottom = newcell if cell == @bottom
    else
      printf("'%s'はありません！\n",p)
    end
  end

  def delete(item)
    precell = @root
    while cell = precell.pointer
      if cell.data == item
        precell.pointer = cell.pointer
        @bottom = precell if cell == @bottom
        return
      end
      precell = cell
    end
    printf("'%s'はないので削除できません！\n",item)
  end
end

これが決定版という方法があれば是非知りたい。