pythonclassoopmethodslinked-list

"add" method for linked list on python


I'm trying to write an add method for linked list on python, but it's not behaving as expected.

class linkedlist:
    def __init__(self):
       self.item=None
       self.next=None
    def add(self,val):
       self.next=self
       self.item=val

This doesn't work. When I create an object:

myobj=linkedlist()
myobj.add(1)
myobj.add(2)
print(myobj.next.item)

gives 2, instead of 1 as I would expect. Where did I go wrong?

I tried to look at Is it safe to replace a self object by another object of the same type in a method? but it's not helping.


Solution

  • You only have 1 object and 2 references pointing to it. You need to copy the list before adding to it:

    from copy import copy
    
    class linkedlist:
        def __init__(self):
           self.item=None
           self.next=None
        def add(self,val):
           self.next=copy(self)
           self.item=val
    
    myobj=linkedlist()
    myobj.add(1)
    myobj.add(2)
    print(myobj.next.item) # prints 1
    

    To clarify:

    print(myobj.item, id(myobj))
    print(myobj.next.item, id(myobj.next))
    

    with your code:

    2 140520931226768
    2 140520931226768 # same object!
    

    With mine:

    2 140520931224368
    1 140519593761456
    

    UPDATE:

    First your expectations are wrong, you should get 3 and 2, which are the values left in the list after you popped the head. To get these results you need to update what a points to. You could do this by adding return self at the end of add and pop methods, and the reassign a:

    from copy import copy
    
    class linkedlist:
        def __init__(self):
           self.item=None
           self.next=None
        def add(self,val):
           self.next=copy(self)
           self.item=val
           return self
        def pop(self):
           self=copy(self.next)
           return self
        
    a=linkedlist()
    a = a.add(1)
    a = a.add(2)
    a = a.add(3)
    a = a.add(4)
    a = a.pop()
    print(a.item)
    a = a.pop()
    print(a.item)
    

    But IMO this is rather ugly and I would rather use Allan's approach...