#
# Linked list
#
class linked_list:
    def __init__(self):
        self.next = self
        self.prev = self
        self.value = None

def map (f, l):
    itr = l.next
    while itr != l:
        f (itr.value)
        itr = itr.next

def list_print (l):
    i = l.next
    while i != l:
        print (i.value)
        i = i.next

def list_insert_after (p, x):
    new_elem = linked_list()
    new_elem.value = x
    new_elem.prev = p
    new_elem.next = p.next
    new_elem.prev.next = new_elem
    new_elem.next.prev = new_elem

def list_delete (p):
    # assert p != sentinel
    p.prev.next = p.next
    p.next.prev = p.prev

def list_clear (l):
    # l is the sentinel
    l.next = l
    l.prev = l