A two-way line

Build a class Line: a line of values that can grow and shrink at both ends. Every method except to_list must take O(1) time, however long the line is.

L = Line()
L.add_last(1); L.add_last(2); L.add_first(0)
L.to_list()        # [0, 1, 2]
L.remove_first()   # 0
L.remove_last()    # 2
len(L)             # 1
L.remove_last()    # 1
L.remove_last()    # None: the line is empty

collections.deque does exactly this, so it is switched off. Build it yourself from nodes. A Python list will not do either: insert(0, x) and pop(0) move every item, so they are O(n).

Limits

• Up to 200,000 operations in one test.
• The tests call the methods and compare what each one returns.