# LMPTHW - Exercise 13 Single Linked List

Hi there,
This is my first post here…

I am a bit confused - I am going through the SingleLinkedList exercise in Learn More Python the Hard Way. I have managed to complete some of the tests but I can’t seem to update the count method
I have successfully run the shift and unshift methods… but problem lies with the following line… in the test program…

``````assert colors.pop() == "Cadmium Orange"
assert colors.count() == 1
``````

My feeling is (and I know I could be wrong ) that the pop method does NOT remove the last element but does return the value…

This is the code that I have completed so far…

—BEGINNING OF CODE----------------------------

class Node(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)}]"
``````

``````def __init__(self):
self.begin = None
self.end = None

def push(self, obj):
node = Node(obj, None)

if self.begin is None:
self.begin = node
self.end = self.begin
else:
self.end.next = node
self.end = node
test_node = self.begin
while test_node:
test_node = test_node.next

def count(self):
"""Counts the number of elements in the list"""
node = self.begin
count = 0
while node:
count += 1
node = node.next
return count

def print_list(self):
cur_node = self.begin
while cur_node:
print(cur_node.value)
cur_node = cur_node.next

def pop(self):
if self.end == None: # this has to be adjusted -- if self.begin = None:
return None
elif self.end == self.begin:
node = self.begin
self.end = self.begin = None
return node.value
else:
node = self.begin
while node.next != self.end:
node = node.next
assert self.end != node
self.end = node
node = self.end
return node.next.value

def shift(self, data):
new_node = Node(data, None)

new_node.next = self.begin
self.end = self.begin
self.begin = new_node

def unshift(self):
"""Removes the first item and returns it"""
if self.begin == None:
return None

else:
self.end = self.begin
cur_node = self.end
print("This is cur_node UNSHIFT", cur_node)
self.begin = cur_node.next
print("THIS IS self.begin:", self.begin)
if cur_node:
return cur_node.value
cur_node = None
``````

-----End of code------------------------------------------------

And this is the error I get when I run pytest…

``````    colors.shift("Carbazole Violet")
assert colors.count() == 2

assert colors.pop() == "Cadmium Orange"
``````
``````  assert colors.count() == 1
``````

E assert 2 == 1
E + where 2 = <bound method SingleLinkedList.count of <posted_zed.SingleLinkedList object at 0x7ff19d2597b8>>()

Basically the count is running and is maintained at 2 …

Can some one help?

Thank you in advance…
Vinay

You see this:

``````E + where 2 = <bound method SingleLinkedList.count of <posted_zed.SingleLinkedList object at 0x7ff19d2597b8>>()
``````

I’m not sure where that’s coming from but that tells me you forgot to add () on the function, so you’re doing something like:

``````assert colors.count == 1
``````

Which would compare the number 1 to the count function, not the return of the count function.

But, what is the test code that is causing that output?

Hi Zed,

Thank you for quick response…

I have posted the test code and the controller that I have been working on below… (just in case I missed something out above).

``````----beginning of test code ---

from posted_zed import *

def test_push():
colors.push("Pthalo Blue")
assert colors.count() == 1
colors.push("Ultramarine Blue")
assert colors.count() == 2

def test_pop():
colors.push("Magenta")
colors.push("Alizarin")
assert colors.pop() == "Alizarin"
assert colors.pop() == "Magenta"
assert colors.pop() == None

def test_unshift():
colors.push("Viridian")
colors.push("Sap Green")
colors.push("Van Dyke")
assert colors.unshift() == "Viridian"
assert colors.unshift() == "Sap Green"
assert colors.unshift() == "Van Dyke"
assert colors.unshift() == None

def test_shift():
assert colors.count() == 1

colors.shift("Carbazole Violet")
assert colors.count() == 2

assert colors.pop() == "Cadmium Orange"
assert colors.count() == 1
assert colors.pop() == "Carbazole Violet"
assert colors.count() == 0

---------end of test code---------``````

And the following is what I have been working on…

``````-------beginning of Controller ----

class Node(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)}]"

class SingleLinkedList(object): # remember to change back

def __init__(self):
self.begin = None
self.end = None

def push(self, obj):
node = Node(obj, None)

if self.begin is None:
self.begin = node
self.end = self.begin
else:
self.end.next = node
self.end = node
test_node = self.begin
while test_node:
test_node = test_node.next

