I dont think you have to worry about the head node of CDLL. Its a very safe assumption to make . Now your method s adding a node in O(n) time, which can be improved to O(lgn) by making use of the fact that list is sorted. Just run a variant of Binary search on the list list , head pointer is given and tail = head->prev. In this variant , instead of returning true /false just return the pointer to the lower index where the Binary search recursion terminates. prev of this pointer is the place where you need to add the node.

Algorithm: Let's say the list is 1->2->3->5->7->1 and we want to insert 4. We don't know if the start node in iteration is head node or not. 1. Loop through the linked list and find out the head node. while (node.next.value > node.value) { node = node.next; } Node head = node.next; 2. Start from the head node and find the appropriate location for the new node to be inserted. Node temp = head; Node input = new Node(4); while (temp.next != head) { if (temp.value = 4) { Node link = temp.next; temp.next = input; input.next = link; return true; } temp = temp.next; } Let me know if this is incorrect or can be improved.