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)?
-
Usually not, unless there you have references to several nodes in the list.willeM_ Van Onsem– willeM_ Van Onsem2017-04-17 16:52:34 +00:00Commented Apr 17, 2017 at 16:52
-
1With only O(1) references into the list (e.g. head + tail), then no.Oliver Charlesworth– Oliver Charlesworth2017-04-17 16:54:25 +00:00Commented Apr 17, 2017 at 16:54
-
@OliverCharlesworth there is no pointers in Java.Omore– Omore2017-04-17 16:55:42 +00:00Commented Apr 17, 2017 at 16:55
-
2@Omore - NullPointerException disagrees ;) (Didn't notice that this was marked Java...)Oliver Charlesworth– Oliver Charlesworth2017-04-17 16:57:09 +00:00Commented Apr 17, 2017 at 16:57
Add a comment
|
1 Answer
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).
