Podstawowe struktury danych w C# — przegląd

Struktura danych to sposób organizacji danych w pamięci, dobrany pod kątem operacji, które będziesz na nich wykonywać najczęściej. Ten artykuł to mapa całego terenu — krótkie przypomnienie struktur, które mają już swoje dedykowane, szczegółowe wpisy na tym blogu (z linkami), oraz pełne omówienie z działającym kodem C# dla trzech struktur, których nigdzie indziej na blogu nie znajdziesz: list wiązanych, drzew binarnych i kopców.

Klasyfikacja struktur danych

• Liniowe — elementy ułożone sekwencyjnie, każdy (poza skrajnymi) ma jednego poprzednika i następcę: tablice, listy, stosy, kolejki, listy wiązane.
• Nieliniowe — elementy tworzą bardziej złożone relacje niż prosta sekwencja: drzewa, grafy.

Pełną klasyfikację algorytmów operujących na tych strukturach (dziel i zwyciężaj, zachłanne, programowanie dynamiczne) znajdziesz w osobnym artykule: Klasyfikacja Algorytmów.

Struktury z dedykowanymi wpisami na blogu

Poniższe struktury mają pełne, osobne omówienie (API, złożoność, pułapki, przykłady) — tutaj tylko krótkie przypomnienie, po co je stosować:

• Tablica — stały rozmiar, dostęp po indeksie w O(1). Zobacz Tablica w C#.
• List<T> — dynamiczna tablica, rośnie automatycznie. Zobacz wydajność listy i praktyczne zastosowania.
• Stack<T> — LIFO, ostatni dodany pierwszy zdjęty. Zobacz Stack w C#.
• Queue<T> — FIFO, pierwszy dodany pierwszy zdjęty. Zobacz Queue w C#.
• HashSet<T> / Dictionary<TKey,TValue> — dostęp i wyszukiwanie średnio O(1) dzięki tablicy haszującej. Zobacz HashSet i Dictionary.
• Sortowanie i przeszukiwanie — komplet algorytmów (bąbelkowe, przez wstawianie, selection, quick, merge, bucket, wyszukiwanie liniowe i binarne) z analizą złożoności krok po kroku: zobacz Klasyfikację Algorytmów, która linkuje do każdego z nich.
• Grafy — przechodzenie (DFS, BFS, Dijkstra) — reprezentacja grafu jako listy sąsiedztwa i pełny, działający kod przeszukiwania: zobacz Algorytmy krok po kroku.

Listy wiązane (Linked List) — struktura, której .NET używa rzadziej niż myślisz

Lista wiązana składa się z węzłów (Node), gdzie każdy węzeł przechowuje dane oraz referencję do następnego węzła. W przeciwieństwie do tablicy czy List<T>, elementy nie leżą obok siebie w pamięci — są rozproszone, połączone wskaźnikami.

public class Node<T>
{
    public T Value;
    public Node<T>? Next;

    public Node(T value) => Value = value;
}

public class SinglyLinkedList<T>
{
    private Node<T>? head;

    public void AddFirst(T value)
    {
        var node = new Node<T>(value) { Next = head };
        head = node;
    }

    public void AddLast(T value)
    {
        var node = new Node<T>(value);

        if (head is null)
        {
            head = node;
            return;
        }

        var current = head;
        while (current.Next is not null)
        {
            current = current.Next;
        }
        current.Next = node;
    }

    public IEnumerable<T> Traverse()
    {
        var current = head;
        while (current is not null)
        {
            yield return current.Value;
            current = current.Next;
        }
    }
}

var lista = new SinglyLinkedList<string>();
lista.AddLast("A");
lista.AddLast("B");
lista.AddFirst("Start");

foreach (var element in lista.Traverse())
    Console.WriteLine(element);
// Start, A, B

Dlaczego rzadko piszesz to sam

.NET ma gotową, podwójnie wiązaną System.Collections.Generic.LinkedList<T> — z węzłami LinkedListNode<T> dostępnymi bezpośrednio, co pozwala na wstawianie/usuwanie w O(1), jeśli już masz referencję do węzła. Problem w praktyce: żeby dojść do konkretnego węzła, i tak musisz przejść listę od początku — O(n). To dlatego w kodzie C# lista wiązana pojawia się rzadko — List<T> ma gorszą złożoność teoretyczną dla wstawiania w środku (O(n) przez przesuwanie pamięci), ale w praktyce często wygrywa dzięki lokalności pamięci podręcznej procesora (cache locality) — ciągły blok pamięci jest szybszy do przeglądania niż rozproszone węzły, nawet przy teoretycznie gorszej złożoności.

Drzewa binarne i BST — hierarchia zamiast sekwencji

Drzewo to struktura nieliniowa: każdy węzeł ma najwyżej dwóch “potomków” (w drzewie binarnym), tworząc hierarchię zamiast prostej sekwencji. Drzewo wyszukiwań binarnych (BST) dodaje regułę porządkującą: dla każdego węzła wszystkie wartości w lewym poddrzewie są mniejsze, a w prawym — większe.

public class TreeNode<T> where T : IComparable<T>
{
    public T Value;
    public TreeNode<T>? Left;
    public TreeNode<T>? Right;

    public TreeNode(T value) => Value = value;
}

public class BinarySearchTree<T> where T : IComparable<T>
{
    private TreeNode<T>? root;

