Структура Данных Списка Эффективность C#

Question

Структура Данных Списка Эффективность C#

В данный момент я использую List<short> в качестве буфера для хранения вещей на некоторое время, пока вычисление производится для каждого значения на основе других значений ниже по буферу. Затем я понял, что это, вероятно, не очень эффективно, поскольку мне сказали, что List<> - это связанный список, поэтому каждый раз, когда я делаю whatever = myList[100];, бедняжке приходится сначала прыгать вниз по всем другим узлам, чтобы добраться до нужного мне значения. Я не хочу использовать обычный массив, потому что у меня есть множество Add() и Remove()S, разбросанных в других места в коде. Поэтому мне нужен класс, который наследует IList<T> , но использует обычную структуру данных массива. Кто-нибудь знает класс в .net, который работает таким образом, чтобы мне не пришлось писать свой собственный? Я пробовал использовать ArrayList, но он не универсальный!

523 4

c#generics .net

4 ответов:

Comments

Ничего не найдено.

David Neale · Accepted Answer · 2013-05-23 22:02:57

Нет, List<T> - это общая коллекция, а не связанный список. Если вам нужно добавить и удалить функциональность, то List<T> - это реализация, которую большинство людей используют по умолчанию.

tvanfosson · Accepted Answer · 2010-07-11 19:28:14

List<T> не использует реализацию связанного списка. Внутренне он использует массив, так что это, кажется, именно то, что вам нужно. Обратите внимание, что, поскольку это массив, удаление/вставка может быть дорогостоящей операцией в зависимости от размера списка и позиции удаляемого/вставляемого элемента - O(n). Однако, не зная больше о том, как вы его используете, трудно рекомендовать лучшую структуру данных.

Цитирование из раздела комментариев документаdocs .

Класс List (T) является универсальным эквивалентом класса ArrayList. Он реализует универсальный интерфейс IList(T), используя массив, размер которого динамически увеличивается по мере необходимости.

JSBձոգչ · Accepted Answer · 2010-07-11 19:25:56

List<T> поддерживается массивом, а не связанным списком. Индексированные обращения a List<T> происходят в постоянное время.

John Rasch · Accepted Answer · 2010-07-11 19:27:25

В дополнение к правильному ответу tvanfosson, если вы когда-либо не уверены в том, как что-то работает внутри, просто загрузите .NET Reflector, и вы сможете точно увидеть, как все реализовано. В этом случае детализация до индексатора List<T> показывает нам следующий код:
public T this[int index]
{
    get
    {
        if (index >= this._size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }
        return this._items[index];
    }
    // ...
, где видно, что this._items[index] является массивом универсального типа T.