class DLLNode(object):
    """A Node in a doubly-linked list"""

    def __init__(self, data, prev_link=None, next_link=None):
        '''(DLLNode, object, DLLNode, DLLNode) -> NoneType

        Create a new DLLNode containing object, with previous node
        prev_link, and next node next_link.
        '''
        # Representation invariant:
        # data is an object
        # prev_link is a DLLNode
        # next_link is a DLLNode
        # data is the item held in this node
        # prev_link is the node immediately before (closer
        # to the head of the list than) this node
        # next_link is the node immediately after (closer
        # to the tail of the list than) this node

        self.data = data
        self.prev_link = prev_link
        self.next_link = next_link

    def __str__(self):
        '''(DLLNode) -> str
        Return a str representation of this DLLNode.
        '''

        return str(self.data)


class DoublyLinkedList(object):
    """A doubly linked list"""

    def __init__(self):
        '''(DoublyLinkedList) -> NoneType
        Create a new empty DoublyLinkedList
        '''
        # Representation invariant:
        # _head is a DLLNode
        # _tail is a DLLNode
        # if the list is empty:
        #     _head = _tail = None
        # if the list is non-empty:
        #     _head is the first node in the list
        #     _tail is the last node in the list
        #     if nodeA and nodeB are both nodes in this list and nodeA is
        #     before (closer to the head than) nodeB:
        #         nodeA.next_link[.next_link]* = nodeB
        #             ([.next_link]* = 0 or more repetitions of .next_link)
        #         nodeB.prev_link[.prev_link]* = nodeA

        self._head = DLLNode(None)
        self._tail = DLLNode(None)

        self._head.next_link = self._tail
        self._tail.prev_link = self._head

    def __str__(self):
        '''(DoublyLinkedList) -> str

        Return a str representation of the contents of this
        DoublyLinkedList.
        '''
        # current location in the list
        curr = self._head
        answer = "head =  "

        # loop till the list ends
        while (curr != self._tail.next_link):
            answer += str(curr.data) + " -> "
            # move to the next node
            curr = curr.next_link

        # formatting
        answer = answer[:-4]
        answer += " = tail"

        return answer

    def add_head(self, add_obj):
        '''(DoublyLinkedList, object) -> NoneType
        Add add_obj to the head of this DoublyLinkedList.
        '''
        # if self does not hold a value. Give the head the value
        if (self._head.data is None):
            self._head.data = add_obj

        # if head has value
        else:
            # create new node
            node = DLLNode(add_obj)

            # set the connections of the list to set head
            self._head.prev_link = node
            node.next_link = self._head

            # the new node is head of the list
            self._head = node

    def add_tail(self, add_obj):
        '''(DoublyLinkedList, object) -> NoneType
        Add add_obj to the tail of this DoublyLinkedList.
        '''
        # if tail has no value, set the value
        if (self._tail.data is None):
            self._tail.data = add_obj

        # if tail has a value
        else:
            # create a new node
            node = DLLNode(add_obj)

            # set the connections to make the new node the tail
            self._tail.next_link = node
            node.prev_link = self._tail

            # set tail as the node
            self._tail = node

    def add_index(self, add_obj, add_index):
        '''(DoublyLinkedList, object, int) -> NoneType
        Add add_obj to this DoublyLinkedList at index add_index.
        '''
        # create the node to be placed in the list
        node = DLLNode(add_obj)

        # current position in the list
        curr = self._head

        # loops through the list to find the location to be added
        for i in range(add_index-1):
            curr = curr.next_link

        # get the next node
        n_curr = curr.next_link

        # point to the new node from the left
        curr.next_link = node
        node.prev_link = curr

        # point to the new node from the right
        n_curr.prev_link = node
        node.next_link = n_curr

    def remove_head(self):
        '''(DoublyLinkedList) -> object
        Remove and return the first item in this DoublyLinkedList.
        '''
        # get the head to be returned
        holder = self._head

        # remove the head from the rest of the list
        self._head = self._head.next_link

        # return the old head
        return holder

    def remove_tail(self):
        '''(DoublyLinkedList) -> object
        Remove and return the last item in this DoublyLinkedList.
        '''
        # get the tail of the list
        holder = self._tail

        # remove the tail from the list
        self._tail = self._tail.prev_link

        # return the old tail
        return holder

    def remove_index(self, remove_index):
        '''(DoublyLinkedList, int) -> object

        Remove and return the item at index remove_index in this
        DoublyLinkedList.
        '''
        # current location in the list
        curr = self._head

        # loop through the list to find the location
        for i in range(remove_index-1):
            curr = curr.next_link

        # node to be removed
        remove = curr.next_link

        # get the next node after the node to be removed
        n_curr = remove.next_link

        # point the node before the remove location to the node after the
        # remove location. Thus removing the wanted node
        curr.next_link = n_curr
        n_curr.prev_link = curr

        return remove