Efficient C# data structure for insertion, deletion and rearranging at given indexes

Question

I'm looking for an efficient data structure in C# that allows me to keep a list of items ordered (by the user) without duplicates.

What I mean by ordered by the user, ie.:

• Insert element 1.
• Insert element 2 before element 1.
• Insert element 3 between 1 and 2. Then rearrange at will.

I will need the order to be continuously updated in a database upon change so that I can load it at start.

Operations I need:

1. Insert at a given index
2. Delete at a given index
3. Move from index x to index y (could be expressed as the combination of 2 and 1 if there is no loss in performance)

All of these operations will be frequent and equally important.

Answer 1

I assume by "efficient" you mean asymptotically efficient. If that's not the case, then clarify the question.

The combination of indexing and arbitrary insertion is a tricky one.

• List<T>s -- which are just a thin wrapper over arrays -- have O(1) insertion/deletion at the end, O(n) insertion/deletion at the beginning, and O(1) indexing. Checking uniqueness is O(n).
• Linked lists have O(1) insertion/deletion provided you already know where you want to put the item, but O(n) indexing to find that location. Checking uniqueness is O(n)
• Balanced binary trees have O(lg n) insertion and deletion and indexing if you're clever. Checking uniqueness is O(n). More exotic data structures like finger trees, skiplists, etc, are similar.
• Hash sets have O(1) insertion and deletion but no indexing; checking uniqueness is O(1).

There is no single data structure that fits your needs. My advice is:

1. Embrace immutability. Write an immutable data structure that meets your needs. It will be easier to reason about.
2. Write a combination of a balanced binary tree -- red-black, AVL, etc -- and a hash set. The hash set is used only for uniqueness checking. The BBT has the number of items below it in every node; this facilitates indexing. The insertion and deletion algorithms are as normal for your BBT, except that they also rewrite the spine of the tree to ensure that the item count is updated correctly.

This will give you O(1) uniqueness checking and O(lg n) indexing, inserting and deleting.

I note that this data structure gives you O(1) answers to the question "is this item in the collection?" but O(n) answers to the question "where is it?" so if you need the inverse indexing operation to be fast, you have a much larger problem on your hands.

Answer 2

I think I would just use a List and take O(n) Contains or a separate HashSet for uniqueness. List does all the other stuff nicely. Nicely as the operations are all there but most will be O(n). Even on 10,000 O(n) is pretty fast. The database calls are going to be the slowest part by far (try async).

    class MyCollection<T> : IList<T>
    {
        private readonly IList<T> _list = new List<T>();

        public void Insert(int index, T item)
        {
            if (this.Contains(item))
                throw new IndexOutOfRangeException();
            _list.Insert(index, item);
            //make database call
        }

        // implement all the other features of IList with database calls

Answer 3

This has kind of turned into two questions: one for the database layer and one for the in-memory collection. However, I think you can practically bring it back down to a single question if you let the database layer become your source of truth.

The reason I say this is that with roughly 100 items as the maximum likely number of active items in your list, you can pretty much ignore asymptotic complexity. Performance-wise, the most important thing to focus on when you've got this many items is round-trips across network connections (e.g. to the database).

Here's a fairly simple approach you can use. It's similar to something I've done in the past, with similar requirements. (I can't remember if it's exactly the same or not, but close enough.)

1. Use a numeric Order column to determine the order of your items within the given list. int should be just fine.
2. When you remove an item, decrement the orders of all items in the same list after that item. This can be done with a single UPDATE statement in SQL.
3. When you add an item, give it an Order value based on the location it's added at, and increment the orders of all items in the same list after that item (again, with a single Update statement).
4. When you move an item to a different location, change its Order and then increment or decrement the Orders of all the items between its starting and ending positions.
5. Every time a change is made, re-load the entire list of items, in order, from the database to display to the user.

You may want to use stored procs to do more of this work in individual round-trips. Definitely a transactions to avoid race conditions.

An approach like this will easily scale for individual users editing individual lists. If you need scalability in terms of concurrent users, it's likely that another strategy like a NoSQL store is going to be the way to go. If you need to scale on many concurrent users editing the same list, things get really complicated and you may need to implement message buses and other goodness. If you find that you need to scale to tens of thousands of items in the list, you'll need to rethink your UI and how it communicates with the server (e.g. you won't want to load the entire list into memory). But when each of the operations is performed manually by a user, worrying about your in-memory data structure isn't going to get you where you want to be in any of these cases.

Answer 4

In terms of data structures, a linked list is fast for inserts and deletes assuming you have direct reference to the nodes (in this case, you would want a doubly-linked list). I haven't used the built-in .NET LinkedList, but it seems it has some efficiency problems. You may want to just use a normal List if you have issues with LinkedList (Really depends on how "efficient" you need this to be.) See List time complexities here

As for saving it, all you need to do is save the index in your database and fill your collection from an query with an ORDER BY on start.

EDIT:

And for duplicate management, you could maintain a HashSet to check for duplicates and prevent insertion.