""" A node is a container which encapsulates any type of data.
    The node object also has a reference to the NODE preceding and following
    said object."""
class Node(object):
 
    def __init__(self, data, prev, next):
        self.data = data
        self.prev = prev
        self.next = next
        
    def getNext(self):
        if self.next is not None:
            return self.next
        print('There\'s nothing next, trying prev')
        if self.prev is not None:
            return self.prev
        print('There\s nothing before either, just this one')
        return self
        
    def getPrev(self):
        if self.prev is not None:
            return self.prev
        print('There\'s nothing before, trying next')
        if self.next is not None:
            return self.next
        print('There\'s nothing next either, just this one')
        return self
        
    def getData(self):
        return self.data
 
""" A doubly-linked list implementation 
    NOTE: the getters and setters return a reference to a Node object,
    inside which is the data you're probably looking for. If you want to
    access data, remember; after you call a get or find, use .data"""
class DoubleList(object):
 
    head = None
    tail = None
    length = 0;
 
    """ Add a node to the list """
    def append(self, data):
        new_node = Node(data, None, None)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            new_node.next = None
            self.tail.next = new_node
            self.tail = new_node
        self.length = self.length + 1
 
    """ Find a node in the list, then remove it """
    def remove(self, node):
        current_node = self.head
 
        while current_node is not None:
            if current_node == node:
                # if it's not the first element
                if current_node.prev is not None:
                    current_node.prev.next = current_node.next
                    current_node.next.prev = current_node.prev
                # if its the last element
                elif current_node.next is None:
                    self.tail = current_node.prev
                    self.tail.prev = current_node.prev.prev
                    self.tail.next = None
                else:
                    # otherwise we have no prev (it's None), head is the next one, and prev becomes None
                    self.head = current_node.next
                    current_node.next.prev = None
 
            current_node = current_node.next
        self.length = self.length - 1
    
    def show(self):
        print("Show list data:")
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next
        print("*"*50)
        
    """ Find a node in the list by value comparison """
    def findNode(self, node_value):
        current_node = self.head
        
        while current_node is not None:
            if current_node.data == node_value:
                return current_node
            current_node = current_node.next
    
    """ Get a node by index position """
    def get(self, index):
        if index > self.length:
            return none
        elif index == 1:
            return self.head
        elif index == self.length:
            return self.tail
        else:
            current_node = self.head
            pos = 1
            while pos < index:
                current_node = current_node.next
                pos = pos + 1
            return current_node
    
    """ Checks if a node is in this list """
    def contains(self, node):
        current_node = self.head
        while current_node is not None:
            if current_node == node:
                return true
            current_node = current_node.next
        return false
        
    """ Get the length of this list """
    def getLength(self):
        return self.length
        
    """ Get the head of this list """
    def getHead(self):  # get head (;
        return self.head
        
    """ Get the tail of this list """
    def getTail(self):
        return self.tail