Skip to content

Instantly share code, notes, and snippets.

@emil-raubach
Created Feb 11, 2019
Embed
What would you like to do?
Single Linked List class implementation from the book 'Learn More Python The Hard Way'
# manually build a list using the SingleLinkedListNode class
# Zed' code
class SingleLinkedListNode(object):
def __init__(self, value, nxt):
self.value = value
self.next = nxt
def __repr__(self):
nval = self.next and self.next.value or None
return f"[{self.value}:{repr(nval)}]"
# controller class for the SLLN
class SingleLinkedList(object):
def __init__(self):
self.begin = None
self.end = None
self.num_nodes = 0
# add a new node
def push(self, obj):
"""Appends a new value on the end of the list."""
if self.begin is None:
self.begin = SingleLinkedListNode(obj, None)
elif self.end is None:
self.end = SingleLinkedListNode(obj, None)
self.begin.next = self.end
else:
new_node = SingleLinkedListNode(obj,None)
self.end.next = new_node
self.end = new_node
self.num_nodes += 1
def pop(self):
"""Removes the last item and returns it."""
if self.begin is None: # empty list
return None
elif self.end is None and self.begin is not None: # only self.begin
rv = self.begin.value
self.begin = None
self.num_nodes -=1
return rv
else: # list contains 2 or more than elements
iterator = 0
previous_node = self.begin # start list traversal here
next_node = self.begin.next
while iterator < self.num_nodes: # or just while True?
if next_node is self.end:
rv = next_node.value
self.end = previous_node
previous_node.next = None
self.num_nodes -= 1
return rv
else:
if next_node is None:
print(">>> this never happens does it?")
rv = next_node.value
previous_node.next = None
if self.num_nodes == 1:
print(">>> pretty sure this will never run.")
self.end = None
else:
self.end = previous_node
self.num_nodes -= 1
return rv
else:
previous_node = next_node
next_node = next_node.next
iterator += 1
def shift(self, obj):
"""Another name for push."""
pass
def unshift(self):
"""Removes the first item and returns it."""
pass
def remove(self, obj):
"""Finds a matching item and removes it from the list."""
pass
def first(self):
"""Returns a *reference* to the first item, does not remove."""
pass
def last(self):
"""Returns a reference to the last item, does not remove."""
pass
def count(self):
"""Return the number of elements in the list"""
return self.num_nodes
def get(self, index):
"""Get the value at index."""
pass
def dump(self, mark):
"""Debugging function that dumps the contents of the list."""
pass
from sllist import *
# import pdb; pdb.set_trace()
def test_push():
colors = SingleLinkedList()
colors.push("Pthalo Blue")
assert colors.count() == 1
colors.push("Ultramarine Blue")
assert colors.count() == 2
def test_pop():
colors = SingleLinkedList()
colors.push("Magenta")
colors.push("Alizarin")
colors.push("Tomato Red")
assert colors.pop() == "Tomato Red"
assert colors.pop() == "Alizarin"
assert colors.pop() == "Magenta"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment