Stuck on Exercise 13 in LMPTHW (Single Linked Lists)

Python
#1

Hello al,

I have been working on implementing the .pop() function for the SingleLinkedList() class in Exercise 13 of Learn More Python The Hard Way, and have gotten to a point where I can’t seem to figure out my flawed logic.

First things first, here is a link to my code:

I was able to get the test to pass at one point, but then I add a third element to the list and it ended up breaking my .pop() function. The beginning of the logical tests are meant to cover the simple cases where there is either zero, or one element in the list. The rest of the logic applies only if there are two or more elements in the list.

My overall implementation is based on the idea of using two temporary variable to traverse the list: previous_node and next_node. At the start, I set the previous_node variable to self.begin, and the next_node variables to self.begin.next. Then, the idea is basically to swap these two variables down the list until the next_node.next is None indicating the end of the list (I used a while-loop using the node counter variable for this but not sure that my logic is sound here either). The value of the last element is then stored in a temp variable so the swapping / clean-up can occur before returning the value. Then, the node above next_node (previous_node) is updated so that it points to None and self.end is now set to it. Then, the next time .pop() is called, it goes through the whole thing again as this is a sequential access structure.

It seems to pop-off the first two elements, but throws an exception on the final one. I believe it is the logic intended to cover a list of size two. It is getting hung-up on the if-else statement on line 65 - AttributeError: 'NoneType' object has no attribute 'value'. I get that the next_node is None and then I am trying to access a member variable of an object that doesn’t have one. I have previously used next_node.next in the if statement, but that didn’t work either (same exception at a different line). I think where I am failing is in correctly updating the nodes after popping one off the end. I have been using pdb to try to debug the code, which has been very insightful, but I can’t seem to fix the error in my logic. Stepping through the code, I get to a point where self.begin and self.end are the same object so I think that is a clue to where things are going wrong but I’m just missing how to fix it.

It very well could be the whole construct is garbage, but it seems like it’s close to working correctly… I have thought of other implementations, such as chaining a bunch of the .next attributes in a row to traverse the list (e.g., self.begin.next.next.next.next…) but I’m not sure that is a great way to do this either. Also, I have been trying not to use built-in Python constructs like lists and for loops as it seems like cheating. (We are trying to create the basic data structures ourselves after all).

I have since held off on watching the video or googling the subject as I really want to figure it out for myself. But if that is a good way to get unstuck, I’m certainly open to it. If anyone has the inkling to glance through the code and provide any insight I would greatly appreciate it! Please let me know if I can more adequately describe the problem, what I’ve tried, etc. I’ve been staring at it so long I’ve pretty well lost al objectivity, so sorry if this is a bit of a ramble!

Thanks!
Emil

#2

Alright so here’s some clues:

  1. It looks like you’re properly handling the 0, 1, many conditions so that works. That’s your outer if-statement.
  2. It looks like you’re trying to just hack the python until it works rather than doing some research and following the recommended pattern (see below).
  3. Your looping construct isn’t going to work. The real pattern is:
cur = self.start
while cur:
     # do stuff
     cur = cur.next
  1. Read the history of the algorithm a bit https://en.wikipedia.org/wiki/Algorithm It was originally a list of steps for doing calulcations written on paper. So, you just have to write down the steps to pop off the end on a piece of paper, and then translate using our method below.
  2. So, you are at cur, and before you go cur.next you can go cur.next.next right? So if you do that and cur.next.next == None then what’s that mean?

The Method

Do this to write your code and you’ll be happier.

  1. Write the steps out on paper or a text file in English and draw diagrams to make sure it’s going to work.
  2. Turn the English description of steps into English Comments in your python file.
  3. Under the English comments, write out pseudo code–meaning fake not real but sort of Python–to effectively create a sketch translating the English into “codish”. These are also comments.
  4. Under the Pseudo code write the python for each step and run it frequently as you write it to make sure it’s working.

Here’s an example using the above code if I were just going to list every node. First the English