def count(self):
"""Counts the number of elements in the list"""
node = self.begin
count = 0
while node:
count += 1
node = node.next
return count

def print_list(self):
cur_node = self.begin
while cur_node:
print(cur_node.value)
cur_node = cur_node.next

def pop(self):
if self.end == None: # this has to be adjusted -- if self.begin = None:
return None
elif self.end == self.begin:
node = self.begin
self.end = self.begin = None
return node.value
else:
node = self.begin
while node.next != self.end:
node = node.next
assert self.end != node
self.end = node
node = self.end
return node.next.value

def shift(self, data):
new_node = Node(data, None)

new_node.next = self.begin
self.end = self.begin
self.begin = new_node

def unshift(self):
"""Removes the first item and returns it"""
if self.begin == None:
return None

else:
self.end = self.begin
cur_node = self.end
print("This is cur_node UNSHIFT", cur_node)
self.begin = cur_node.next
print("THIS IS self.begin:", self.begin)
if cur_node:
return cur_node.value
cur_node = None

---------end of Controller----``````

and this is the error I receive…

``````---------error message -------

assert colors.pop() == "Cadmium Orange"
>       assert colors.count() == 1
E       assert 2 == 1
E        +  where 2 = <bound method SingleLinkedList.count of <posted_zed.SingleLinkedList object at 0x7f63a9b28fd0>>()

------end of error ---``````

Thank you again for your help…
Vinay

Hi Zed,

I was thinking the error message is there because you would want us to create an updated count function using possibly recursion(?).

The count method only runs once in every test and is a fixed value rather than being updated if popping or shifting the nodes on the linked list…

Kindest regards,
Vinay

First, when you post code do this:

``````[code]
# your code here
[/code]
``````

I fixed it for you so it’s easier to work with. Now, this is a failure in your test_shift(), but it happens after you shift on some data, then attempt to pop off the data and check the count. There’s three possiblities here:

1. Your shift code is wrong.
2. Your pop code is wrong.
3. Your count code is wrong.

How these can be wrong is almost always because you forgot to update self.end, self.end, or node.next. Now, what you can do is one of these three strategies:

1. Add a print statement for every operation that dumps the links and lists so you can see if they are changing. This is what I tell people to do, and if you are not printing out things then you aren’t really even debugging anything correctly. Either you print everything, use pdb (python debugger), or you’re blind and just guessing and actually doing it totally wrong.
2. Test each method individually with their own extensive tests, but without using any of the others. This would mean, test that shift works without using pop or count. Then test pop without using shift or count. Then test count without using shift or pop. That would involve manually confirming that the self.end, self.begin, and node.next links are correct after each operation.
3. Erase each function, one at a time, and rewrite it to see if you can make it work a different way. For example, delete shift’s contents. Make the test fail. Then make shift pass the first part. Then make it test the next part, and so on until the test passes.

I suggest you do each of these in order to see if you can figure it out.

Hi Zed,

Thank you…

I have been using print to debug… I expect I need to try harder…

I have noted the protocol to post code and appreciate the time you have taken to reply,

Kindest regards,
Vinay

Show me some of your print debugging so I can see how you’re dong it. How about, post just the shift() function with your print debugging in it, and then I’ll see what I would do instead.

Hi Zed,

Thank you. Just to update you, I did not know what Single Linked List were about 2 weeks ago and I have been on this every day since then, I have also been watching Lucid Programming’s work on this on youtube initially…

So now I have an idea of how it is working … any way here is the code…
You mentioned “shift” to be another name for push and after the reading the test code I ascertained that shift is adding a node to the front of the list and shunting the original to the right as illustrated here…

A
B -> A
C -> B -> A

Anyway here is the code…

[code]

``````def shift(self, data):
new_node = Node(data, None)
print("NODE in SHIFT", new_node)

new_node.next = self.begin
self.end = self.begin
print("THIS IS SELF.END", self.end)
print("THIS IS NEW_NODE.NEXT", new_node.next)
self.begin = new_node
#self.end = self.begin
print("SELF.BEGIN AFTERWARDS", self.begin)
#print("SELF.END AFTERWARDS", self.end)
``````

[code]

I am not going to allow this to beat me…
Vinay

That’s pretty good. Try this:

``````print(">>> shift", data)
...
print("shift: after next begin", self.end, self.begin, new_node.next, data)
...
print("<<< shift", self.end, self.begin, new_node.next, data)
``````

This difference is the following:

