kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_3_C 続き

解説は明日読もう

読んで早々、

また、リストの先頭を指す特別なノードを設置することによって実装を
簡略化することができます。
このノードは「番兵」と呼ばれるもので

あっ

言われてみると!

headで先頭、tailで末尾を覚えるって代わりに
nilというノードを定義して
nil.nextが先頭を、nil.prevが末尾を指すようにするのか

それでうまくいくのか?
・・・いくな
場合分けがキレイになくなってしまう
すばらしい

最初のひとつの追加
先頭に追加
途中に追加
末尾に追加
先頭を削除
途中を削除
末尾を削除
最後のひとつを削除

これくらいの場合について検証が必要
途中に追加、途中を削除、を先に考えてから他のケースが同じように
考えられるかどうかを考える、という順番がよさそう
でも途中で納得したので全部はやってない
nilのおかげで双方向リストが輪になってて、どこにも特別なノードが存在しないので
場合分けが必要ないことが直感的にわかる
nilも他と同じ輪の構成要素で、たまたまちょっとマークがついてるにすぎないので

ただ名前はboundとかの方がイメージしやすかったかな、という気もしないでもない
nilが出てきそうなところに出てくるのは確かなんだけど

とはいうもののそれなりにややこしいのでassertを使ってテストも書いてみた
テスト部分はジャッジには関係ないけど最終版の全ソース(このままでもAC)

#! /usr/local/bin/python3
# coding: utf-8

class DoublyLinkedNode:

    def __init__(self, x):
        self.value = x
        self.prev = None
        self.next = None

    def str(self):
        return str(self.value)

class DoublyLinkedList:

    def __init__(self):
        self.nil = DoublyLinkedNode(None)
        self.nil.prev = self.nil.next = self.nil

    def insert(self, x):
        node = DoublyLinkedNode(x)
        node.prev = self.nil
        node.next = self.nil.next
        self.nil.next.prev = node
        self.nil.next = node

    def search(self, x):
        node = self.nil.next
        while node is not self.nil and node.value != x:
            node = node.next
        return node

    def delete_node(self, node):
        # print("delete_node:", node.value, node.prev.value, node.next.value)
        if node is self.nil:
            return
        next = node.next
        node.prev.next = next
        next.prev = node.prev

    def delete(self, x):
        self.delete_node(self.search(x))

    def delete_first(self):
        self.delete_node(self.nil.next)

    def delete_last(self):
        self.delete_node(self.nil.prev)

    def str(self):
        node = self.nil.next
        v = ""
        while node is not self.nil:
            v += node.str()
            node = node.next
            if node is not self.nil:
                v += " "
        return v

    def debug_str(self):
        v = self.nil.next.str() + " "
        v += self.nil.prev.str() + " | "
        v += self.str()
        return v

def test():
    dll = DoublyLinkedList()
    assert dll.debug_str() == "None None | "
    dll.insert(1)
    assert dll.debug_str() == "1 1 | 1"
    dll.insert(2)
    assert dll.debug_str() == "2 1 | 2 1"
    dll.insert(3)
    assert dll.debug_str() == "3 1 | 3 2 1"
    dll.delete(2)
    assert dll.debug_str() == "3 1 | 3 1"
    dll.delete(1)
    assert dll.debug_str() == "3 3 | 3"
    dll.delete(3)
    assert dll.debug_str() == "None None | "
    dll.insert(1)
    assert dll.debug_str() == "1 1 | 1"
    dll.insert(2)
    assert dll.debug_str() == "2 1 | 2 1"
    dll.delete(2)
    assert dll.debug_str() == "1 1 | 1"
    dll.delete(1)
    assert dll.debug_str() == "None None | "
    dll.insert(1)
    assert dll.debug_str() == "1 1 | 1"
    dll.insert(2)
    assert dll.debug_str() == "2 1 | 2 1"
    dll.delete_first()
    assert dll.debug_str() == "1 1 | 1"
    dll.delete_first()
    assert dll.debug_str() == "None None | "
    dll.insert(1)
    assert dll.debug_str() == "1 1 | 1"
    dll.insert(2)
    assert dll.debug_str() == "2 1 | 2 1"
    dll.delete_last()
    assert dll.debug_str() == "2 2 | 2"
    dll.delete_last()
    assert dll.debug_str() == "None None | "

def main():
    n = int(input())
    dll = DoublyLinkedList()
    # print(dll.debug_str())

    from sys import stdin

    for _ in range(n):
        line = stdin.readline().split()
        if line[0] == "insert":
            dll.insert(int(line[1]))
        elif line[0] == "delete":
            dll.delete(int(line[1]))
        elif line[0] == "deleteFirst":
            dll.delete_first()
        elif line[0] == "deleteLast":
            dll.delete_last()
        # print(dll.debug_str())

    print(dll.str())

test()
main()