Adding members to C# List using indexes

Question

If I a declare a C# List. Make its capacity to 1000. Now, if I want to add an element directly at index 1. I am not able to do it. Throwing error. Are there any alternatives available?

    List<sometype> myList = new List<sometype>()
    myList.capacity = 1000;
    myList[1] = element; //exception thrown

The best alternative that I found is through array.

    sometype[] myarray = new sometype[1000];
    myarray[1] = element;
    //after filling whole array
    myarray.ToList();

Answer 1

List.Capacity only preallocates memory so that the list can grow to the capacity limit without incurring additional memory allocations and associated heap fragmentation. Setting List.Capacity to 1000 does not make 1000 entries accessible. List.Count indicates the end of the actual list contents. List.Insert() cannot be used to insert items beyond List.Count.

Your workaround of creating an array of 1000 items and then converting to a list is simply a shortcut to calling List.Add() 1000 times to allocate empty slots in the list (push List.Count to 1000). Calling List.Add() 1000 times is more memory efficient, since with the array technique there will be 2 copies of the list in memory (1 for the array, and 1 for the list).

You discounted the suggestion of using a Dictionary<int, sometype> for a sparse array because it would use more memory than a sparsely populated array. That depends on how sparse your data is. If you have only 100 items in an index range of 0..1000, you have 10% density. You can also call that 90% wasted memory.

A dictionary will almost certainly be more memory efficient for a low density sparse array than allocating an array of 1000 items but only using 100 of the slots. I don't know the specifics of Dictionary's implementation or memory use, but it's probably a safe guess that if your sparse array's density is 50% or greater, using an array instead of a dictionary wins for memory and speed.

Answer 2

The best alternative that I found is through array.

Correct, most will use an array for this as you demonstrated...

sometype[] myarray = new sometype[1000];
myarray[1] = element;

The other option is to check the bounds before setting the list element...

List<sometype> myList = new List<sometype>()
myList.capacity = 1000;
if( ix < myList.Count )
    myList[1] = element; //replace element
else
{
    while(myList.Count < (ix-1))
        myList.Add(default(sometype)); //fill with empty

    myList.Add(element);
}

Answer 3

You can use the Insert() method, like below:

myList.Insert(1, element); //1 is the index