Массив, который можно быстро изменить

Ответ 1

Просто подведем несколько структур данных:

System.Collections.ArrayList: нетипизированные структуры данных устарели. Вместо этого используйте List (t).

System.Collections.Generic.List(из t): это представляет собой изменяемый размер массива. Эта структура данных использует внутренний массив за кулисами. Добавление элементов в список равно O (1) до тех пор, пока базовый массив не будет заполнен, иначе его O (n + 1) изменит размер внутреннего массива и скопирует элементы.

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

Добавление элементов эффективно только при добавлении в конец списка. Вставка в середине заставляет массив перемещать все элементы вперед, что является операцией O (n). Удаление элементов также равно O (n), так как массиву необходимо переместить элементы назад.

System.Collections.Generic.LinkedList(из t): если вам не нужен случайный или индексированный доступ к элементам в вашем списке, например, вы планируете добавлять элементы и итерации с первого для продолжения, тогда LinkedList - ваш друг. Вставками и удалениями являются O (1), поиск - O (n).

Ответ 2

Для этого вам следует использовать Generic List < > (System.Collections.Generic.List). Он работает в постоянном амортизированном времени.

Он также имеет следующие функции с массивами.

• Быстрый произвольный доступ (вы можете получить доступ к любому элементу в списке в O (1))
• Быстро перевернуть
• Медленно вставлять и удалять объекты в начале или в середине (так как он должен делать копию всего списка)

Если вам нужны быстрые вставки и удаления в начале или конце, используйте либо связанный список, либо очереди

Ответ 3

Будет ли LinkedList <T> работает для вас? Это не (в некоторых случаях) как интуитивное, как прямой массив, но очень быстрый.

• AddLast для добавления в конец
• AddBefore/AddAfter для вставки в список
• AddFirst для добавления в начало

Однако это не так быстро для случайного доступа, поскольку вам нужно перебирать структуру для доступа к вашим элементам... однако у нее есть методы .ToList() и .ToArray() для захвата копии структуры в списке /array, поэтому для доступа к чтению вы можете сделать это в крайнем случае. Увеличение производительности вставки может перевешивать снижение производительности в случае произвольного доступа, или это может быть не так. Это будет полностью зависеть от вашей ситуации.

Там также эта ссылка, которая поможет вам решить, какой именно путь:

Когда использовать связанный список по списку массивов/массивов?

Ответ 4

Что для вас "достаточно хорошо"? Что именно вы хотите сделать с этой структурой данных?

Нет структуры массива (т.е. доступ O (n)) позволяет вставить в середину без O (n) времени исполнения; вставка в конце - это O (n) наихудший случай, а O (1) амортизируется для массивов с самоуничтожением, таких как ArrayList.

Может быть hashtables (амортизированный O (1) доступ и вставка в любом месте, но O (n) наихудший случай для вставки) или деревья (O (log (n)) для доступа и вставки где угодно, гарантировано) лучше подходят.

Ответ 5

Если скорость ваша проблема, я не вижу, как выбранный ответ лучше, чем использование необработанного массива, хотя он и изменяет размеры, он использует тот же механизм, который вы использовали бы для изменения размера массива (и должен дольше), если вы всегда добавляете в конец, и в этом случае он должен делать что-то немного умнее, потому что он выделяет кусок за раз, а не только один элемент.

Если вы часто добавляете около начала/середины своей коллекции и не часто указываете на середину/конец очень часто, вам, вероятно, нужен связанный список. Это будет иметь самое быстрое время вставки и будет иметь большое время итерации, оно просто засасывает при индексировании (например, глядя на третий элемент с конца или на 72-й элемент).