Is there a special way of inserting in a sorted linked list?(<O(n))

Printable View

- 03-15-2008sagsrivinsertion in a sorted linked list
Is there a special way of inserting in a sorted linked list?(<O(n))

- 03-15-2008PING
If you are talking about a singly linked list then the answer is no.

- 03-15-2008iMalc
In general, no there isn't. However you can get amortised O(log n) insertion time into a skiplist.

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. - 03-15-2008sagsriv
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.

- 03-15-2008tabstop
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.

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).