pythonでDoubly Linked List

AOJのALDS1_3-C Doubly Linked List に以下のコードで挑戦してみたが、9/10で時間切れで落とされてしまう。

どうやら、insert/deleteXXX操作回数が多くなると性能が出ないらしい。 ローカル環境で操作の進み具合を確認したところ、現在の100倍くらいに高速化しないと制限時間内に終わりそうにない。

仕方がないので、自分で実装するのはあきらめて collections.deque を使用することにする。

# -*- coding: utf-8 -*-
"""
doubly linked list
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp
"""
# 9/10 で時間超過になる。

from collections import namedtuple


class DualLinkList(object):
    def __init__(self):
        self.nil = namedtuple('Node', ['key', 'prev', 'next'])
        self.nil.next = self.nil
        self.nil.prev = self.nil

    def insert(self, key):
        x = namedtuple('Node', ['key', 'prev', 'next'])
        x.key = key
        x.next = self.nil.next
        self.nil.next.prev = x
        self.nil.next = x
        x.prev = self.nil

    def listSearch(self, key):
        cur = self.nil.next
        while cur != self.nil and cur.key != key:
            cur = cur.next
        return cur

    def deleteNode(self, t):
        if t == self.nil:
            return
        t.prev.next = t.next
        t.next.prev = t.prev
        # del t

    def deleteFirst(self):
        self.deleteNode(self.nil.next)

    def deleteLast(self):
        self.deleteNode(self.nil.prev)

    def deleteKey(self, key):
        self.deleteNode(self.listSearch(key))

    def get_keys(self):
        results = []
        cur = self.nil.next
        while cur != self.nil:
            results.append(cur.key)
            cur = cur.next
        return results

    def print(self):
        cur = self.nil.next
        while cur != self.nil:
            print(cur.key)
            cur = cur.next


def process_instructions(dll, insts):
    # line_count = 1
    for ins in insts:
        # print('processing line: {0}'.format(line_count))
        # line_count += 1
        try:
            code, key = ins.split()
        except ValueError:
            code = ins
        if code == 'insert':
            dll.insert(int(key))
        elif code == 'delete':
            dll.deleteKey(int(key))
        elif code == 'deleteFirst':
            dll.deleteFirst()
        elif code == 'deleteLast':
            dll.deleteLast()
        else:
            raise ValueError
    return dll.get_keys()



if __name__ == '__main__':
    # データの入力
    num = int(input())
    data = [input() for x in range(num)]
    #data = []
    #with open('ALDS1_3_C_in9.txt') as f:  # ファイルの読み込み
    #    for line in f:
    #       data.append(line.strip())
    #data = data[1:]

    # リストの処理
    dll = DualLinkList()
    results = process_instructions(dll, data)

    # 結果の表示
    print('{0}'.format(' '.join(map(str, results))))