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.

A free service run by Zed A. Shaw for learncodethehardway.org.