Last active
May 23, 2019 09:45
-
-
Save xxbinxx/869e5ed1536b8655b19d4c8429640d66 to your computer and use it in GitHub Desktop.
linkedlists, stack (LIFO) implementation in python + Test cases
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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