class CircularList:
    """ A user defined circular list"""
    def __init__(self):
        self.ref = None

    def __str__(self):
        """ String function """
        s = '['
        h = self.ref
        if h == None:
            return '[]'
        s += '(ref) ' + str(h.data)
        h = h.next
        while h != self.ref:
            if h != self.ref:
                s += ', '
            s += str(h.data)
            h = h.next

        s += ']'
        return s

    def __len__(self):
        """ Count the number of elements """
        h = self.ref
        if h == None:
            return 0
        if h.next == h:
            return 1
        else:
            h = h.next
            count = 1
            while h != self.ref:
                count += 1
                h = h.next
            return count

    def insert_before(self, node, indexer):
        """ Insert node before the node indexer"""
        node.next = indexer
        node.prev = indexer.prev
        indexer.prev.next = node
        indexer.prev = node
        

    def insert_ordered(self, node):
        """ Insert a node into an ordered list.
            Here the 'order' is assumed ascending
            from the 'ref' node."""
        if self.ref == None:   # empty list
            self.ref = node
            node.prev = self.ref
            node.next = self.ref
        elif len(self) == 1 or self.ref.data > node.data:
            # only one node, or insert before ref
            self.insert_before(node, self.ref)
            if node.data <= self.ref.data:   
                self.ref = node         # update the self.ref
        else:       # more than one node already in the list
            temp = self.ref.next
            while temp != self.ref and temp.data <= node.data:
                temp = temp.next
            self.insert_before(node, temp)

    def insert(self, node):
        """ Insert a value 'data'"""

        if self.ref == None:       # empty list
            self.ref = node
            node.prev = self.ref
            node.next = self.ref
        else:                       # insert after ref
            self.insert_after(node, self.ref)

    def insert_after(self, node, cur):
        """ Insert node with a value 'data' after 'cur'"""
        node.prev = cur
        node.next = cur.next
        cur.next.prev = node
        cur.next = node

    def traverse_forward(self):
        """ Traverse following 'next' """
        s = '['
        h = self.ref
        if h == None:
            return '[]'
        s += '(ref) ' + str(h.data)
        h = h.next
        while h != self.ref:
            if h != self.ref:
                s += ', '
            s += str(h.data)
            h = h.next

        s += ']'
        print(s)


    def traverse_backward(self):
        """ Traverse following 'prev' """
        s = '['
        h = self.ref
        if h == None:
            return '[]'
        s += '(ref) ' + str(h.data)
        h = h.prev
        while h != self.ref:
            if h != self.ref:
                s += ', '
            s += str(h.data)
            h = h.prev

        s += ']'
        print(s)

    def remove(self, target):
        """ Remove the first node that has the 'target' as data"""
        work = self.ref
        while work != None and work.data != target:
            work = work.next
        if work != None:   # found it
            if work == self.ref:   # set the reference to be next
                self.ref = work.next
            work.prev.next = work.next
            work.next.prev = work.prev


class DListNode:
    """ The node class for list notes"""
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None