How to insert an item into a sorted linked list with constant time complexity?

Question

I have a problem in a sorted linked list. I cannot insert an item in constant time. If possible, how can I solve it?

And this complex time complexity is Big-O (N)

template <class ItemType> void SortedType<ItemType>::InsertItem(ItemType item) { NodeType<ItemType>* newNode; NodeType<ItemType>* predLoc; NodeType<ItemType>* location; bool moreToSearch; location = listData; predLoc = NULL; moreToSearch = (location != NULL); while (moreToSearch) { if (location->info < item) { predLoc = location; location = location->next; moreToSearch = (location != NULL); } else moreToSearch = false; } newNode = new NodeType<ItemType>; newNode->info = item; if (predLoc == NULL) { newNode->next = listData; listData = newNode; } else { newNode->next = location; predLoc->next = newNode; } length++; } 

Answer 1

It is not possible to insert an item into a sorted linked list with constant time complexity. But you can insert an element into O (log n) time complexity.

how to apply binary search O (log n) in a sorted linked list?

Answer 2

It is not possible to insert an item into a sorted linked list with O (1) time complexity. You can insert an item into an unsorted linked list with O (1) time complexity. You can learn more about time complexity from this link http://bigocheatsheet.com/

Answer 3

This is actually not possible in a sorted linked list, but you can insert an element into an unrelated linked list with a constant time, which is Big-O (1).

and also see this ...
https://www.youtube.com/watch?v=tta6BIiIIFI