DoublyLinkedList

class Frob(object):
    def __init__(self, name):
        self.name = name
        self.before = None
        self.after = None
    def setBefore(self, before):
        # example: a.setBefore(b) sets b before a
        self.before = before
    def setAfter(self, after):
        # example: a.setAfter(b) sets b after a
        self.after = after
    def getBefore(self):
        return self.before
    def getAfter(self):
        return self.after
    def myName(self):
        return self.name
        
def insert(atMe, newFrob):
    """
    atMe: a Frob that is part of a doubly linked list
    newFrob:  a Frob with no links 
    This procedure appropriately inserts newFrob into the linked list that atMe is a part of.    
    """
    if atMe.myName() <= newFrob.myName():
        next = atMe.getAfter()
        before = atMe
        while next != None and next.myName() < newFrob.myName():
            before = next
            next = next.getAfter()            
        if next == None:
            before.setAfter(newFrob)
            newFrob.setBefore(before)
        else:
            temp = next.getBefore()
            next.setBefore(newFrob)
            newFrob.setBefore(temp)
            temp.setAfter(newFrob)
            newFrob.setAfter(next)
            
    if atMe.myName() > newFrob.myName():
        next = atMe.getBefore()
        after = atMe
        while next != None and next.myName() > newFrob.myName():
            after = next
            next = next.getBefore()          
        if next == None:
            after.setBefore(newFrob)
            newFrob.setAfter(after)
        else:
            temp = next.getAfter()
            next.setAfter(newFrob)
            newFrob.setAfter(temp)
            temp.setBefore(newFrob)
            newFrob.setBefore(next)  
            
def findFront(start):
    """
    start: a Frob that is part of a doubly linked list
    returns: the Frob at the beginning of the linked list 
    """
    # Your Code Here
    if start.getBefore() == None:
        return start
    else:
        return findFront(start.getBefore())