Will a binary search on LinkedList<T> to insert a value into the middle of a sorted value list increase performance?

Question

I need to create a sorted list adding one item at a time. So I decided to go with LinkedList<T>, Since it is efficient in insert operations. But when finding the proper location, it seems to take much longer time. I am using linear search to get the location. If I use binary search to get the proper location using ElementAt method, will it increase the performance? According to this, still it is a O(n) operation. What do you think? If it is so, is there any other better data structure for the work? Because if I use a different data structure, when inserting a new value to the middle, I will have to shift all the data after that location by one location, which is obviously not desired.

Answer 1

Your question has a few misconceptions.

Will a binary search on LinkedList to insert a value into the middle of a sorted value list increase performance?

Binary search makes sense only on a sorted collection. LinkedList<T> isn't one. It's an insertion order respecting collection. To perform a binary search on a LinkedList<T>:

• you will have to either sort the linked list, which is not only very inefficient (operation on a linked list) but also too much work for mere insertion

• or you will have to maintain the sort order at the time of insertion itself by inserting in the right position, which is too much work again.

From your question what I understand is that you want a sort order respecting collection but insertions has to faster (unlike O(n) characteristic of say, a typical List<T>). My suggestion would be to use a sorted collection type in .NET. There is a SortedSet<T> in system.dll. That wouldn't let you have duplicates as it is a set, in which case you can implement a custom SortedBag<T> (or SortedList<T> or whatever name) as shown here.

I am using linear search to get the location.

My suggestion is that you dont do that. Let the collection itself find its location to perform an insert. Sorted collection types are best fit here.

If I use binary search to get the proper location using ElementAt method, will it increase the performance

ElementAt method doesn't perform binary search. At best it checks if collection type is an IList<T> and uses the indexer accordingly. No in your case it makes no difference to performance.

when inserting a new value to the middle, I will have to shift all the data after that location by one location, which is obviously not desired .

You're right, inserting in the middle of array based structures like List<T> is an O(n) operation. I'm not sure if you need index operation as well, but that will be costlier. You can either have a sorted collection type with efficient inserts which will have no sense of indexes, or you can have an indexed sorted collection type but insertions will be O(n). Its the trade off you have to pay.

Answer 2

For your purpose, you would probably be better off with a SortedDictionary class (or perhaps SortedList)

SortedDictionary gives O(log n) insert and retrieval times.