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