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())
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.
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…
def remove_all_node(self, value_to_remove):
# Skipping the head node for the first time
current_node = self.head_node
next_node = current_node.get_next_node()
while next_node:
if next_node.get_value() == value_to_remove:
current_node.set_next_node(next_node.get_next_node())
next_node = current_node.get_next_node()
else:
current_node = next_node
next_node = current_node.get_next_node()
# At the end check for the head node
head_node = self.head_node
if head_node.get_value() == value_to_remove:
self.head_node = head_node.get_next_node()
I am very confused right now about the stringify_list method in the lesson. I created a small linked list and then tried to print the string which comes from the stringify_list method. However, the output I get is very unexpected, I get the following
<__main__.Node object at 0x7f9fc6002048>
<__main__.Node object at 0x7f9fc6002080>
<__main__.Node object at 0x7f9fc60020b8>
<__main__.Node object at 0x7f9fc60020f0>
I figured it out, I had to overwrite the string method for the Node class to deal with the case when the value of the Node is a string rather than a number (which is something that doesn’t come up in the lesson). I’m still not sure why one has to do this, but it works.
A lot of answers here are duplicating code for the review challenge of removing all nodes instead of just the first, when they can just call their already written and working code.
The last node throws an attribute error because in the method removing one node it checks the value of next_node, but the next node in None at this point and thus does not have an appropriate “get_value” attribute.
def remove_all_nodes(self, value_to_remove):
while True:
try:
self.remove_node(value_to_remove)
except AttributeError:
break
In the remove_node method, I’m struggling to understand what the “while current_node:” loop is checking for. Current_node is set to self.get_head_node() initially. Does that mean that it is checking for the return value of get_head_node()? If so, then why does setting current_node = next_node in the “else:” statement not exit the while loop? In the “if” statement, if the value is found then at the end current_node is set to None, which makes more sense to me as to why it would exit the “while” loop. Any help?
Here’s code that I wrote for inserting a node at the end of a linked list
def insert_end(self, new_value):
new_node = Node(new_value)
current_node = self.head_node
#this checks if there is only one node currently in the list
if current_node.get_next_node() == None:
current_node.set_next_node(new_node)
else:
#we traverse the linked list until we get to the last node
while(current_node.get_next_node() != None):
current_node = current_node.get_next_node()
#when we get to the last node, we link it to the new node
current_node.set_next_node(new_node)
The “while current_node” loop is checking whether "current_node is equal to None.
You can see that reflected in the fact that in the if statement, when the condition is satisfied, the loop ends with the statement current_node = None
This is code I wrote for inserting a new node anywhere in the linked list
def insert_node(self, node_position, new_value):
#this adds the new node at the beginning of the linked list
if node_position == 1:
self.insert_beginning(new_value)
else:
node_count = self.count_nodes()
current_node = self.head_node
previous_node = self.head_node
# this adds a new node at the end of the linked list
if node_position - node_count == 1:
new_node = Node(new_value)
#traverse the list till you find the last node
while(current_node.get_next_node() != None):
current_node = current_node.get_next_node()
current_node.set_next_node(new_node)
return
#if node you want to insert is out of bounds
elif node_position - node_count > 1:
print('The node you selected is out of bounds.')
return
else:
target_node = 0
while(target_node != node_position):
previous_node = current_node
current_node = current_node.get_next_node()
target_node += 1
new_node = Node(new_value)
new_node.set_next_node(current_node)
previous_node.set_next_node(new_node)