Stack - Implemented as Singly Linked List

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.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
# make head point to the new element

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
# make head point to the node after the node that will be poped
return temp
else:
print("can not pop items from an empty list")

def peek(self):

def __iter__(self):
# start from the node that head refers to
while node:
yield node
node = node.front

def stack_search(self, value):
# start from the 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

• 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.