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

class SingleLinkedList(object):

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 = 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")
    assert colors.pop() == "Alizarin"
    assert colors.pop() == "Magenta"
    assert colors.pop() == None

def test_unshift():
    colors = SingleLinkedList()
    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():
    colors = SingleLinkedList()
    colors.shift("Cadmium Orange")
    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…


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

class SingleLinkedList(object):

    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.
:slight_smile:

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 = SingleLinkedList()
    colors.push("Vermillion")
    assert colors.get(0) == "Vermillion"
    colors.push("Sap Green")
    assert colors.get(0) == "Vermillion"
    assert colors.get(1) == "Sap Green"
    colors.push("Cadmium Yellow Light")
    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 = SingleLinkedList()
        colors.push("Vermillion")
        assert colors.get(0) == "Vermillion"
        colors.push("Sap Green")
        assert colors.get(0) == "Vermillion"
        assert colors.get(1) == "Sap Green"
        colors.push("Cadmium Yellow Light")
        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
A free service run by Zed A. Shaw for learncodethehardway.org.