C# List Sort vs Inserting

Question

I have a list of objects which I sort multiple times throughout code and when the user interacts with the program. I was wondering if it would be better to insert new items into the list rather than add to the end of the list and resort the entire list.

The code below is for importing browser bookmarks - Here I add a bunch of bookmarks to the List (this._MyLinks) which are Link objects and then sort the final List - Which I think is probably best in this given scenario....

    public void ImportBookmarks(string importFile)
    {         
        using (var file = File.OpenRead(importFile))
        {
            var reader = new NetscapeBookmarksReader();
            var bookmarks = reader.Read(file);               
            foreach (var b in bookmarks.AllLinks)
            {
                bool duplicate = this._MyLinks.Any(link => link._URL == b.Url);
                if(duplicate)
                {
                    continue;
                }
                Link bookmark = new Link();
                bookmark._URL = b.Url;
                bookmark._SiteName = b.Title;
                bookmark.BrowserPath = "";
                bookmark.BrowserName = "";

                if (bookmark.AddToConfig(true))
                {
                    this._MyLinks.Add(bookmark);
                }

            }
        }
        this._MyLinks = this._MyLinks.OrderBy(o => o._SiteName).ToList();
    }

Now a user also has the option to add their own links (one at a time). Whenever the user adds a link the ENTIRE list is sorted again using

this._MyLinks = this._MyLinks.OrderBy(o => o._SiteName).ToList();

Is it better from a preformance standpoint (or just generally) to just insert the item directly into it's specified location? If so would you have suggestions on how I can go about doing that?

Thanks!

@PatrickHofman That's functionally identical to just inserting the new items into the middle of the list (that's all that that class does), and it's quite inefficient. — Servy, Aug 13 '15 at 14:35
@PatrickHofman It's a completely different data structure with completely different operations and performance characteristics of its operations. With respect to this case, it can add items in O(log(n)) time rather than O(n) time, and removes the additional linear search through the collection entirely. — Servy, Aug 13 '15 at 14:41
@OP If you need to access the elements by index, you *have* to use an indexable collection such as `SortedList` (you won't be able to use `SortedSet` with indexing), — Matthew Watson, Aug 13 '15 at 14:42
@MatthewWatson Which he's not doing, and there are of course ways around that problem in the even that it is actually need, *if* it's actually needed. — Servy, Aug 13 '15 at 14:43
@Servy Well, we don't really know `_MyLinks ` is used outside that method. — Matthew Watson, Aug 13 '15 at 14:44
However I totally agree that `SortedSet` is a very good solution if indexing isn't needed. — Matthew Watson, Aug 13 '15 at 15:01
@MatthewWatson I actually am using the index. Thank you for the suggestion I will give both SortedSet and SortedList a shot! — Paul, Aug 13 '15 at 15:07

score 3 · Accepted Answer · answered Aug 13 '15 at 14:34

Since you want a sorted set of data you should be using a more appropriate data structure, specifically a sorted data structure, rather than using an unsorted data structure that you re-sort every time, or that forces you to inefficiently add items to the middle of a list.

SortedSet is specifically designed to maintain a sorted set of data efficiently.

C# List Sort vs Inserting

1 Answers1