Question

Define an iterative function named append_ordered; it is passed two arguments: a linked list (ll) whose values are ordered from smallest to biggest (they can be ints, strs, anything that can be compared), and another value (v). It returns a reference to the front of a linked list that includes all the values of the original linked list, and v, all in order. We call it like x = append_ordered(x,v). You may create exactly one new LN, for storing the value of v. For example, if we defined x = list_to_ll([1, 3, 8, 12])and wrote the assignment x = append_ordered(x, 10), then str_ll(x) returns the string "1->3->8->10->12->None". Your code should work correctly regardless of whether the other value is added at the front, middle, or rear of the linked list. You may not use any other data structures (e.g., you may not put all the values into a list, sort the list, and then put all the values into a linked list), nor call any other helper functions: write the iterative code.

Answer 1

A python programming language (code) was used for this exercise.

The code is shown below in the explanation section

Step-by-step explanation:

Solution

Python code:

class LN:

def __init__(self,value,next=None):

self.value = value

self.next = next

def list_to_ll(self,l):

if l == []:

return None

front = rear = LN(l[0])

for v in l[1:]:

rear.next = LN(v)

rear = rear.next

return front

def str_ll(self,ll):

answer = ''

while ll != None:

answer += str(ll.value)+'->'

ll = ll.next

return answer + 'None'

def append_ordered(self,ll,v):

ln1=LN(v); #create a node with the new value by creating an instance of the LN class

if ll is None: #if the linked list is empty

ll=ln1 #return the new created node

elif(ll.value >= ln1.value): #if the value to be add is smallest, append the linked list to it

ln1.next=ll

ll=ln1

else:

current=ll; #crate a temporary pointer to iterate over linked list

#iterate till the next node value is smaller than the new value and list is not over

while (current.next is not None and current.next.value < ln1.value):

current=current.next

ln1.next=current.next #save the current node in the next of the new node

current.next=ln1 #save new node in the next of current node

return ll

ln=LN(0); #create an instance of class LN

ll1=ln.list_to_ll([1,2,4,5]); #create a linked list of the list

answer=ln.str_ll(ll1);

print(answer); #print the linked list

ll2=ln.append_ordered(ll1,3); #append the value 3 in the linked list

answer=ln.str_ll(ll2)

print(answer); #print the new linked list

Now,

• If Linked list is empty then make the node as head and return it.

• If value of the node to be inserted is smaller than value of head node, then insert the node at start and make it head.

• In a loop, find the appropriate node after which the input node ( 10 ) is to be inserted.To find the appropriate node start from head,keep moving until you reach a node GN (12 ) who's value is greater than the input node. The node just before GN is the appropriate node (8).

• Insert the node (10) after the appropriate node (8) found in step 3.

Note: Kindly find the output python code attached to the question below.