Is there a special way of inserting in a sorted linked list?(<O(n))
Printable View
Is there a special way of inserting in a sorted linked list?(<O(n))
If you are talking about a singly linked list then the answer is no.
In general, no there isn't. However you can get amortised O(log n) insertion time into a skiplist.Quote:
Originally Posted by sagsriv
However, if you have a lot of insertions to do, you can store a small sorted selection of those nodes in a temporary array and allow an O(log n) search time.
There are many alternatives to what you're doing, as well:
If you have a bunch of items to insert then you could first sort the items to be inserted, then do a merge pass on the two lists.
Perhaps you can simply add them to the end, and re-sort the list every now and then.
Another idea is using a self-balancing binary tree instead.
It would be best for you to give more background on what the list insertions are part of. Show us the bigger picture.
Thanx PING and iMalc. Actually, I have seen this question (insert an element in a sorted linked list) in lots of technical interview papers. So, I thought there was something special with this 'sorted' term,as, in an array, we would have used a binary search first, then place the number in the proper position. But for linked list, this option is not time efficient (is it?).Nyways, seems these interviewers try to baffle people with dis typo questions.
Well, if coded correctly, O(impossible) can finish pretty quickly. But no, you don't have random access to the elements of a linked list, so you can't do binary search.Quote:
Originally Posted by sagsriv
I realize that I'm a mere academic, but I would guess the point of this interview question would not be to worry about speed, but just to get it right (off the top of my head, given a standard sorted linked list, I can think of exactly one way to do it).