Time complexity of inserting a node in a sorted linked list

Question

What is the time complexity of inserting a node in a sorted linked list in Java? Is there an algorithm with complexity less than O(n)?

• willeM_ Van Onsem: Usually not, unless there you have references to several nodes in the list.
• Oliver Charlesworth: With only O(1) references into the list (e.g. head + tail), then no.
• Omore: @OliverCharlesworth there is no pointers in Java.
• Oliver Charlesworth: @Omore - NullPointerException disagrees ;) (Didn't notice that this was marked Java...)

Answer 1

If all you have is a linked links and you're starting from the head, in the worst case you have to iterate over the entire list to find the insertion point. This gives O(n) worst-case time.

Something like a skiplist could give O(log n) insertion. However, that's a different data structure to what you're asking about (and so are trees etc).