単方向リスト(ポインタ版)

ポインタを利用した単方向リスト。
容易に可変長のリストが作れるかわり、メモリ消費量が増えます。
操作を限定すればキューとしても、リストとしても使用できます。
発展版として、双方向リストや循環リスト、二分木が存在します。

class Node
  attr_reader	:data	#data(key) is immutable
  attr_accessor	:next	#next is mutable

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

class LinkedList

  def initialize
    @head = nil
  end

  def insertFront(node)
    unless @head
      @head = node
    else
      nextNode = @head
      @head = node
      @head.next = nextNode
    end
  end

  def insertRear(node)
    unless @head
      insertFront(node)
    else
      prevNode = @head
      while  prevNode.next != nil do
        prevNode = prevNode.next
      end
      prevNode.next = node
    end
  end

  def removeFront
    return unless @head
    nextNode = @head.next
    @head.next = nil
    @head = nextNode
  end

  def clear
    until @head == nil do
      removeFront
    end
  end

  def removeRear
    return unless @head
    unless @head.next
      removeFront
    else
      prevNode = @head
      targetNode = @head.next
      while targetNode.next != nil do
        prevNode = targetNode
        targetNode = targetNode.next
      end
      prevNode.next = nil
    end
  end

  def size
    count = 0
    currentNode = @head
    while currentNode != nil do
      count += 1
      currentNode = currentNode.next
    end
    return count
  end

  def print
    currentNode = @head
    while currentNode do
      printf "%d ", currentNode.data
      currentNode = currentNode.next 
    end
    puts
  end

  def get(index)
    if index > self.size
      return nil
    else
      node = @head
      index.times do
        node = node.next
      end
    end
    return node
  end

  def remove(index)
    if index >= self.size
      return nil
    elsif index == self.size - 1
      removeRear
    elsif index == 0
      removeFront
    else
      count = 0
      prevNode = nil 
      targetNode = @head
      while count < index do
        prevNode = targetNode
        targetNode = targetNode.next
        count += 1
      end
      nextNode = targetNode.next
      targetNode.next = nil	#clear reference to next node for GC
      prevNode.next = nextNode
    end
  end
end

知識確認→参考書確認→実装→バグ取り・動作確認。
実装以降で5時間ほどかかった。
動的に領域を確保するため、配列を使用しないポインタ実装を選択。
null参照が発生しやすい実装となるため、案の定バグがたくさん出た。
こうなっているはずという思い込みで時間を多くとられた。
紙に書き出せばきちんと解決できるので、早い段階で書き出しを検討したい。

今回は実装しなかったが、末尾参照のためのポインタ追加により
末尾ノードの操作が高速となる。
また、先頭・末尾以外へのノード挿入も実装していない。

あとは、末尾ノードまでリンクをたどっていく制御構造は

until currentNode.next == nil do

の方がわかりやすいかもしれない。