1. I use >>> and <<< to indicate when I entered and exited the function.
2. I first print the arguments to the function.
3. I don’t just print what I changed on one line, I print all of the data in play at each point I want to analyze.
4. When I exit, I do <<< and again print all the data.

Also, you have to work out what each operation does, so try doing this on paper with boxes and lines. I think your thinking here is just muddled because you’re trying to think in code. Draw it out, then write out the steps in English (or whatever) comments, then write the python code under those to make them work.

Thank you. I have just been going through code now and yes… my thinking is a bit muddled. But I can solve this.

Yep, I’d say, delete this code, then draw out on paper how the links change with some simple boxes and lines. Then, turn that into an series of steps in plain language. Take those steps and create code comments. Once you’ve got that it’s a fill-in-the-blank problem.

Hi Zed,

Can you please kick start me for the dump function in ex13?

For the following code

``````
def dump(self, mark):
"""Debugging function that dumps the contents of the list."""
``````

Thank you.
Vinay

Hi Zed,

I have had the “light bulb” moment in relation to this exercise. please see the following code. I still have to complete the remove function… but here is the code…

``````

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)}]"

def __init__(self):
self.begin = None
self.end = None

def push(self, obj):
"""Appends a new value on the head of the list."""
node = SingleLinkedListNode(obj, None)
if self.begin == None:
# Nothing yet
self.begin = node
self.end = self.begin
else:
self.end.next = node # this points to the next node in the chain
self.end = node # this assigns the node the end of the linked list
assert self.end.next == None

def shift(self, obj):
"""Another name for push""" # need to check if this the correct one

node  = SingleLinkedListNode(obj, None)

if self.begin:
node.next = self.begin
self.begin = node
else:
self.begin = node
self.end = self.begin

def remove(self, key):

cur_node = self.begin
print("THIS IS CUR_NODE which should be first node", cur_node)
print("THIS SHOULD BE the value attached", cur_node.value)
print("THIS SHOULD BE THE KEY", key)

if cur_node and cur_node.value == key:
self.begin = cur_node.next
print("THIS SHOULD BE cur_node.next HARD:YARD", cur_node.next)
cur_node = None
print("cur_node should equal to self.head", cur_node, self.begin)
return

prev = None
while cur_node and cur_node.value != key:
prev = cur_node
cur_node = cur_node.next

if cur_node is None:
return

prev.next = cur_node.next
cur_node = None

prev = None
#last_node = self.end
first_node = self.begin
if self.end and self.end.value == key:
print("TRUE")
print("THIS IS HEAD NODE", first_node)
print("THIS IS SELF END", self.end)
print("THIS IS first_node.next", first_node.next)
while first_node:
prev = first_node
first_node = first_node.next
print("THIS WORKS")
print("IS THIS THE LAST NODE", first_node)
print("THIS IS PREV", prev)
self.end = prev

def count(self):
count = 0
if self.begin == None:
count = 0
print(count)
return count
else:
last_node = self.end
node = self.begin
count = 1
while node != last_node:
count += 1
node = node.next
print(count)
return count

def print_list(self):
cur_node = self.begin
while cur_node:
print(cur_node.value)
cur_node = cur_node.next
``````

As per my previous message, if you can just kick start the dump function ie give me some pointers …

Thank you in advance for your help…

Vinay

I think your `print_list` is actually a good starting point. You just have to go through them all, but print it out so that you can debug it.

Also, be sure to end your code blocks correctly:

``````[code]
#
[/code] <----- See the / there?
``````

Another alternative is three backticks:

`````````
# code here
`````````

Either way, you’re very close. Just look at your print_list.

wow thank you Zed…

I have noted about the [/code] protocol. Hi Zed,

I do have a quick question in relation to the pop method in the SingleLlinkedList class…

In the solution that you have given… you don’t seem to cleanly close the self.end = node as the self.end.next still points to value…

if I pop off a node then the last node should point to null…

so if I do self.end.next = None

I will not be able to successfully return the node.next.value… as this return None…

I will illustrate this with an example in the next post… I work full time and practice this in my free time…

And I appreciate any feedback in the meantime…

``````
node = self.begin
while node.next != self.end:
node = node.next
assert self.end != node
self.end = node
``````

The following is the solution that give for the pop method…

``````
def pop(self):
"""Removes the last item and returns it."""
if self.end == None:
return None
elif self.end == self.begin:
node = self.begin
self.end = self.begin = None
return node.value
else:
node = self.begin
while node.next != self.end:
node = node.next
assert self.end != node
self.end = node
return node.next.value
``````

