Implementing a stack using a linked list in python. Issues with pop method and questions about mutability

Question

I am trying to implement a stack using a linked list based off of just a node class. I am having some issues with the pop method of my class which doesn't seem to exhibit mutability. When I use the pop class method it returns the top of the stack correctly, but it fails to update the stack.

x=stack_linked(1)
x=x.insert(2)
x=x.insert(3)
x.print() # This is correct and prints 3,2,1
print(x.pop()) # This is correct and prints 3, but doesn't actually modify my list
x.print() # This prints 3,2,1

Why is self not mutable? Also how can I modify my class without completely blowing it up or creating a wrapper for it? Here is my class.

class stack_linked(object):
    def __init__(self,data):
     self.data=data
     self.next=None

    def insert(self,front):
     front=stack_linked(front)
     front.next=self
     return front

    def peek(self):
     if self==None:
        return None
     else   
        return self.data

    def pop(self):
     front=self
     self=self.next # some sort of issue here
     return front


    def print(self):
     x=self
     if x==None:
        print("Empty")
     else:
        print(x.data)
     while x.next !=None:
        x=x.next
        print(x.data)

Assigning to self in an instance method doesn't cause the whole instance to be replaced. — jonrsharpe
– jonrsharpe, Commented Jan 9, 2017 at 0:01

thebjorn · Accepted Answer · 2017-01-09 00:11:25Z

2

You're a little bit limited by only having nodes and forward links, but it is possible to implement pop(-first) by making the first node subsume the second node:

class stack_linked(object):
    def __init__(self, data):
        self.data = data
        self.next = None

    def pop(self):
        data = self.data
        nxt = self.next
        if nxt is None:
            self.data = self.next = None
        else:
            self.data = nxt.data
            self.next = nxt.next
            nxt.next = None
        return data

answered Jan 9, 2017 at 0:11

thebjorn

27.6k12 gold badges107 silver badges152 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user3776598 Over a year ago

Also Why set nxt.next=None?

thebjorn Over a year ago

nxt.next = None is there to break any cycles so the garbage collector will have an easier time. Semantically it is also correct, since the nxt object doesn't exist anymore, and thus shouldn't be pointing to a live object.

Collectives™ on Stack Overflow

Implementing a stack using a linked list in python. Issues with pop method and questions about mutability

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related