New : Single Linked List Python
Update 9-2-19: reformatted the code block. Should be easier to copy/paste so you can tinker.
Pytest is now included in this post, it is included at the bottom. I have added a new test to show that any valid python object can be stored in the Single Linked list. I may be cleaning this up today and adding a 'reverse' method.
Ok this time It is a single linked list with python.
I still couldn't manage to follow zeds vocabulary. I don't know why. I named stuff my way and was able to do it and at the end I was able to change it to how he had stuff and understood. Not sure why this was such an issue for me. I'll work on that some more, but this is a completed , tested sinlge linked list with python.
12-4-2017
Updated the insert. It was searching for a matching value.... Now it searches by matching the count to the index, and then changing the links. I also added some cheeky comments. Cause I was just feeling like a cheeky bastard today.
I also have a graphical for this one that will print off the list for you in command prompt. If the graphical fails to print, something is wrong in the nodes. If there are errors, I'm new at this, and I am sorry, feel free to tell me, I'd love to make improvements!
12-30 method dump() now prints contents instead of deleting the list.... opps.
1-4-17 method remove() now uses new method detach_node()
--- start code block ---
--- end code block ---
Pytest code block
--start code block--
--End code block--
Pytest is now included in this post, it is included at the bottom. I have added a new test to show that any valid python object can be stored in the Single Linked list. I may be cleaning this up today and adding a 'reverse' method.
Ok this time It is a single linked list with python.
I still couldn't manage to follow zeds vocabulary. I don't know why. I named stuff my way and was able to do it and at the end I was able to change it to how he had stuff and understood. Not sure why this was such an issue for me. I'll work on that some more, but this is a completed , tested sinlge linked list with python.
12-4-2017
Updated the insert. It was searching for a matching value.... Now it searches by matching the count to the index, and then changing the links. I also added some cheeky comments. Cause I was just feeling like a cheeky bastard today.
I also have a graphical for this one that will print off the list for you in command prompt. If the graphical fails to print, something is wrong in the nodes. If there are errors, I'm new at this, and I am sorry, feel free to tell me, I'd love to make improvements!
12-30 method dump() now prints contents instead of deleting the list.... opps.
1-4-17 method remove() now uses new method detach_node()
--- start code block ---
class SLLNode(object):
# Value is like the item in the list
def __init__(self, value, nxt):
self.value = value
# next is a reference to the next node in the list
self.next = nxt
def __repr__(self):
# this creates a string representation of the value and next
nval = self.next and self.next.value or None
# nval is the next node, so it needs the (node = next and it's value) or None
return f"[{self.value}:{repr(nval)}]"
class SLList(object):
# start off with None, list is empty
def __init__(self):
self.end = None
self.begin = None
def push(self, obj):
# add node to the list, value=obj
if self.end == None:
# define the node if list is empty
node = SLLNode(obj, None)
# set the begin and end to that node
self.end = node
self.begin = node
elif self.end == self.begin:
node = SLLNode(obj, None)
self.end.next = node #( --->)
self.begin.next = node #( --->)
self.end = node #( obj, None)
else:
node = SLLNode(obj, None)
self.end.next = node
self.end = node
def what(self):
# A way to print off what's going on in my node list
node = self.begin
if node == None:
print(" Empty list! ")
return None
else:
while node:
print(node)
# go to the next node until we reach the end of the list
# node which has a self.next of None
node = node.next
def graphical(self):
node = self.begin
if node:
print("\n\n")
else:
print(" Empty List! ")
length = self.count()
x = length
count = 0
while node:
# format
#[(index) DATA , link ]
# first node =
# [(0) DATA, 1 ]
# second node =
# [(1) DATA, 2 ]
# third node =
# [(2) DATA, (/)]
if node.next != None:
print(f"{node.value} = ")
print(f"[({count}) DATA , {(length - x) + 1}]")
else:
print(f"{node.value} = ")
print(f"[({count}) DATA , (/) ]")
count += 1
x -= 1
node = node.next
def pop(self):
# remove last item in list
# once the old node has no reference: a pointer carrying it's address, python will garbage collect it.
node = self.end
carrots = node.value
if node == None:
print( " Empty List ")
return(None)
elif self.begin == self.end:
self.begin = None
self.end = None
print(" List being Emptied! ")
return(carrots)
else:
node = self.begin
while node:
if node.next == self.end:
node.next = None
self.end = node
node = node.next
return carrots
def count(self):
# count the number of nodes
node = self.begin
count = 0
if node == None:
# if list is empty return 0
return count
else:
while node:
count += 1
# go through the nodes until there are no more links
node = node.next
return count
def get(self, index):
length = self.count()
count = 0
if length == 0:
print(" Empty List! ")
return(None)
elif index > (length):
# now I know what this message is all about.
# the index is greater then the length of the list
# remember index starts at 0
return(" index out of range! ")
else:
node = self.begin
while node:
if count == index:
return(node.value)
else:
node = node.next
count += 1
def insert(self, obj, index):
# put a new node into the list at given index
node = self.begin
length = self.count()
# make sure the index given is an integer.
try:
index = int(index)
except TypeError:
print(" index arguement must be an integer ")
# if the try fails and goes to except, this still runs
# but they'll have that little message in there error somewhere
# check for empty list and all the things they'd use push for.
# this was made from doing a MasterCopy exercise.
if node == None and index == 0:
print("You're list is Empty....")
print("You can use push to do this. wink wink. nudge nudge.")
self.push(obj)
elif node == self.end and index == 1:
print("You're list only has one item.....")
print("Seriously.... push.... wink wink, nudge nudge, hint hint.")
self.push(obj)
elif index == length:
print("You're adding to the end of the list.....")
print(" I'm just going to push this for you.... and have some tea.")
self.push(obj)
# check if they are asking for an index beyond range
elif index > length:
print(" You're list isn't that big! Compensate much? ")
return(" index out of range! ")
# now cover if they want to insert at 0:
elif index == 0:
link = node
newnode = SLLNode(obj, link)
self.begin = newnode
# cover all other index's:
# [ DATA, 1 -->] [ DATA, 2--->] (data, ---->) [DATA, 3--->]
else:
node = self.begin
count = 0
while node:
if count == index - 1:
link = node.next
newnode = SLLNode(obj, link)
node.next = newnode
count += 1
node = node.next
def remove(self, index):
# remove was fixed in remix of ex17 dictionary
count = 0
node = self.begin
while node:
if count == index:
print("remove match")
self.detach_node(node)
break
node = node.next
count += 1
def detach_node(self, node):
print("detach node")
if self.end == self.begin and (node == self.begin or node == self.end):
# list is length 1:
self.begin = None
self.end = None
print(f" self.begin = {self.begin} ")
elif self.begin.next == self.end and (node == self.begin or node == self.end):
## list length is 2#
if self.end == node:
self.end = self.begin
self.begin.next = None
else:
self.begin = self.end
self.begin.next = None
elif node == self.begin:
link = self.begin.next
self.begin = link
elif node == self.end:
self.pop()
else:
#print("else... sll detach_node")
start = self.begin
link = node.next
while start:
if start.next.next != None:
if start.next.next == link:
start.next = link
print(' match.... break')
break
else:
print('pass')
else:
print('none')
start = start.next
def dump(self):
## Print off contents
begin = self.begin
if begin == None:
print("[]")
else:
x = "["
while begin:
x = x + f"{begin.value}"
if begin.next != None:
x = x + ","
begin = begin.next
x = x + "]"
print(x)
def first(self):
# return the first item on the list
node = self.begin
if node == None:
return None
else:
if node != None:
return node.value
def last(self):
# return the last node added to the list
node = self.end
if node == None:
return None
else:
return node.value
def unshift(self):
# it's like a reverse pop() It'll remove the first item...
node = self.begin
if node == None:
print(" Empty list! ")
return(None)
else:
first = self.first()
self.remove(0)
return first
def shift(self, obj):
# remove the last item from the list? or add item to the list?
# looking up what shift does..... ok, internet is all over the
# place with this. DO what I want I guess. I'm just going to push.
self.push(obj)
Pytest code block
--start code block--
from SLList import*
def test_pop():
## remove the last item in the linked list
colors = SLList()
colors.push("Magenta")
colors.push("Alizarin")
colors.push("yellow")
assert colors.pop() == "yellow"
#assert colors.get(2) == None
assert colors.get(1) == "Alizarin"
assert colors.pop() == "Alizarin"
#assert colors.get(2) == None
assert colors.get(0) == "Magenta"
assert colors.pop() == "Magenta"
#assert colors.pop() == None
assert colors.get(0) == None
#print(zero)
def test_get():
colors = SLList()
assert colors.get(0) == None
colors.push("Yellow")
assert colors.get(0) == "Yellow"
colors.push("Olive")
assert colors.get(1) == "Olive"
colors.push("Jade")
assert colors.get(2) == "Jade"
assert colors.get(3) == None
assert colors.pop() == "Jade"
assert colors.pop() == "Olive"
def test_insert():
colors = SLList()
colors.push("blue")
assert colors.get(0) == "blue"
colors.insert("new color", 0)
assert colors.get(0) == "new color"
assert colors.get(1) == "blue"
colors.push("yellow")
assert colors.count() == 3
assert colors.get(2) == "yellow"
colors.insert("orange", 2)
assert colors.get(2) == "orange"
assert colors.get(3) == "yellow"
assert colors.count() == 4
def test_remove():
colors = SLList()
colors.push("blue") #0
colors.push("yellow") #1
colors.remove(0) #<--- fail.
colors.push("green") #2
colors.push("orange") #3
colors.push("Trillium") #4
colors.remove(1)
assert colors.count() == 3
assert colors.get(1) == "orange"
assert colors.remove(9) == None
colors.remove(0)
assert colors.count() == 2
assert colors.get(0) == "orange"
assert colors.get(1) == "Trillium"
assert colors.get(2) == None
colors.insert("umber", 1)
assert colors.get(1) == "umber"
colors.remove(0)
assert colors.count() == 2
def test_first():
# copy and pasted remove test. It does a ton of maniputaltion
# to the list, so it's like an extra test to combine the two.
colors = SLList()
colors.push("blue") #0
colors.push("yellow") #1
colors.remove(0) #<--- fail.
colors.push("green") #2
colors.push("orange") #3
colors.push("Trillium") #4
colors.remove(1)
assert colors.count() == 3
assert colors.get(1) == "orange"
assert colors.remove(9) == None
colors.remove(0)
assert colors.count() == 2
assert colors.get(0) == "orange"
assert colors.get(1) == "Trillium"
assert colors.get(2) == None
colors.insert("umber", 1)
assert colors.get(1) == "umber"
colors.remove(0)
assert colors.count() == 2
#assert colors.first == '[orange, None]' <-- returns address not string repr.
#assert colors.first() == "orange" # <-- fail, returns umber
# oh! I had a remove 0, so yes it should return umber
assert colors.first() == "umber"
def test_last():
# going to use the pop test to check this one
colors = SLList()
colors.push("Magenta")
colors.push("Alizarin")
colors.push("yellow")
assert colors.pop() == "yellow"
assert colors.last() == "Alizarin"
assert colors.get(1) == "Alizarin"
assert colors.pop() == "Alizarin"
assert colors.last() == "Magenta"
assert colors.get(0) == "Magenta"
assert colors.pop() == "Magenta"
assert colors.last() == None
assert colors.get(0) == None
def test_unshift():
# copy paste 'insert' test to try out this one:
colors = SLList()
colors.push("blue")
assert colors.get(0) == "blue"
colors.insert("new color", 0)
assert colors.get(0) == "new color"
assert colors.get(1) == "blue"
colors.push("yellow")
assert colors.count() == 3
assert colors.get(2) == "yellow"
colors.insert("orange", 2)
assert colors.get(2) == "orange"
assert colors.get(3) == "yellow"
assert colors.count() == 4
######### testing unshift on manipulated list #####
#!!!! Using colors.unshift() in the assert removes item too
assert colors.unshift() == "new color"
#!!!! the assert removed the 0 node
colors.unshift()
assert colors.count() == 2
assert colors.unshift() == "orange"
assert colors.count() == 1
assert colors.unshift() == "yellow"
assert colors.count() == 0
assert colors.unshift() == None
def test_non_string_types():
## store any valid object in this SLL
colors = SLList()
reds = ["Magenta", "lava", "fire", "passion"]
blues = ["Ocean", "Lake Michigan", "mood", "Summer skys"]
yellows = ["Daffodil", "school bus", "yield", "honey"]
colors.push(reds)
colors.push(blues)
colors.push(yellows)
assert colors.pop() == yellows
#assert colors.get(2) == None
assert colors.get(1) == blues
assert colors.pop() == blues
#assert colors.get(2) == None
assert colors.get(0) == reds
assert colors.pop() == reds
#assert colors.pop() == None
assert colors.get(0) == None
#print(zero)
dicts = SLList()
nums = {'by two': [2,4,6], 'by three': [3,6,9], 'by four': [4, 8, 12]}
tups = (1, 5, 20, 100)
hats = ['bolar', 'top', 'helmet', 'cap', 'feathered']
new_list = SLList()
dicts.push(nums)
dicts.push(tups)
dicts.push(hats)
dicts.push(new_list)
assert dicts.get(0) == nums
assert dicts.get(1) == tups
assert dicts.get(2) == hats
assert dicts.get(3) == new_list
assert isinstance(dicts.pop(), SLList)
Comments
Post a Comment