FAQ: Linked Lists: Python - Linked List Review

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 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 stringify_list(self):
        string_list = ""
        current_node = self.get_head_node()

        while current_node:

            if current_node.get_value() != None:
                if len(string_list) == 0:
                    string_list += str(current_node.get_value())
                else:
                    string_list += "->" + str(current_node.get_value())
            current_node = current_node.get_next_node()

        return string_list

    def remove_node(self, value_to_remove):
        """
        Remove the first node in the linked list who match the value to remove parameter
        parameter: value_to_remove
        return None
        """
        current_node = self.get_head_node()

        if current_node.get_value() == value_to_remove:
            self.head_node = current_node.get_next_node()
        else:

            while current_node:
                next_node = current_node.get_next_node()

                if next_node.get_value() == value_to_remove:
                    current_node.set_next_node(next_node.get_next_node())
                    current_node = None
                else:
                    current_node = next_node

    def remove_all_node(self, value):
        """
        remove all the nodes of the linked list who shares the same value
        arg: value to remove
        return: None
        """
        current_node = self.get_head_node()

        while current_node:

            if current_node.get_value() == value:
                self.head_node = current_node.get_next_node()
                current_node = self.head_node

            else:
                if current_node.get_next_node().get_value() == value:
                    current_node.set_next_node(current_node.get_next_node().get_next_node())
                    current_node = current_node.get_next_node()
                    if current_node.get_next_node() == None:
                        break

                else:
                    current_node = current_node.get_next_node()
                    if current_node.get_next_node() == None:
                        break



lst_01 = LinkedList()

lst_01.insert_beginning("red")
lst_01.insert_beginning("green")
lst_01.insert_beginning("blue")
lst_01.insert_beginning("green")
lst_01.insert_beginning("red")
print("Linked list built:", lst_01.stringify_list())
print()
lst_01.remove_node("red")
print("Removed the first met node with red value from the linked list:",lst_01.stringify_list() )
print()
lst_01.remove_all_node("green")
print("Removed all nodes with green value from the linked list:",lst_01.stringify_list() )

I am wondering if it is possible to make the remove all node function in a recursive way.

Here is my attempt at the Linked List Review(I did the exercise and then I got stuck so I replaced my code with the solution and I added some of some other 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 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 stringify_list(self): string_list = "" current_node = self.get_head_node() while current_node: if current_node.get_value() != None: string_list += str(current_node.get_value()) + "\n" current_node = current_node.get_next_node() return string_list def remove_node(self, value_to_remove): current_node = self.get_head_node() if current_node.get_value() == value_to_remove: self.head_node = current_node.get_next_node() else: while current_node: next_node = current_node.get_next_node() if next_node.get_value() == value_to_remove: current_node.set_next_node(next_node.get_next_node()) current_node = None else: current_node = next_node from random import randint linked_list_1 = LinkedList(randint(0, 99)) for i in range(randint(0, 99)): linked_list_1.insert_beginning(randint(0, 99)) with open("random_numbers.txt", "a") as rand_file: rand_file.write(linked_list_1.stringify_list())

How can I improve it?

I think there’s a test case the remove method fails

If you do next_node.get_value( ) and next_node is None, then you will get an error. Because None has no attribute get_value( )

1 Like

Hi y’all,

Something weird is happening with my code. I tried doing the extra practice recommendation, where they suggested we write a method that removes all nodes with a given value from the list. I just modified the one they gave us, and it worked!

ALMOST

It removed all nodes with the given value except for one, and I can’t begin to fathom why it would do that.

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 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 stringify_list(self): string_list = "" current_node = self.get_head_node() while current_node: if current_node.get_value() != None: string_list += str(current_node.get_value()) + "\n" current_node = current_node.get_next_node() return string_list def remove_node(self, value_to_remove): current_node = self.get_head_node() if current_node.get_value() == value_to_remove: self.head_node = current_node.get_next_node() else: while current_node: next_node = current_node.get_next_node() if next_node.get_value() == value_to_remove: current_node.set_next_node(next_node.get_next_node()) current_node = current_node.get_next_node() else: current_node = next_node #It's a FAMILY tree smith_tree = LinkedList("Atticus") smith_tree.insert_beginning("Zachary") smith_tree.insert_beginning("Atticus") smith_tree.insert_beginning("Jeremy") smith_tree.insert_beginning("Atticus") smith_tree.insert_beginning("Atticus") smith_tree.insert_beginning("Patricia") print(smith_tree.stringify_list()) smith_tree.remove_node("Atticus") #Should print without Atticus print(smith_tree.stringify_list())

I’m sure you decided it already, just to train myself: you skip second “Atticus” and don’t orphane it like the first one because:
in your “if” block inside the “while” loop the last statement is “current_node = current_node.get_next_node()”. Means, now current node is a node with the value “Atticus” and it should be orphaned. But instead you skip it and check it’s NEXT node:
next_node = current_node.get_next_node()
if next_node = value_to_remove:
and so on…
The “collision” will occur only if nodes with the same data that is needed to be removed go in a row one by one. In this case you will remove only each second of them, not all. Right?

I agree! The metod remove_node from “Linked LIst Review” lesson returns an error: AttributeError: ‘NoneType’ object has no attribute ‘get_value’ , if we try to remove a node with non existent value or any node from an empty list. But maybe they decided not to make it too complicated and just gave an idea? And finaly make us to check and find the decision? Just a quesswork…

1 Like