Question

Given main.py and a Node class in Node.py, complete the LinkedList class (a linked list of nodes) in LinkedList.py by writing the insert_in_ascending_order() method that inserts a new Node into the LinkedList in ascending order.

Ex: If the input is:

8 3 6 2 5 9 4 1 7
the output is:

1 2 3 4 5 6 7 8 9

So, after finagling and wracking my brain I've gotten to this point with the code, but here's the issue;


Here's the code:



class LinkedList:
def __init__(self):
self.head = None
self.tail = None

def append(self, new_node):
if self.head == None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node

def prepend(self, new_node):
if self.head == None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node

def insert_after(self, current_node, new_node):
if self.head == None:
self.head = new_node
self.tail = new_node
elif current_node is self.tail:
self.tail.next = new_node
self.tail = new_node
else:
new_node.next = current_node.next
current_node.next = new_node

def insert_in_ascending_order(self, new_node):
if self.head == None or new_node.data < self.head.data:
new_node.next = self.head
self.head = new_node
else:
cur_node = self.head
while cur_node.next != None and new_node.data > cur_node.next.data:
cur_node = cur_node.next
cur_node.next = new_node


def remove_after(self, current_node):
# Special case, remove head
if (current_node == None) and (self.head != None):
succeeding_node = self.head.next
self.head = succeeding_node
if succeeding_node == None: # Remove last item
self.tail = None
elif current_node.next != None:
succeeding_node = current_node.next.next
current_node.next = succeeding_node
if succeeding_node == None: # Remove tail
self.tail = current_node

def print_list(self):
cur_node = self.head
while cur_node != None:
cur_node.print_node_data()
print(end=' ')
cur_node = cur_node.next


Here's the INPUT:
8 3 6 2 5 9 4 1 7

Here's my OUTPUT:
1 2 7


What can I do? Why does it only output 3 integers? I feel like the issue must be in my def remove_after section, however that was base code in the assignment (which I'm not necessarily supposed to change).

Answer 1

Based on the code you provided, the issue lies in the `insert_in_ascending_order()` method. The problem is with the last line inside the `else` block:

```python
cur_node.next = new_node
```

This line is incorrectly assigning the new node directly to the `cur_node.next`, which causes the previous nodes to be lost and results in a truncated list.

To fix this issue, you need to rearrange the statements in the `else` block as follows:

```python
new_node.next = cur_node.next
cur_node.next = new_node
```

This way, you correctly set the `next` references of the new node and the current node, preserving the integrity of the linked list.

Here's the corrected `insert_in_ascending_order()` method:

```python
def insert_in_ascending_order(self, new_node):
if self.head is None or new_node.data