Rubyでアルゴリズムやらデータ構造やらのお勉強（Linked List）

linkedlist.rb

# -*- coding: utf-8 -*-

# Cで書かれたアルゴリズムやらデータ構造なりを、自分なりにRubyで表現してみるお勉強PJ。
# 参考書籍（プログラミングの宝箱 アルゴリズムとデータ構造）
# Ruby1.9.3で動作確認済み

# アイディアだけ聞いて実装イメージの大半を自力でつかめたのはこれと線形探索ぐらいだった気がする。（あってるのか別にして）
# でもこれそのものをRubyで使うことはないんだろうな・・・RubyのArrayは可変な上にindex使えるんだし。

$VERBOSE = true

class LinkedList

  class Node

    attr_accessor :value, :pre, :succ
    alias_method :next, :succ
    alias_method :next=, :succ=

    def initialize(value, pre, succ)
      @value, @pre, @succ = value, pre, succ
    end

  end

  attr_reader :first, :last

  def initialize(first_value)
    @first = @last = Node.new first_value, nil, nil
  end

  def <<(value)
    @last.succ = Node.new value, @last, nil
    @last = @last.succ
    self
  end

  def each
    return to_enum(__callee__) unless block_given?

    node = @first
    yield node.value

    while node = node.succ
      yield node.value
    end

    self
  end

  def reverse_each
    return to_enum(__callee__) unless block_given?

    node = @last
    yield node.value

    while node = node.pre
      yield node.value
    end

    self
  end

end

# Overview

list = LinkedList.new 7
list << 9 << 200 << -3

p list.first.value   #=> 7
p list.last.value    #=> -3

list.each do |value|
  p value
end

#=> 7, 9, 200, -3

list.reverse_each do |value|
  p value
end

#=> -3, 200, 9, 7