Ordered Doubly Linked List

Question

Ok A question from assignment says to create an ordered doubly linked list...such that each object with lexicographically smaller name comes "Before" the other One...Like names in a Dictionary...also objects with same name can be arranged in any order...

To link two objects I have setBefore() and setAfter() method... and I have done this much...but still don't know where I'm doing wrong..may be a little guidance from you guys can help me...

atMe is an object that is already present in the doubly linked list and newFrob is an object to be inserted...

def insert(atMe, newFrob):
    if newFrob.myName() < atMe.myName():
        if atMe.getBefore() == None:
            atMe.setBefore(newFrob)
            newFrob.setAfter(atMe)
        elif atMe.getBefore().myName()<newFrob.myName():
            atMe.getBefore().setAfter(newFrob)
            newFrob.setBefore(atMe.getBefore)
            atMe.setBefore(newFrob)
            newFrob.setAfter(atMe)
        else:
            insert(atMe.getBefore(),newFrob)

    elif newFrob.myName() > atMe.myName():
        if atMe.getAfter() == None:
            atMe.setAfter(newFrob)
            newFrob.setBefore(atMe)
        elif atMe.getAfter().myName()>newFrob.myName():
            atMe.getAfter().setBefore(newFrob)
            newFrob.setAfter(atMe.getAfter)
            atMe.setAfter(newFrob)
            newFrob.setBefore(atMe)
        else:
            insert(atMe.getAfter(),newFrob)

    elif newFrob.myName()==atMe.myName():
        if atMe.getAfter() != None:
            newFrob.setAfter(atMe.getAfter())
        newFrob.setBefore(atMe)
        if atMe.getAfter() != None:
            atMe.getAfter().setBefore(newFrob)
        atMe.setAfter(newFrob)

And this is the Frob Class to be used...

class Frob(object):
    def __init__(self, name):
        self.name = name
        self.before = None
        self.after = None
    def setBefore(self, before):
        self.before = before
    def setAfter(self, after):
        self.after = after
    def getBefore(self):
        return self.before
    def getAfter(self):
        return self.after
    def myName(self):
        return self.name

where Before and After are links to left and right objects in double linked list... objects from this class are to be inserted to double linked list...

Example:

a=Frob('foo')
b=Frob('bar')
c=Frob('frob')
d=Frob('code')

code                             output
insert(a,b)                   bar->foo
insert(a,c)                   bar->foo->frob
insert(b,d)                   bar->code->foo->frob

now suppose

code                             output
insert(b,Frob('code'))        bar->code->code->foo->frob

@downvoters: Please explain. As I can see, OP had clearly laid down the question, presented his best effort and still he cannot find a solution and would require help. He may not be quite apt with Python but we should help him out instead of downvoting. — Abhijit
please explain what you mean exactly by a Ordered Doubly Linked List? explain how it should work, what methods it should implement... etc etc... — Inbar Rose
what you described is a normal linked-list, where are the 'ordered' and 'double' parts coming from? — Inbar Rose
I do not see anything particularly incorrect about your solution. In my experience, it is somewhat odd to have the insert function traverse the list recursively like this, but there is nothing wrong with doing it that way. Can you tell us about a problem you are having? Like an example of a series of inserts after which the list is wrong? — ken.ganong

Blckknght Blckknght · Accepted Answer · 2013-01-14T15:43:13

The issue is in this line (and an equivalent one when you're moving the other direction):

newFrob.setBefore(atMe.getBefore)

You're missing a set of parentheses after atMe.getBefore, so you end up passing the bound method itself to newFrob.setBefore rather than the value that would be returned by that method. This is an easy typo to make, so I wouldn't feel too bad about missing it on your assignment.

I found the error by trying the following sequence of inserts and inspecting the values (I've summarized the ones that worked OK with comments):

>>> a = Frob("a")
>>> b = Frob("b")
>>> c = Frob("c")
>>> d = Frob("d")
>>> insert(a, b) # list is a<->b
>>> insert(a, d) # list is a<->b<->d
>>> insert(a, c) # list is a<->b<->c->?
>>> c.getAfter()
<bound method Frob.getAfter of <__main__.Frob object at 0x000000000318EBA8>>

That object mentioned at the end is b, which lead me to find the error in the code.

Ordered Doubly Linked List

1 Answers