Good morning, I want to implement a method in the SortedLinkedList class that accepts a value to insert in the list as a parameter. The value will be inserted in order, so that it is inserted after all that are less than and just before those that are greater than or equal to. The list will remain ordered from smallest to largest at all times.
This first module generates the list, so in the method that I want to implement I don't have to create any list
import random
from sortedlinkedlist import SortedLinkedList
if __name__ == "__main__":
my_slist = SortedLinkedList()
for i in range(10):
my_slist.insert(random.randint(10, 100))
for item in my_slist:
print(item)
In this second module there is a series of methods that deal with linked lists and should not be modified because I have verified that they work
class SortedLinkedList:
class Node:
def __init__(self, value, next_node = None):
self.value = value
self.next_node = next_node
def __init__(self):
self.__first = None
self.__len = 0
def __len__(self):
return self.__len
def __iter__(self):
self.__current = self.__first
return self
def __next__(self):
if self.__current != None:
result = self.__current.value
self.__current = self.__current.next_node
return result
else:
raise StopIteration
Next is the method I want to implement. This is what I have tried
def insert(self, value):
if value == 0:
self.insert_as_first(value)
elif value == len(self):
self.append(value)
elif value < 0 or value > len(self):
raise IndexError
else:
current = self.__first
current_pos = 1
while current_pos < value:
current = current.next_node
current_pos += 1
current.next_node = self.Node(value, current.next_node)
self.__len += 1
When you are going to insert a new node in the list we can have one of these situations:
♦ The list is empty
Therefore it
self.__first
isNone
and itself.__len
is0
. In this case we simply have to create a new instance ofNode
and assign it toself.__first
.♦ The value to enter is less than the value of the first node in the list
In this case our new node must become the first:
For this we do:
Nodo
and assign to its attributenext_node
the node associated withself.__first
so far, the one that was the first node in the list.self.__first
our new node so that it becomes the first.♦ None of the above occurs
In this case the node must be inserted between other nodes or at the end of the list. Therefore we must iterate over it until we find the position in which our new node would be ordered:
If we find a node with a value less than the one we want to add but whose next node has a value greater than or equal to, we must insert the new node between them.
This would be done in two steps:
next_node
of our new node the node following the one we are in this iteration (the first node in the list whose value is greater than or equal to the value of our new node)next_node
of the current node of the iteration, the last one whose value is less, to our new node, the instance of the newly created node.If we arrive at a node in which the node that follows is
None
(last node in the list) we only have to assign the attributenext_node
of this node our new node, which will become the last node.Your method could look something like this:
Another possibility is to use a
for in - else
withrange
leveraging that our list implementslen
:By avoiding two comparisons the insert is somewhat more efficient.
Do not use the equality/inequality operators (
==
/!=
) to find out if a variable is associated withNone
, None is a singleton, the correct way is to use the identity operator (is
/is not
):