単方向リスト（カーソル版）

ポインタではなく配列を利用した単方向リスト。
空き領域の管理が面白かった。

#linkedlist by cursor

class Node

  attr_reader	:data
  attr_accessor	:next 

  def initialize(obj)
    @data = obj
    @next = nil
  end
end

class LinkedList

  attr_reader	:size

  def initialize(size)
    @list = Array.new(size)
    @head = nil
    @tail = nil
    @size = 0
    @free = Array.new(0)
    (size - 1).step(0, -1){|i|
      @free << i
    }
  end

  def showFields
    printf "@size={#@size} @head={#@head} @tail={#@tail}\n"
  end

  def insertFront(node)
   if @size == 0
     #初回追加時
     @head = @free.pop
     @tail = @head
     @list[@head] = node
     @size += 1
   else
     #2回目以降
     return nil unless newHead = @free.pop
     node.next = @head
     @list[newHead] = node
     @head = newHead
     @size += 1
   end 
  end

  def insertRear(node)
   if @size == 0
     #初回追加
     @head = @free.pop
     @tail = @head
     @list[@tail] = node
     @size += 1
   else
     #2回目以降
     return nil unless newTail = @free.pop
     @list[@tail].next = newTail
     @list[newTail] = node 
     @tail = newTail
     @size += 1
   end
  end

  def removeFront
    if @size > 0
      @tail = nil if @size == 1 
      @free.push(@head)
      newHead = @list[@head].next
      @list[@head] = nil
      @head = newHead
      @size -= 1
    end
  end

  def clear
    until @size == 0 do
      removeFront
    end
  end

  def removeRear
    if @size == 1
      removeFront
    elsif @size > 1
      targetIndex = @list[@head].next
      prevTail = @head
      until targetIndex == @tail do
        prevTail = targetIndex
        targetIndex = @list[prevTail].next 
      end 
      @list[@tail] = nil
      @list[prevTail].next = nil
      @free.push(@tail)
      @tail = prevTail
      @size -= 1
    end
  end

  def to_s
    string = String.new
    currentIndex = @head
    until currentIndex == nil do
      string = string + @list[currentIndex].data.to_s + " "
      currentIndex = @list[currentIndex].next
    end
    return string
  end

  def get(index)
    node = nil
    if 0 <= index && index < @size
      c = 0
      node = @list[@head]
      until c == index do
        node = @list[node.next]
        c += 1
      end
    end
    return node
  end

  def remove(index)
    if index < 0
      return
    elsif index == 0
      removeFront
    elsif index == @list.size - 1
      removeRear 
    else
      c = 1
      prevIndex = @head
      targetIndex = @list[@head].next
      #対象のindexまで進む
      until c == index do
        prevIndex = targetIndex
        targetIndex = @list[prevIndex].next
        c += 1
      end
      #前のノードのnextを削除対象ノードのnextにする
      @list[prevIndex].next = @list[targetIndex].next
      #削除対象ノードをリストからクリア
      @list[targetIndex] = nil
      #フリースタックに削除indexをpush
      @free.push(targetIndex) 
      @size -= 1
    end
  end
end

実装→バグ取り・確認で合計6時間ほど。
時間がかかった理由としては、
「自分のなかでどういう動作のものを作るのかというのがはっきりしていなかった」から。
また、「テストをしっかり行えていなかった」ことも原因となった。

両者ともに、配列、変数の値のトレースで解決した。