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

Question

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

Answer 1

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

Answer 2

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

Цитирование из раздела примечаний docs.

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

Answer 3

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

Answer 4

В дополнение к правильному ответу 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.