List Data Structure C# Efficiency

Question

Hi, at the moment I'm using a List<short> as a buffer to hold things for a while while a calculation is made to each value based on other values further down the buffer. I then realised that this probably wasn't very effecient as I have been told that List<> is a linked list so every time I do whatever = myList[100]; the poor thing is having to jump down all the other nodes first to get to the value I want. I dont want to use a regular Array because I have got loads of Add() and Remove()s kicking around in other places in the code. So I need a class that inherits IList<T> but uses a regular array data structure. Does anyone know a class in .net that works this way so I dont have to write my own? I tried using ArrayList but it 'aint generic!

Answer 1

List<T> doesn't use a linked list implementation. Internally it uses an array, so it appears to be exactly what you need. Note that, because it's an array, Remove/insert could be an expensive operation depending on the size of the list and the position item being removed/inserted - O(n). Without knowing more about how you are using it, though, it's hard to recommend a better data structure.

Quoting from the Remarks section of the docs.

The List(T) class is the generic equivalent of the ArrayList class. It implements the IList(T) generic interface using an array whose size is dynamically increased as required.

Answer 2

No, a List<T> is a generic collection, not a linked list. If you need add and remove functionality then List<T> is the best type to use. I believe the CLR is optimised to handle them so performance need not be a concern.

Answer 3

List<T> is backed by an array, not a linked list. Indexed accesses of a List<T> happen in constant time.

Answer 4

In addition to tvanfosson's correct answer, if you're ever unsure of how something works internally, just load up the .NET Reflector and you can see exactly how things are implemented. In this case, drilling down to the indexer of List<T> shows us the following code:

public T this[int index]
{
    get
    {
        if (index >= this._size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }
        return this._items[index];
    }
    // ...

where you can see that this._items[index] is an array of the generic type T.