Inserting a Node Into a Sorted Doubly Linked List
Given a reference to the head of a doubly-linked list and an integer,  create a new DoublyLinkedListNode object having data value and insert it at the proper location to maintain the sort.

Function Description

Complete the sortedInsert function in the editor below.

sortedInsert has two parameters:

DoublyLinkedListNode pointer head: a reference to the head of a doubly-linked list

int data: An integer denoting the value of the  field for the DoublyLinkedListNode you must insert into the list.

Returns

DoublyLinkedListNode pointer: a reference to the head of the list

Note: Recall that an empty list (i.e., where ) and a list with one element are sorted lists.

Input Format

The first line contains an integer , the number of test cases.

Each of the test case is in the following format:

The first line contains an integer , the number of elements in the linked list.

Each of the next lines contains an integer, the data for each node of the linked list.

The last line contains an integer,, which needs to be inserted into the sorted doubly-linked list.

Constraints

Sample Input
1
4
1
3
4
10
5

Sample Output
1 3 4 5 10

#!/bin/python3
import math
import os
from pickle import NONE
import random
import re
import sys

class DoublyLinkedListNode:
    def __init__(self, node_data):
        self.data = node_data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    def insert_node(self, node_data):
        node = DoublyLinkedListNode(node_data)
        if not self.head:
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
def print_doubly_linked_list(node, sep, fptr):
    while node:
        fptr.write(str(node.data))
        node = node.next
        if node:
            fptr.write(sep)

 

 

 

def sortedInsert(head, data):

 

    temp=head

 

    while(temp.data<data and temp.next!=None):

 

        pre=temp

 

        temp=temp.next

 

    if(temp.prev==None):

 

        node = DoublyLinkedListNode(data)

 

        node.next=temp

 

        temp.prev=node

 

       

 

        return node

 

    elif(temp.next==None and temp.data<data):

 

        node = DoublyLinkedListNode(data)

 

        temp.next=node

 

        node.prev=temp

 

        return head

 

 

 

    else:

 

 

 

        node = DoublyLinkedListNode(data)

 

        pre.next=node

 

        node.prev=pre

 

        node.next=temp

 

        temp.prev=node

 

        return head

 

 

 

if __name__ == '__main__':

 

    fptr = open(os.environ['OUTPUT_PATH'], 'w')

 

 

 

    t = int(input())

 

 

 

    for t_itr in range(t):

 

        llist_count = int(input())

 

 

 

        llist = DoublyLinkedList()

 

 

 

        for _ in range(llist_count):

 

            llist_item = int(input())

 

            llist.insert_node(llist_item)

 

 

 

        data = int(input())

 

 

 

        llist1 = sortedInsert(llist.head, data)
        print_doubly_linked_list(llist1, ' ', fptr)

 

        fptr.write('\n')
    fptr.close()