CODEWITHSUNDEEP
pythonlinked-liststack
user3776598
user3776598

Reputation: 426

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

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)

Upvotes: 3

Views: 2907

Answers (1)

thebjorn
thebjorn

Reputation: 27311

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

Upvotes: 2

Related Questions