First some minor issues with naming, then a rewrite:
prev could be
previous, there is no need to skimp on characters.
node_i are completely different things, yet their names suggest they are both "moving pointers". That is only true for
node_j. May I suggest using
The use of
while..else is pretty cool, but confused me at first. Take that with a grain of salt, though, I'm not usually writing a lot of python.
Now for the meat of the problem:
This can be simplified by inverting the logic on your traversal. Consider the following code:
def sorted_insert(head, data):
if head is None:
if data < head.data:
new_head = Node(data)
new_head.next = head
# at this point we will always return head
current_node = head
# advance if next node is smaller than node to be inserted
while current_node.next is not None and current_node.next.data < data:
current_node = current_node.next
insert = Node(data)
insert.next = current_node.next
current_node.next = insert
This is an improvement over the code you presented because it separates special cases from traversal.
- We first handle the special case of an empty list (
head is None).
- Then we handle the case where we create a new head (
data < head.data)
With these special cases out of the way we now search for the insertion position, namely what you store in
prev. The way this works is by advancing
current_node only if the next node also has a smaller
data than the insertion.
This simplification allows us to eliminate a variable at the cost of a somewhat more difficult to understand loop condition. Overall this tradeoff is worth it, because we reduce the complexity of the loop body.
After we found the insertion position, the insertion itself becomes a matter of setting the properties in the correct order to avoid dropping the tail of the list.