1
\$\begingroup\$

I have tried Implementing Stacks Using Linked Lists, and would like some tips and tricks regarding optimizations or ways to simplify/compact processes.

It has 3 functions, Push, Pop, and Peek (For checking the top item in stacks)

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

class Stack:
    def __init__(self):
        self.bottom = None
        self.top = None
        self.length = 0

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

    def push(self, data):
        NewNode = Node(data)
        if self.length == 0:
            self.bottom = self.top = NewNode
        else:
            top = self.top
            self.top = NewNode
            self.top.next = top
        self.length += 1
        return self

    def pop(self):
        length = self.length
        top = self.top
        if length == 0:
            raise IndexError('No items in stack')
        elif self.bottom == top:
            self.bottom = None
        else:
            NextTop = self.top.next
            self.top = NextTop
        self.length -= 1
        return top.data

Output:

stack = Stack()           

stack.push(0)
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.peek())

print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())

stack.push(5)
stack.push(2)
print(stack.pop())
print(stack.pop())

-----------------------
3
3
2
1
0
2
5
-----------------------
\$\endgroup\$
1
\$\begingroup\$

First, I believe that the Node class is an implementation detail. You could move it inside the Stack or your could rename it _Node to indicate that it is private.

Next, I will refer you to this answer to a different CR question, also written by me: https://codereview.stackexchange.com/a/185052/106818

Specifically, points 2-7:

  1. ... consider how the Python list class (and set, and dict, and tuple, and ...) is initialized. And how the Mutable Sequence Types are expected to work.

    Because your code is implementing a "mutable sequence type." So there's no reason that your code shouldn't work the same way. In fact, if you want other people to use your code, you should try to produce as few surprises as possible. Conforming to an existing interface is a good way to do that!

  2. Create an initializer that takes a sequence.

    class Stack:
        def __init__(self, seq=None):
            ...
            if seq is not None:
                self.extend(sequence)
    
  3. Implement as many of the mutable sequence operations as possible.

  4. Use the standard method names where possible: clear, extend, append, remove, etc.

  5. Implement special dundermethods (method names with "double-underscores" in them: double-under-methods, or "dundermethods") as needed to make standard Python idioms work:

    def __contains__(self, item):
        for i in self:
            ...
    
    def __iter__(self):
        node = self.head
    
        while node:
            yield node.value
            node = node.next
    
  6. Implement your test code using standard Python idioms, to prove it's working and to show developers how your code should be used!

Finally, some direct code criticisms:

  1. Don't use equality comparisons with None. Use is None or is not None instead. This is a PEP-8-ism, and also actually faster.

  2. You don't really use self.bottom for anything. Go ahead and delete it.

  3. Don't use CamelCase variable names. That's another PEP-8 violation. Use snake_case for local variables.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.