I'm playing around with LinkedLists, came into an issue, help please!

Get Help Python
#1

Hi guys. Below is my code:

class Node:
    def __init__(self,value,next_node = None):
        self.value = value
        self.next_node = next_node
    
    def get_value(self):
        return self.value
    
    def get_next_node(self):
        return self.next_node
    
    def set_next_node(self,next_node):
        self.next_node = next_node

class LinkedList:
    def __init__(self,value=None):
        self.head_node = Node(value)

    def __repr__(self):
        current_node = self.head_node
        stringify = '\n'
        while current_node:
            stringify += str(current_node.get_value())+(', ' if current_node.get_next_node()!= None else '')
            current_node = current_node.get_next_node()
        return stringify+'\nLength: '+str(len(self))+'\n'

    def __len__(self):
        counter = 0
        current_node = self.head_node
        while current_node:
            counter+=1
            current_node = current_node.get_next_node()
        return counter
    
    def get_head_node(self):
        return self.head_node
    
    def insert_beginning(self,new_value):
        new_node = Node(new_value)
        new_node.set_next_node(self.head_node)
        self.head_node = new_node
    
    def insert_at_end(self,new_value):
        #I want to get the node at the end of the list
        current_node = self.head_node
        new_node = Node(new_value)
        while current_node.get_next_node() != None:
            current_node = current_node.get_next_node()
        current_node.set_next_node(new_node)
    
    def insert_in_middle(self,new_value):
        #Only work if Length of LinkedList is at least 2
        if len(self)<2:
            print ("LinkedList not long enough for this method. Please ensure at least 2 nodes are present")
        else:
            #Divide Length by 2, get int, go to that space and insert
            middle = int(len(self)/2)-1
            current_node = self.head_node
            for traverse in range(middle):
                current_node = current_node.get_next_node()
            new_node = Node(new_value)
            new_node.set_next_node(current_node.get_next_node())
            current_node.set_next_node(new_node)



    def remove_node(self,value_to_remove):
        current_node = self.head_node
        next_node = current_node.get_next_node()
        if current_node.get_value() == value_to_remove:
            #If it's the head node, all you need to to is to replace the head node with the next node
            self.head_node = next_node
        else:
            while current_node:
                next_node = current_node.get_next_node()
                next_next_node = next_node.get_next_node()
                if next_node.get_value() == value_to_remove:
                    #If it's not the head node, then the NEXT node's pointer needs to become the CURRENT node's pointer
                    #The NEXT node falls away automatically because of Garbage Collection
                    current_node.set_next_node(next_next_node)
                    current_node = None
    
    def remove_nodes(self,value_to_remove):
        #I would think this just iterates the remove_node method. But first we find how many instances of the value to remove there is
        times_to_remove = 0
        current_node = self.head_node
        for i in range(len(self)-1):
            times_to_remove+=1 if current_node.get_value() == value_to_remove else 0
            current_node = current_node.get_next_node()
        #Now Loop the remove_node method:
        for p in range(times_to_remove):
            self.remove_node(value_to_remove)
        #print(times_to_remove)

So I tried to create the remove_nodes function, but in the last loop, my terminal just doesn’t process it. Not sure where I’m going wrong?

#2

Absolutely no clue what codecademy tells you here but I would say that remove_nodes shouldn’t rely on length or remove-a-single-node, instead it should be walking through the list, taking it apart while doing so and putting it back together behind itself, without including the values to be eliminated.

When you say you’re not sure where you’re going wrong, is that because you don’t know what should happen or you don’t know if it does what you want it to do? If the former, then you have some head scratching and deciding to do, if the latter, then maybe some prints to write out what is being done so that you can compare this output to what you intend to happen?

3 Likes
#3

Thanks for the reply
So my logic was reuse the remove_node code instead of writing a new sequence. I expect the remove_node method to execute 10 times or so and remove every instance of the value to remove by definition. But it doesn’t run. It gets stuck, like crashes and I have to kill the terminal.

I will try make a loop so it goes through and changes it once. I just thought this method would also work

3 Likes
#4

It would work if done right, but imagine having a list containing 100000 ‘b’ followed by 100000 ‘a’.
Now remove all the a’s. Removing an a requires looping through 100000 b’s. It needs to be done 100000 times. A total of 10000000000 iterations for what should be walking through the list only once (100000 iterations)

Regardless, printing out what’s being done may tell you where it goes wrong. Can’t look at it myself because I don’t have code that reproduces the failure.

stuff = LinkedList()
stuff.insert_beginning(5)
stuff.insert_beginning(4)
stuff.insert_beginning(4)
stuff.insert_beginning(4)
stuff.insert_beginning(4)
stuff.insert_beginning(5)
print(stuff)
stuff.remove_nodes(4)
print(stuff)

5, 4, 4, 4, 4, 5, None
Length: 7


5, 5, None
Length: 3

The length is arguably wrong (depends on perspective), but the removal is right for this case. So what case did it fail? To debug it you’d have to start with that - to identify what the failure at all is.

2 Likes
#5

Sean, look here:

    def remove_node(self,value_to_remove):
        current_node = self.head_node
        next_node = current_node.get_next_node()
        if current_node.get_value() == value_to_remove:
            #If it's the head node, all you need to to is to replace the head node with the next node
            self.head_node = next_node
        else:
            while current_node:
                next_node = current_node.get_next_node()
                next_next_node = next_node.get_next_node()
                if next_node.get_value() == value_to_remove:
                    #If it's not the head node, then the NEXT node's pointer needs to become the CURRENT node's pointer
                    #The NEXT node falls away automatically because of Garbage Collection
                    current_node.set_next_node(next_next_node)
                    current_node = None

Now, focussing on that final if, what happens if next_node.get_value() is not value_to_remove?

2 Likes