    public void Insert(T value)
    {
        root = InsertRecursive(root, value);
    }

    private TreeNode<T> InsertRecursive(TreeNode<T>? node, T value)
    {
        if (node is null) return new TreeNode<T>(value);

        if (value.CompareTo(node.Value) < 0)
            node.Left = InsertRecursive(node.Left, value);
        else if (value.CompareTo(node.Value) > 0)
            node.Right = InsertRecursive(node.Right, value);

        return node; // wartości równe istniejącej ignorujemy (brak duplikatów)
    }

    public bool Contains(T value)
    {
        var current = root;
        while (current is not null)
        {
            int comparison = value.CompareTo(current.Value);
            if (comparison == 0) return true;
            current = comparison < 0 ? current.Left : current.Right;
        }
        return false;
    }

    // Przechodzenie in-order zwraca wartości w kolejności rosnącej — właściwość BST
    public IEnumerable<T> InOrderTraversal() => InOrder(root);

    private IEnumerable<T> InOrder(TreeNode<T>? node)
    {
        if (node is null) yield break;

        foreach (var value in InOrder(node.Left)) yield return value;
        yield return node.Value;
        foreach (var value in InOrder(node.Right)) yield return value;
    }
}

var bst = new BinarySearchTree<int>();
foreach (var n in new[] { 50, 30, 70, 20, 40, 60, 80 })
    bst.Insert(n);

Console.WriteLine(bst.Contains(40));  // true
Console.WriteLine(string.Join(", ", bst.InOrderTraversal()));
// 20, 30, 40, 50, 60, 70, 80 — in-order zawsze zwraca posortowaną kolejność

Złożoność zależy od kształtu drzewa. Dla drzewa zrównoważonego (mniej więcej tyle samo węzłów po obu stronach) wyszukiwanie, wstawianie i usuwanie to O(log n) — bo każde porównanie odrzuca połowę pozostałych węzłów, podobnie jak wyszukiwanie binarne. Ale jeśli wstawiasz dane już posortowane (1, 2, 3, 4, 5…), drzewo degeneruje się do listy wiązanej — O(n) dla każdej operacji. Samo-równoważące się warianty (drzewa AVL, czerwono-czarne) rozwiązują ten problem kosztem bardziej złożonej implementacji — .NET używa drzewa czerwono-czarnego pod maską SortedSet<T>, więc w praktyce rzadko piszesz własne BST od zera.

Kopce (Heap) — struktura, której używasz częściej niż myślisz

Kopiec to kompletne drzewo binarne z jedną własnością: w kopcu minimalnym każdy węzeł jest mniejszy lub równy swoim dzieciom (najmniejszy element zawsze w korzeniu), w kopcu maksymalnym — odwrotnie. Dzięki temu dostęp do najmniejszego/największego elementu to O(1), a dodanie lub usunięcie elementu z zachowaniem własności kopca to O(log n).

Nie musisz pisać własnego kopca w C# — .NET dostarcza gotowy PriorityQueue<TElement, TPriority> (od .NET 6), zaimplementowany właśnie jako kopiec minimalny pod maską:

var queue = new PriorityQueue<string, int>();

queue.Enqueue("Zadanie o niskim priorytecie", 5);
queue.Enqueue("Zadanie pilne", 1);
queue.Enqueue("Zadanie średnie", 3);

while (queue.TryDequeue(out var zadanie, out var priorytet))
{
    Console.WriteLine($"{priorytet}: {zadanie}");
}
// 1: Zadanie pilne
// 3: Zadanie średnie
// 5: Zadanie o niskim priorytecie

To dokładnie ta struktura stoi za implementacją algorytmu Dijkstry (najkrótsza ścieżka w grafie z wagami) — pełny, działający kod znajdziesz w artykule Algorytmy krok po kroku. Kopiec jest też podstawą algorytmu sortowania heapsort — buduje kopiec ze wszystkich elementów, a potem wielokrotnie zdejmuje korzeń.

Struktury specjalistyczne — krótko

Poniższe struktury rozwiązują konkretne, wąskie problemy — nie są codziennym narzędziem, ale warto wiedzieć, że istnieją:

• Trie (drzewo prefiksowe) — każdy węzeł to jeden znak, ścieżka od korzenia definiuje słowo. Idealne do autouzupełniania i sprawdzania pisowni.
• Drzewo sufiksów — przechowuje wszystkie sufiksy tekstu, umożliwiając bardzo szybkie wyszukiwanie wzorców. Stosowane w bioinformatyce (analiza sekwencji DNA) i kompresji danych.
• Drzewo B — zrównoważone drzewo z wieloma dziećmi na węzeł, zoptymalizowane pod odczyt z dysku. Fundament indeksów w bazach danych i systemach plików.

Podsumowanie

Wybór struktury danych to pytanie o operacje, które będziesz wykonywać najczęściej: potrzebujesz dostępu po indeksie? Tablica/List. Kolejność LIFO/FIFO? Stack/Queue. Błyskawiczne sprawdzanie przynależności? HashSet/Dictionary. Hierarchia z szybkim wyszukiwaniem? Drzewo zrównoważone (SortedSet). Zawsze potrzebujesz najmniejszego/największego elementu? Kopiec (PriorityQueue). Żadna struktura nie jest uniwersalnie “najlepsza” — każda to świadomy kompromis między szybkością różnych operacji.