class Node:
  def __init__(self, data, next=None, prev=None):
    self.data = data
    self.next = next
    self.prev = prev

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None

  def appendNode(self, node):
    '''
    Adds a node to the end of the list
    '''
    if not self.head:
      #if the first node, set it as the head, and tail of the ll
      self.head = node
      self.tail = node
      node.next = None
      node.prev = None
    else:
      #else set it as the tail of the ll
      node.prev = self.tail
      node.prev.next = node
      self.tail = node

  def insertNode(self, nodeBefore, nodeAfter, node):
    '''
    Inserts a node between two other nodes on the list
    '''
    if not nodeBefore:
      self.head = node
      node.prev = None
      node.next = nodeAfter
      nodeAfter.prev = node
    elif not nodeAfter:
      self.tail = node
      node.prev = nodeBefore
      node.next = None
      nodeBefore.next = node
    else:
      nodeBefore.next = node
      nodeAfter.prev = node
      node.prev = nodeBefore
      node.next = nodeAfter

  def searchNodes(self, search):
    currentNode = self.head
    while currentNode != None:
      if currentNode.data == search:
        return currentNode
      currentNode = currentNode.next
    return -1

  def printNodes(self):
    currentNode = self.head
    while currentNode != None:
      print(currentNode.data)
      currentNode = currentNode.next

n1 = Node("First Node")
ll = LinkedList()
ll.appendNode(n1)
n2 = Node("Second Node")
ll.appendNode(n2)
n4 = Node("Fourth Node")
ll.appendNode(n4)
print(n4.prev.data)
print(n2.next.data)
print(n2.prev.data)
print(n1.next.data)
n3 = Node("Third Node")
ll.insertNode(n2, n4, n3)
print("These are the nodes: {}, {}, {}, {}".format(
  n1.data, n1.next.data, n1.next.next.data, n1.next.next.next.data
))
print("This is the head and tail of the Linked List: {}, {}".format(
  ll.head.data, ll.tail.data
))
n5 = Node("Fifth Node")
ll.insertNode(None, n1, n5)
print("This is the head and tail of the Linked List: {}, {}".format(
  ll.head.data, ll.tail.data
))
n6 = Node("Sixth Node")
ll.insertNode(ll.tail, None, n6);
print("This is the head and tail of the Linked List: {}, {}".format(
  ll.head.data, ll.tail.data
))
print("These are the nodes: {}, {}, {}, {}, {}, {}".format(
  ll.head.data,
  ll.head.next.data,
  ll.head.next.next.data,
  ll.head.next.next.next.data,
  ll.head.next.next.next.next.data,
  ll.head.next.next.next.next.next.data
))
print(ll.searchNodes("Fifth Node"))
print(ll.searchNodes("Seventh Node"))
ll.printNodes()