Lista w C# — wydajność, pułapki i dobre praktyki

List<T> to jedna z najczęściej używanych kolekcji w .NET — elastyczna, wygodna, prosta w obsłudze. Dzięki niej nie musisz z góry znać liczby elementów, a dodawanie nowych wartości wydaje się banalne. Ale ta wygoda ma swoją cenę: niewłaściwe użycie listy, zwłaszcza przy dużych zbiorach danych, może prowadzić do poważnych problemów z wydajnością.

Jak List<T> działa pod maską

Wewnętrznie List<T> to opakowanie na zwykłą tablicę o zmiennym rozmiarze. Gdy tablica się zapełni, kolekcja alokuje nową, większą (domyślnie podwaja pojemność) i kopiuje do niej wszystkie dotychczasowe elementy. To dlatego, jeśli znasz przybliżoną docelową liczbę elementów, warto podać ją w konstruktorze — unikniesz serii kosztownych realokacji:

var lista = new List<int>(capacity: 10_000);

Rozróżnienie, o którym łatwo zapomnieć: Count to liczba faktycznie przechowywanych elementów, a Capacity to rozmiar wewnętrznej tablicy — zwykle większy niż Count, żeby zostawić miejsce na kolejne dodania bez natychmiastowej realokacji.

Złożoność czasowa — dlaczego nie każda operacja kosztuje tyle samo

Dlaczego wstawianie w środku jest kosztowne

Dodanie elementu na końcu listy to szybka, tania operacja. Ale wstawienie elementu w środku wymaga przesunięcia wszystkiego, co znajduje się za tym miejscem — List<T> przechowuje dane sekwencyjnie w pamięci, więc to nie tylko logiczne przesunięcie, ale fizyczne kopiowanie danych w pamięci RAM.

Dla listy 5- czy 100-elementowej to niezauważalne. Ale na liście z milionem elementów operacja, która wygląda niewinnie, zaczyna kosztować naprawdę dużo czasu — i to samo dotyczy usuwania elementów ze środka lub początku.

// ❌ antywzorzec: wstawianie na początku listy w pętli
var lista = new List<int>();
for (int i = 0; i < 10_000; i++)
{
    lista.Insert(0, i); // każde wstawienie przesuwa WSZYSTKIE dotychczasowe elementy
}
// złożoność: 10 000 wstawień × przesunięcie rosnącej liczby elementów = O(n²)

// ✅ z LinkedList<T> — wstawianie na początku to O(1), bez przesuwania czegokolwiek
var linkedLista = new LinkedList<int>();
for (int i = 0; i < 10_000; i++)
{
    linkedLista.AddFirst(i);
}
// złożoność: 10 000 wstawień × O(1) = O(n)

Dla 10 000 elementów różnica między O(n²) a O(n) to różnica między milisekundami a sekundami — a rośnie tym drastyczniej, im większa kolekcja. To dokładnie ten scenariusz, w którym “wygląda niewinnie w kodzie” i “jest tanie w wykonaniu” to dwie zupełnie różne rzeczy.

Kiedy List<T> jest najlepszym wyborem

Lista to wciąż świetna kolekcja, o ile używasz jej z głową. Najczęstsze dobre zastosowania:

• budowanie kolekcji krok po kroku przez dodawanie elementów na końcu,
• wyszukiwanie i wyliczanie elementów (pod tym względem lista działa niemal jak tablica),
• sytuacje, w których nie znasz z góry liczby elementów.

Jeśli planujesz częste wstawianie lub usuwanie elementów na początku czy w środku dużej kolekcji, rozważ alternatywę:

• LinkedList<T> — szybkie wstawianie/usuwanie w dowolnym miejscu (O(1), gdy masz już referencję do węzła), ale brak szybkiego dostępu po indeksie (O(n)).
• Queue<T> — gdy naprawdę potrzebujesz tylko FIFO (dodawanie na końcu, usuwanie z początku) — obie operacje O(1), bez przesuwania danych.
• Stack<T> — analogicznie dla LIFO.
• Dictionary<TKey, TValue> / HashSet<T> — gdy potrzebujesz błyskawicznego wyszukiwania (O(1) zamiast O(n) jak w liście), kosztem utraty kolejności i indeksowania.

Podsumowanie

Lista to potężne narzędzie, ale jak każde narzędzie wymaga świadomości swoich ograniczeń. W większości przypadków najlepszym zastosowaniem List<T> jest budowanie kolekcji przez dynamiczne dodawanie elementów na końcu — właśnie tam jest ona swoim najmocniejszym wariantem. W momencie, gdy zauważysz, że Twój kod regularnie wstawia lub usuwa elementy z początku czy środka dużej listy, to sygnał, żeby sprawdzić jedną z alternatyw powyżej, zanim wydajność stanie się realnym problemem produkcyjnym.