Stack - Implemented as Singly Linked List

Question

Note: I do know that Python libraries provide a Linked List and Stack. This implementation has been done to practice Python and some of the data structures and Algorithms.

I have implemented Stack as a Singly Linked-List, feel free to make suggestions. Note: code works

Targeted Big O:

search: O(n), Push and Pop: O(1)

Methods:

push(value)- for insertion
pop()- for removing
is_empty()- to check if empty
peek()- look at what head holds without poping
stack_search(value)-find a value
length()-get size

Classes:

class Node:
 def __init__(self, value):
 self.data = value
 self.front = None 
class Stack:
 def __init__(self):
 self.head = None
 self.count = 0
 def push(self, value):
 #make new node
 new_node = Node(value)
 self.count += 1
 if self.head is not None:
 #make new node point to the old node
 new_node.front = self.head
 # make head point to the new element
 self.head = new_node
 def is_empty(self):
 if self.head is None:
 return True
 else:
 return False
 def pop(self):
 if not self.is_empty():
 self.count -= 1
 temp = self.head.data
 # make head point to the node after the node that will be poped
 self.head = self.head.front
 return temp
 else:
 print("can not pop items from an empty list")
 def peek(self):
 return self.head.data
 def __iter__(self):
 # start from the node that head refers to
 node = self.head
 while node:
 yield node
 node = node.front
 def stack_search(self, value):
 # start from the head
 p = self.head
 while p is not None:
 # make p reference to next node
 if p.front is not None:
 if p.data == value:
 print("Found value")
 return p.data
 p = p.front
 else:
 print("fail")
 return 0
 def length(self):
 return self.count

Test:

from stack_Queue import Stack
def main():
 print("-------Test Stack----------")
 print("------Test push-------")
 my_stack = Stack()
 test_list = [1, 2, 3, 4, -2000000, 'a', 500000, 50]
 for i in test_list:
 my_stack.push(i)
 print("-------Push Done------")
 print("-------Dump stack-----")
 for i in my_stack:
 print(i.data)
 print("-----Dump stack Done---")
 print("----check count-------")
 print("should be: 8")
 print(my_stack.length())
 print("-----check count Done--")
 print("-------Test pop $ print remaining stack--------")
 my_stack.pop()
 for i in my_stack:
 print(i.data)
 print("-----Test pop Done-----")
 print("-----Test search-------")
 x = my_stack.stack_search('a')
 print(x)
 print("---Test search Done---")
 print("-----Test pop - full stack & print what is being poped-----")
 while my_stack.length() > 0:
 x = my_stack.pop()
 print(x)
 print("-----Test pop Done-----")
 print("-----Test Empty Stack-----")
 for i in my_stack:
 print(i.data)
 print("---------Done---------")
if __name__ == "__main__":
 main()

Result:

-------Test Stack----------
------Test push-------
-------Push Done------
-------Dump stack-----
50
500000
a
-2000000
4
3
2
1
-----Dump stack Done---
----check count-------
should be: 8
8
-----check count Done--
-------Test pop $ print remaining stack--------
500000
a
-2000000
4
3
2
1
-----Test pop Done-----
-----Test search-------
Found value
a
---Test search Done---
-----Test pop - full stack & print what is being poped-----
500000
a
-2000000
4
3
2
1
-----Test pop Done-----
-----Test Empty Stack-----
---------Done---------
Process finished with exit code 0

Answer 1

• Your stack_search function re-implements loop over your linked-list. Instead of that you can use your __iter__ itself to keep in DRY. Plus it should True or False instead of 1 and 0.

  The Pythonic way will be implement __contains__ to check if your container type contains an item. Then you could simply do 'a' in my_stack.

  def __contains__(self, value):
   return value in (node.data for node in self)
  

• Instead of length method implement __len__. This will work with Python's built-in len().

  Plus after defining this you won't need the method is_empty either as __len__ can be used to check for falsyness: if my_stack: .... You could also define __bool__ based on self.head for checking falsiness instead of using __len__, but it would be redundant in my opinion.

• pop() should raise an exception when the stack is empty, for example list.pop, dict.pop, deque.pop all raise some error for it.

• Stack().peek() currently raises an AttributeError. Instead of that you should be raising some custom exception when the stack is empty.