class DLinkedList:
    """ A user defined doubly linked list"""
    def __init__(self):
        self.head = None
        self.tail = None


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

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

        if self.head == None:       # empty list
            self.head = node
            self.tail = node
        else:                       # insert after tail
            self.tail.next = node
            node.prev = self.tail
            self.tail = node

    def insert_before(self, node, cur):
        """ Insert a node before 'cur' """
        pass

    def insert_after(self, node, cur):
        """ Insert a node after 'cur' """
        pass

    def insert_sorted(self, node):
        """ Insert a new node, maintain the sorted order """
        pass

    def find_place(self, node):
        """ Find the place for the node to insert, maintaining 
        ascending order """
        place = self.head
        while place != None and place.data < node.data:
            place = place.next
        return place

    def find_node(self, target):
        """ Find the location of the node containging"""
        place = self.head
        while place != None and place.data != target:
            place = place.next
        return place

    def remove_node(self, target):
        """ Remove the node containing 'target'
        """
        place = self.find_node(target)
        if place is None:
            return
        else:
            if place == self.head:
                self.head = self.head.next
                self.head.prev = None
            elif place == self.tail:
                self.tail = self.tail.prev
                self.tail.next = None
            else:
                place.prev.next = place.next
                place.next.prev = place.prev
        
class DListNode:
    """ The node class for list notes"""
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None