Skip to content

Instantly share code, notes, and snippets.

@xxbinxx
Last active May 23, 2019 09:45
Show Gist options
  • Save xxbinxx/869e5ed1536b8655b19d4c8429640d66 to your computer and use it in GitHub Desktop.
Save xxbinxx/869e5ed1536b8655b19d4c8429640d66 to your computer and use it in GitHub Desktop.
linkedlists, stack (LIFO) implementation in python + Test cases
"""
LinkedLists, Stack implementation using python classes and methods
Added methods to our LinkedList class,
and use that to implement a Stack.
we have 4 functions below: insert_first, delete_first, push, and pop.
Think about the underlying working before checking out the code"""
class Element(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def append(self, new_element):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_element
else:
self.head = new_element
def insert_first(self, new_element):
"Insert new element as the head of the LinkedList"
new_element.next = self.head
self.head = new_element
return self.head
def delete_first(self):
"Delete the first (head) element in the LinkedList as return it"
deleted = None
if self.head:
deleted = self.head
self.head = self.head.next
return deleted
class Stack(object):
def __init__(self, top=None):
self.ll = LinkedList(top)
def push(self, new_element):
"Push (add) a new element onto the top of the stack"
return self.ll.insert_first(new_element)
def pop(self):
"Pop (remove) the first element off the top of the stack and return it"
return self.ll.delete_first()
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)
# Start setting up a Stack
stack = Stack(e1)
# Test stack functionality
stack.push(e2)
stack.push(e3)
print stack.pop().value
print stack.pop().value
print stack.pop().value
print stack.pop()
stack.push(e4)
print stack.pop().value
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment