C# data structures

C# 14 uses .NET collection types. Availability can vary by the .NET target framework, but the types below are the standard choices for current .NET applications.

Help-desk ticket system

The ticket-system scenario uses a different collection for each operation: a dictionary for ID lookup, a set for duplicate events, a queue for arrival order, and a priority queue for urgent work.

public record Ticket(string Id, string Title, int Priority);

var ticketsById = new Dictionary<string, Ticket>();
var processedEvents = new HashSet<string>();
var waitingTickets = new Queue<string>();
var urgentTickets = new PriorityQueue<string, int>();

var ticket = new Ticket("HD-1042", "Cannot sign in", 1);
ticketsById[ticket.Id] = ticket;

if (processedEvents.Add("evt-8"))
{
    waitingTickets.Enqueue(ticket.Id);
    urgentTickets.Enqueue(ticket.Id, ticket.Priority);
}

PriorityQueue<TElement, TPriority> removes the lowest priority value first, so use 1 for the most urgent ticket or provide priorities accordingly. See Data structure decisions for why each collection is used and Big O notation for the trade-offs.

Language-level data structures

struct

A value type, copied by value. Use it for small data with value semantics.

public readonly struct Point(int x, int y)
{
    public int X { get; } = x;
    public int Y { get; } = y;
}

Point origin = new(0, 0);

record struct

A value type with generated value equality and a concise declaration.

public readonly record struct Coordinate(int Latitude, int Longitude);

Coordinate paris = new(49, 2);

class and record

Reference types. A record adds value-based equality; a class normally uses reference equality.

public record Person(string Name, int Age);

Person person = new("Ada", 36);

enum

A named set of integral constants.

public enum Status { Pending, Active, Complete }

Status status = Status.Active;

Tuples

Use ValueTuple syntax for lightweight grouped values. Use Tuple<...> when reference-type tuple semantics are required.

(string Name, int Score) result = ("Mia", 100);
Console.WriteLine(result.Name);

Tuple<string, int> legacy = Tuple.Create("Mia", 100);

Sequential collections

Arrays: T[] and multidimensional arrays

Fixed-size, indexed collections. Use rectangular arrays for matrix-like data and jagged arrays for rows of different lengths.

int[] numbers = [10, 20, 30];
int[,] matrix = { { 1, 2 }, { 3, 4 } };
int[][] jagged = [[1, 2], [3]];

List<T>

A resizable, indexed array. This is the usual default for an ordered mutable collection.

List<string> names = ["Ada", "Linus"];
names.Add("Grace");
Console.WriteLine(names[0]);

LinkedList<T>

A doubly linked list. It is useful when you retain nodes and frequently insert or remove near them.

LinkedList<string> route = new(["Start", "Finish"]);
route.AddAfter(route.First!, "Stop");

ArraySegment<T>

A view over a contiguous slice of an existing array without copying it.

int[] values = [1, 2, 3, 4];
ArraySegment<int> middle = new(values, 1, 2);
Console.WriteLine(middle[0]); // 2

Span<T> and ReadOnlySpan<T>

Stack-only views over contiguous memory. They avoid allocations and work with arrays, strings, and stack memory.

Span<int> buffer = stackalloc[] { 1, 2, 3 };
ReadOnlySpan<int> firstTwo = buffer[..2];

Memory<T> and ReadOnlyMemory<T>

Heap-safe, asynchronous-friendly counterparts to spans.

Memory<byte> bytes = new byte[1024];
bytes.Span[0] = 42;

Stack and queue collections

Stack<T>

Last in, first out (LIFO).

Stack<string> undo = new();
undo.Push("Type text");
string action = undo.Pop();

Queue<T>

First in, first out (FIFO).

Queue<string> jobs = new();
jobs.Enqueue("Send email");
string job = jobs.Dequeue();

PriorityQueue<TElement, TPriority>

Removes the element with the lowest priority value first by default.

PriorityQueue<string, int> triage = new();
triage.Enqueue("Critical incident", 1);
triage.Enqueue("Documentation", 5);
string next = triage.Dequeue();

Set collections

HashSet<T>

An unordered collection of unique values with fast membership checks.

HashSet<string> tags = ["csharp", "dotnet"];
tags.Add("csharp"); // Duplicate ignored.
bool hasDotnet = tags.Contains("dotnet");

SortedSet<T>

A unique collection kept in sorted order.

SortedSet<int> scores = [30, 10, 20];
Console.WriteLine(scores.Min); // 10

BitArray

A compact, indexable sequence of Boolean values.

BitArray flags = new(8);
flags[3] = true;

FrozenSet<T>

An immutable, read-optimized set. Build it once when lookup speed matters more than construction cost.

using System.Collections.Frozen;

FrozenSet<string> commands = new[] { "start", "stop" }.ToFrozenSet();
bool known = commands.Contains("start");

Key-value collections

Dictionary<TKey, TValue>

An unordered key-value map with fast lookup by key.

Dictionary<string, int> stock = new()
{
    ["apples"] = 12
};
stock["apples"]++;

SortedDictionary<TKey, TValue>

A key-value map whose entries stay sorted by key.

SortedDictionary<string, int> rankings = new()
{
    ["Mia"] = 1,
    ["Ada"] = 2
};

SortedList<TKey, TValue>

A sorted key-value map stored in arrays. It uses less memory than SortedDictionary and favors reads over inserts.

SortedList<int, string> months = new()
{
    [1] = "January",
    [2] = "February"
};

FrozenDictionary<TKey, TValue>

An immutable, read-optimized dictionary.

using System.Collections.Frozen;

FrozenDictionary<string, int> codes = new Dictionary<string, int>
{
    ["OK"] = 200
}.ToFrozenDictionary();

KeyValuePair<TKey, TValue>

Represents one key-value entry, commonly while enumerating a dictionary.

KeyValuePair<string, int> item = new("apples", 12);
Console.WriteLine($"{item.Key}: {item.Value}");

Immutable collections

Immutable collections return a new collection for every change, making them safe to share without mutation.

ImmutableArray<T>

An immutable, array-like collection with low overhead.

using System.Collections.Immutable;

ImmutableArray<int> ids = [1, 2];
ImmutableArray<int> updated = ids.Add(3);

ImmutableList<T>, ImmutableHashSet<T>, and ImmutableSortedSet<T>

Immutable equivalents of list and set collections.

using System.Collections.Immutable;

ImmutableHashSet<string> roles = ["reader"];
roles = roles.Add("editor");

ImmutableDictionary<TKey, TValue> and ImmutableSortedDictionary<TKey, TValue>

Immutable key-value maps.

using System.Collections.Immutable;

ImmutableDictionary<string, int> ports =
    ImmutableDictionary<string, int>.Empty.Add("https", 443);

ImmutableQueue<T> and ImmutableStack<T>

Immutable FIFO and LIFO collections.

using System.Collections.Immutable;

ImmutableQueue<string> queue = ImmutableQueue<string>.Empty.Enqueue("job");
string next = queue.Peek();

Thread-safe collections

Types in System.Collections.Concurrent coordinate access from multiple threads. They do not make multi-step operations automatically atomic.

ConcurrentDictionary<TKey, TValue>

A thread-safe key-value map.

using System.Collections.Concurrent;

ConcurrentDictionary<string, int> counters = new();
counters.AddOrUpdate("requests", 1, (_, count) => count + 1);

ConcurrentQueue<T>, ConcurrentStack<T>, and ConcurrentBag<T>

Thread-safe FIFO, LIFO, and unordered work-sharing collections.

using System.Collections.Concurrent;

ConcurrentQueue<string> messages = new();
messages.Enqueue("hello");
messages.TryDequeue(out string? message);

BlockingCollection<T>

A producer-consumer wrapper that can block and optionally limit capacity.

using System.Collections.Concurrent;

using BlockingCollection<int> work = new(boundedCapacity: 100);
work.Add(42);
int item = work.Take();

Observable collection

ObservableCollection<T>

A mutable list that raises change notifications, often used for data-bound UI.

using System.Collections.ObjectModel;

ObservableCollection<string> items = ["First"];
items.CollectionChanged += (_, _) => Console.WriteLine("Changed");
items.Add("Second");

Common collection interfaces

Program against these interfaces when callers do not need a concrete implementation.

IEnumerable<int> sequence = [1, 2, 3]; // Enumerate only.
IReadOnlyList<int> readOnly = [1, 2, 3]; // Enumerate and index.
ICollection<int> collection = new List<int>(); // Add, remove, count.
ISet<int> set = new HashSet<int>(); // Set operations.
IDictionary<string, int> map = new Dictionary<string, int>(); // Key lookup.

Choosing a structure