連結リスト

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

class Node
    attr_accessor :key, :nexts, :prev
end

class LinerList
    def initialize
        @null = Node.new
        @null.nexts = @null
        @null.prev = @null
    end

    def search(key)
        cur = @null.nexts
        while cur != @null and cur.key != key do
            cur = cur.nexts
        end
        cur
    end

    def delete(t)
        return if t == @null
        t.prev.nexts = t.nexts
        t.nexts.prev = t.prev
    end

    def delete_first
        delete @null.nexts
    end

    def delete_last
        delete @null.prev
    end

    def delete_key(key)
        delete(search(key))
    end

    def insert(key)
        x = Node.new
        x.key = key
        x.nexts = @null.nexts
        @null.nexts.prev = x
        @null.nexts = x
        x.prev = @null
    end

    def dump
        cur = @null.nexts
        keys = []
        while cur != @null do
            keys << cur.key
            cur = cur.nexts
        end
        puts keys.join(" ")
    end
end

n = gets.to_i
list = LinerList.new
n.times do
    com, key = gets.split(" ")
    if com == "insert"
        list.insert(key.to_i)
    elsif com == "delete"
        list.delete_key(key.to_i)
    elsif com == "deleteFirst"
        list.delete_first
    elsif com == "deleteLast"
        list.delete_last
    end
    # list.dump
end
list.dump