1class DoublyLinkedListNode:
2 def __init__(self, node_data):
3 self.data = node_data
4 self.next = None
5 self.prev = None
6
7def sortedInsert(head, data):
8 node = DoublyLinkedListNode(data)
9 if (head == None):
10 return node
11 elif (data < head.data):
12 node.next = head
13 head.prev = node
14 return node
15 else:
16 node = sortedInsert(head.next, data)
17 head.next = node
18 node.prev = head
19 return head
20