# Get the start node
# While that node exists
# Print the value
# Get the next node

Now the pseudo-code:

# Get the start node
# cur = start node
# While that node exists
# while cur:
# Print the value
# print cur.value
# Get the next node
# cur = next node

Then clean it up:

# cur = start node
# while cur:
# print cur.value
# cur = next node

Then put the Python in, and remember, you’re running this on almost every line of Python you put in:

# cur = start node
cur = self.start
# while cur:
while cur:
    # print cur.value
    print cur.value
    # cur = next node
    cur = cur.next

Once that works, clean it up:

cur = self.start
while cur:
    print cur.value
    cur = cur.next

Then, typically after a session like this you’ll see a better way to do it and you can work this code to refine it more, or even erase it and do a new version using the same process.

So, erase that code you have, maybe the whole function, and do this to rewrite it.

2 Likes
#3

Yup, you are right - I was pretty much trying to hack my way through! I actually did try to write it out and draw diagrams as you suggest, but I obviously need to improve at that process. (Don’t want you to think I ignored the early part of the book!). I will check out the Wikipedia page as well, that looks like a great resource for understanding the basis for Algorithms.

Thank you so much for taking the time to write such a thorough and detailed response - it is extremely helpful and much appreciated!!! I did end up getting it to work, see below:

def pop(self):
        """Removes the last item and returns it."""
        
        cur = self.begin

        while cur:
            if cur.next is None:
                rv = self.begin.value
                self.begin = None
                self.num_nodes -= 1
                return rv
            elif cur.next.next is None:
                rv = cur.next.value
                cur.next = None
                self.end = cur
                self.num_nodes -= 1
                return rv
            else:
                cur = cur.next

I’m sure it’s not a perfect solution, but it is much better than my nonsensical code I had previously. I will keep working on this exercise with the pseudocode method, and keep refining my processes.

Thanks again!
Emil

#4

Alright way better! Ok, now I like this solution but it’s what I call “implicit logic”, where I have to trace through and prove that it handles the three conditions in the while-loop correctly. Remember, we want to explicitly handle:

0 elements
1 element
many elements

Your code does that but it’s not explicit so I have to trace through it and prove in my mind that it does. If you pull the check for 0 and 1 elements out of the while loop, then I don’t have to prove those two conditions. All I have to do is confirm that the while loop handles the many elements.

Try that change out and see what you come up with.

#5

Oh, that makes a lot of sense. I had originally had it where the 0 and 1 cases were outside the while-loop but looking at the way you stated the loop, I saw the implicit logic and thought “Hey that actually covers it without the additional if-else loop!” and that it may be the more elegant way to do it. But, I can definitely see that having the code be easy to read, with explicit logic, is going to be better for understanding what is going on - especially if someone else has to read it at some point!

It was actually easy to pull out those elements once I got the overall logic sorted out. The latest iteration:

def pop(self):
        """Removes the last item and returns it."""
        
        cur = self.begin

        if cur is None:
            return None        
        elif cur.next is None:
            rv = self.begin.value
            self.begin = None
            self.num_nodes -= 1
            return rv
        else:
            while cur:            
                if cur.next.next is None:
                    rv = cur.next.value
                    cur.next = None
                    self.end = cur
                    self.num_nodes -= 1
                    return rv
                else:
                    cur = cur.next

In the elif block, I thought about putting a more explicit statement, such as elif cur.next is None and cur is not None: but I’m not sure that is necessary. I’m also assuming that later on, when we are optimizing the algorithm, additional - potentially unnecessary - comparisons are the things that could slow down computation time? But if it doesn’t affect it, then maybe the additional overhead is worth it.

On to the next function!

Edit: I just noticed I forgot the else to the while block! Still worked, but not explicit. Fixed.

#6

Just to close the loop - here’s my final solution to this exercise for anyone interested:

It took a super long time but I learned a lot and it was a fun and challenging exercise!

#7

Nice, looking good from what I see. Keep going.

1 Like