Hmm, that may be true. Try this:

So you’ve got what you think is a bug, and you have an automated test for this. Try to create a test that exploits or causes the bug, then tests that it’s fixed, then fix it and see if that works. Drop your test here so we can see what you did.

So basically I was struggling with the Get Method and then realized that there is a possibility that the Pop Method is not complete.

I looked at the Push method and this completes with the self.end.next as None. The following is the snippet of the Push method;

``````        else:
node = self.begin
while node.next != self.end:
node = node.next
assert self.end != node
a = node.next.value
self.end = node
self.end.next = None``````

But the Pop method does not complete self.end.next as None as this still points to a next node which should have been popped off.

The following is the code here https://github.com/zedshaw/learn-more-python-the-hard-way-solutions/blob/master/ex13_sllist/sllist.py

``````    def pop(self):
"""Removes the last item and returns it."""
if self.end == None:
return None
elif self.end == self.begin:
node = self.begin
self.end = self.begin = None
return node.value
else:
node = self.begin
while node.next != self.end:
node = node.next
assert self.end != node
self.end = node
return node.next.value
``````

And this is the test code I used to illustrate the error and fix;

``````def test_get():
colors.push("Vermillion")
assert colors.get(0) == "Vermillion"
colors.push("Sap Green")
assert colors.get(0) == "Vermillion"
assert colors.get(1) == "Sap Green"
assert colors.get(0) == "Vermillion"
assert colors.get(1) == "Sap Green"
assert colors.get(2) == "Cadmium Yellow Light"
assert colors.pop() == "Cadmium Yellow Light"
assert colors.get(0) == "Vermillion"
assert colors.get(1) == "Sap Green"
assert colors.get(2) == None
colors.pop()
assert colors.get(0) == "Vermillion"
colors.pop()
assert colors.get(0) == None``````

The following is the code that I used for the Get Method. I feel that it is correct as it tracks the node value in an index like format.

``````    def get(self, index):
current = self.begin
count = 0

while current:
if count == index:
return current.value
count += 1
current = current.next

return None``````

When I run this code with the Pop Method that is given as a solution, I get the following error which highlights the last node, which should have been popped off as an error as illustrated below.

``````
def test_get():
colors.push("Vermillion")
assert colors.get(0) == "Vermillion"
colors.push("Sap Green")
assert colors.get(0) == "Vermillion"
assert colors.get(1) == "Sap Green"
assert colors.get(0) == "Vermillion"
assert colors.get(1) == "Sap Green"
assert colors.get(2) == "Cadmium Yellow Light"
assert colors.pop() == "Cadmium Yellow Light"
assert colors.get(0) == "Vermillion"
assert colors.get(1) == "Sap Green"
>       assert colors.get(2) == None
E       AssertionError: assert 'Cadmium Yellow Light' == None
E        +  where 'Cadmium Yellow Light' = <bound method SingleLinkedList.get of <sixth.SingleLinkedList object at 0x7f0f41ba7d30>>(2)
E        +    where <bound method SingleLinkedList.get of <sixth.SingleLinkedList object at 0x7f0f41ba7d30>> = <sixth.SingleLinkedList object at 0x7f0f41ba7d30>.get
``````

Now if I change the Pop Method as follows I don’t get an error and it passes the test.

``````    def pop(self):
"""Removes the last item and returns it."""
if self.end == None:
return None
elif self.end == self.begin:
node = self.begin
self.end = self.begin = None
return node.value
else:
node = self.begin
while node.next != self.end:
node = node.next
assert self.end != node
print("THIS IS NODE.NEXT.VALUE, 1st", node.next.value)
a = node.next.value
self.end = node
self.end.next = None
return a``````

So basically the solution that I propose to solve this bug is to pass the value to be popped off to a variable “a” like this:

``a = node.next.value``

and then pass None to self.end.next,

``self.end.next = None``

after which return the variable a

``return a``

…which has stored the value to pass the test. This assures that the self.end.next refers to Null. This then would correspond with the assertion that the popped off node in the Get Method is None.

Nice, I like it. Good find.

ok … thank you. As mentioned I have learn’t a lot using your work over the past years. I only do this part time, as in learning. I would like to take this to a different level ie do it professionally.

Have a good one Zed.

1 Like