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:
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
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
previous_node) is updated so that it points to
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
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.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!