リスト

• リスト
• リストのサーチ
• 応用例：自己組織化探索

リスト

基本的な考え方

　大量のデータを格納しておきたい場合、配列のみに頼ると、データの数がいったいいくつあるか、最初は分からず、確保する配列のサイズをどうするかという問題が発生する。その場合の1つの解決策としてリストを利用することが考えられる（注1）。

　リストのポイントは、下記の通り。

1. リストの要素（ノード）は、前後の位置関係を把握している。
2. 前後の位置関係を把握するだけなので、追加・削除が容易。
3. リストでは先頭と末尾のみを把握しているため、ランダムにアクセスすることは向いていない。
• データ群にランダムアクセスする必要がある場合はリストは向いていない。
• 何度も前後を行ったり来たりする場合はリストは向いていない。

●注1：冨倉メモ
　Ruby では「配列は動的で、作成時にサイズを指定する必要はありません。」（Hal Fulton 『The Ruby Way』　翔泳社）となっており、配列のサイズを生成後に動的に変更できる。従って、単純に配列の初期化に絡む問題だけで言えば、リストを使う必要はないような気がする。

class Count
  def initialize
    @array = Array.new()
  end
  
  def main
    buf = nil
    sum = 0
    
    # ユーザから入力された値を配列に保存
    while buf != 0 do
      puts "整数を入力して下さい。（0を入力すると終了)"
      buf = intReader.to_i
      if buf != 0
        @array.push(buf)
      end
    end
    
    puts "入力値は下記の通り"
    p @array
    @array.each_index do |i|
      sum += @array[i]
    end
    puts "合計は#{sum}です"
  end
  
  private
  def intReader
    gets()
  end
end

count = Count.new
count.main

●冨倉メモ
　上記のように Ruby では、Arrayクラスに配列の要素を追加するメソッド（push）が存在するので、C や Java のサンプルコードにあるような配列のサイズを確保しておいて、そこにデータを入れていくということ、配列のサイズ一杯までデータが入った場合にどうするかということは、それほど意識しなくてもいい。

class Node
  attr_reader :data
  attr_accessor :prev, :next
  
  def initialize( data )
    @data = data
    @prev = nil
    @next = nil
  end
end

class Count
  def main
    buf = nil
    sum = 0
    firstNode = nil
    lastNode = nil
    
    while buf != 0 do
      puts "整数を入力して下さい。（0を入力すると終了)"
      buf = intReader.to_i
      if buf != 0
        # 新しいノードの生成
        newNode = Node.new(buf)
        newNode.next = nil
        if lastNode != nil
          # すでにあるリストの末尾に新しいノードをつなげる
          lastNode.next = newNode
          newNode.prev = lastNode
          lastNode = newNode
        else  # 今回生成したノードが最初の要素だった場合
          firstNode = lastNode = newNode
          newNode.prev = nil
        end
      end
    end
    
    puts "入力値は下記の通り"
    thisNode = firstNode
    while thisNode != nil
      print "#{thisNode.data}, "
      sum += thisNode.data
      thisNode = thisNode.next
    end
    print "¥n"
    puts "合計は#{sum}"
  end
  
  private
  def intReader
    gets()
  end
end

count = Count.new
count.main

リストのサーチ

ポイント

　リストの中に格納されているデータをサーチする方法は、リニアサーチのみ。

class Node
  attr_reader :data
  attr_accessor :prev, :next
  
  def initialize( data )
    @data = data
    @prev = nil
    @next = nil
  end
end

class UseList
  def initialize
    @firstNode = nil
    @lastNode = nil
  end
  
  def main
    makeNode
    searchNode
  end
  
  def makeNode
    buf = nil
    while buf != 0 do
      puts "整数を入力して下さい。（0を入力すると終了)"
      buf = intReader
      if buf != 0
        newNode = Node.new(buf)
        newNode.next = nil
        if @lastNode != nil
          @lastNode.next = newNode
          newNode.prev = @lastNode
          @lastNode = newNode
        else
          @firstNode = @lastNode = newNode
          newNode.prev = nil
        end
      end
    end
  end
  
  def searchNode
    buf = nil
    while buf != 0 do
      puts "検索する値を入力してください。（0を入力すると終了）"
      buf = intReader
      thisNode = @firstNode
      while thisNode != nil do
        if thisNode.data == buf
          puts "#{buf}発見。ノードを削除します"
          if thisNode.prev != nil
            thisNode.prev.next = thisNode.next
          else
            @firstNode = thisNode.next
          end
          
          if thisNode.next != nil
            thisNode.next.prev = thisNode.prev
          else
            @lastNode = thisNode.prev
          end
          break
        end
        thisNode = thisNode.next
      end
      if thisNode == nil
        puts "#{buf}を発見できなかった"
      end
    end
  end
  
  private
  def intReader
    gets().to_i
  end
end

node = UseList.new
node.main

応用例：自己組織化探索

　参考：サーチ「自己組織化探索」

class Node
  attr_reader :data
  attr_accessor :next
  
  def initialize( data )
    @data = data
    @next = nil
  end
end

class OrganizationSearch
  def initialize
    @firstNode = nil
    @lastNode = nil
  end
  
  def main
    makeNode
    searchNode
  end
  
  def makeNode
    buf = nil
    while buf != 0 do
      puts "整数を入力して下さい。（0を入力すると終了)"
      buf = intReader()
      if buf != 0
        newNode = Node.new(buf)
        newNode.next = nil
        if @lastNode != nil
          @lastNode.next = newNode
          @lastNode = newNode
        else
          @firstNode = @lastNode = newNode
        end
      end
    end
  end
  
  def searchNode
    buf = nil
    while buf != 0 do
      showNodeList()
      puts "検索する値を入力してください。（0を入力すると終了）"
      buf = intReader()
        if buf != 0
          thisNode = @firstNode
          tempNode = thisNode
          while thisNode != nil
            if thisNode.data == buf
              puts "#{buf} 発見"
              if thisNode != @firstNode
                tempNode.next = thisNode.next
                if @lastNode == thisNode
                  @lastNode = tempNode
                end
                thisNode.next = @firstNode
                @firstNode = thisNode
              end
              break
            end
            tempNode = thisNode
            thisNode = thisNode.next
          end
        end
      if thisNode == nil
        puts "#{buf} は見つかりません"
      end
    end
  end
  
  def showNodeList
    thisNode = @firstNode
    while thisNode != nil do
      print "#{thisNode.data} "
      thisNode = thisNode.next
    end
    print "¥n"
  end
  
  private
  def intReader
    gets().to_i
  end
end

org = OrganizationSearch.new
org.main