Коллекции: Array, List, Dictionary, HashSet, Queue, Stack — что выбрать и какая сложность?

var list = new List<int>(capacity: 1000);   // задайте ёмкость, если размер известен — меньше копирований
list.Add(1);
list.AddRange([2, 3, 4]);
int first = list[0];                          // O(1)
bool has = list.Contains(3);                  // O(n) — перебор
list.Remove(3);                               // O(n): поиск + сдвиг
list.RemoveAt(list.Count - 1);                // O(1) с конца
list.Sort();                                  // O(n log n)

var stock = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase)
{
    ["apple"] = 5,
    ["pear"] = 3,
};

stock["banana"] = 10;                        // добавить или заменить
stock.Add("kiwi", 1);                        // ArgumentException, если ключ уже есть
int n = stock["apple"];                      // KeyNotFoundException, если ключа нет!

if (stock.TryGetValue("mango", out var count))   // безопасное чтение — одна операция поиска
    Console.WriteLine(count);

stock.TryAdd("pear", 100);                   // false — уже есть, значение не меняется
stock.Remove("pear");
foreach (var (fruit, qty) in stock) Console.WriteLine($"{fruit}: {qty}");   // порядок не гарантирован

var seen = new HashSet<string>();
foreach (var email in emails)
    if (!seen.Add(email))                    // Add возвращает false для дубликата
        Console.WriteLine($"Дубликат: {email}");

var a = new HashSet<int> { 1, 2, 3 };
var b = new HashSet<int> { 2, 3, 4 };
a.IntersectWith(b);   // {2, 3} — также UnionWith, ExceptWith, IsSubsetOf

var tasks = new Queue<string>();
tasks.Enqueue("письмо 1"); tasks.Enqueue("письмо 2");
while (tasks.TryDequeue(out var t)) Send(t);       // обработка в порядке поступления

var undo = new Stack<string>();
undo.Push("ввёл текст"); undo.Push("удалил строку");
var last = undo.Pop();                              // "удалил строку" — отмена последнего действия

var pq = new PriorityQueue<string, int>();          // очередь с приоритетом (.NET 6+)
pq.Enqueue("обычный", 5); pq.Enqueue("срочный", 1);
pq.Dequeue();                                       // "срочный"

public IReadOnlyList<OrderLine> Lines => _lines;      // наружу — без права изменения
public decimal Sum(IEnumerable<decimal> values) => values.Sum();   // принимаем минимально необходимое