Просто суммируем несколько структур данных:
System.Collections.ArrayList : нетипизированные структуры данных устарели. Вместо этого используйте List (of t).
System.Collections.Generic.List (of t) : это представляет массив с изменяемым размером. Эта структура данных использует внутренний массив за сценой. Добавление элементов в List - это 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 (of t) : если вам не нужен случайный или индексированный доступ к элементам в вашем списке, например, вы только планируете добавлять элементы и выполнять итерацию от первого к наконец, LinkedList - ваш друг. Вставки и удаления - O (1), поиск - O (n).