List<T>, Dictionary<TKey,TValue>, HashSet<T> — you've used all of them for a whole module now. They were generic types the entire time. Here's the rest of the family.
Back in Foundations, you learned List<T>, Dictionary<TKey,TValue>, HashSet<T>, Stack<T>, and Queue<T> as "the collections" — practical tools, used because they worked. At the time, the <T> in each name was just part of the syntax you typed. Now, after several lessons on generics, that angle-bracket notation means something concrete: every one of those types is a generic class, instantiated with whatever type argument your code supplies.
In this lesson, you'll revisit those five familiar collections through that new lens, then meet four more that round out the .NET generic collections toolkit: LinkedList<T>, SortedList<TKey,TValue>, SortedDictionary<TKey,TValue>, and SortedSet<T>. By the end, you'll know exactly which collection earns its place for a given job.
The generic collections in System.Collections.Generic are ready-made, reusable data structures — a growable list, a key-lookup table, a set with no duplicates, a stack, a queue, and a few more specialized shapes — each one written once against a type parameter T (or TKey/TValue), so it works identically and type-safely no matter what kind of data you put in it.
Every type covered in this lesson is a generic class (or, for Stack<T> and Queue<T>, likewise generic) living in System.Collections.Generic, each implementing the collection interface hierarchy you already studied (IEnumerable<T>, ICollection<T>, and, where it makes sense, IList<T> or IDictionary<TKey,TValue>). "Generic collection" simply means: a collection type parameterized by the element type it holds, checked by the compiler at every call site, with no runtime casting or boxing for the reference-type case, and no boxing at all for value types — exactly the guarantees the "Generics" lesson promised, now paying off across the entire collections toolkit.
Before generics existed in C#, .NET's collections lived in System.Collections — ArrayList, Hashtable, and friends — and every one of them stored object, because that was the only way to write "a collection that holds anything" without generics. That meant every value type went in and out through boxing (real, measurable overhead, as covered in earlier lessons), and every read required an explicit cast the compiler couldn't verify — a cast that could fail at runtime if the collection secretly held a mix of types.
// The old, non-generic way — don't write new code like this
ArrayList list = new ArrayList();
list.Add(42); // boxed — an int wrapped in a heap object
list.Add("oops"); // ArrayList has no idea this doesn't belong
int first = (int)list[0]; // works, but only because you got lucky
int second = (int)list[1]; // InvalidCastException at runtimeGeneric collections fix exactly this: a List<int> flatly refuses to accept a string at compile time — no cast is ever needed to read an int back out, and no value type ever gets boxed to be stored. The entire System.Collections.Generic namespace exists so you get compile-time type safety, no boxing overhead, and no manual casting, for every shape of collection you'd ever reasonably need.
| Collection | Shape | Ordering | Duplicates? | Familiar or new |
|---|---|---|---|---|
List<T> | Resizable indexed array | Insertion order | Yes | Familiar (Foundations 033) |
Dictionary<TKey,TValue> | Hash-bucketed key/value pairs | Unordered | Keys unique | Familiar (Foundations 034) |
HashSet<T> | Hash-bucketed unique values | Unordered | No | Familiar (Foundations 035) |
Stack<T> | LIFO — last in, first out | Push/pop order | Yes | Familiar (Foundations 036) |
Queue<T> | FIFO — first in, first out | Enqueue/dequeue order | Yes | Familiar (Foundations 036) |
LinkedList<T> | Doubly-linked nodes | Insertion order (explicit) | Yes | New |
SortedList<TKey,TValue> | Sorted array of key/value pairs | Always sorted by key | Keys unique | New |
SortedDictionary<TKey,TValue> | Sorted tree of key/value pairs | Always sorted by key | Keys unique | New |
SortedSet<T> | Sorted tree of unique values | Always sorted | No | New |
public class List<T> : IList<T>, IReadOnlyList<T>, ...List<Product>, List<int>, or List<string> you've ever written is the exact same generic definition, closed with a different type argument — precisely the mechanism from the "Generics" lesson.public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>, ...
where TKey : notnullwhere TKey : notnull, exactly as covered in the constraints lessons.HashSet<T> is a generic class over a hash-bucketed structure guaranteeing uniqueness (the mechanics of which the next lesson digs into). Stack<T> and Queue<T> are generic classes wrapping a resizable buffer with LIFO or FIFO access respectively — no indexing, by design, since that's not the access pattern they're for.var history = new LinkedList<string>();
history.AddLast("Home");
history.AddLast("Products");
LinkedListNode<string> current = history.AddLast("Cart");
history.AddAfter(current, "Checkout"); // O(1) — no shifting, unlike List<T>.InsertLinkedListNode<T>, holding a reference to the node before it and after it. Inserting or removing at a known node position is O(1) — no shifting of other elements, unlike List<T>.Insert, which is O(n) because everything after the insertion point has to move over.history[2]. Reaching the nth element means walking node by node from one end, an O(n) operation. LinkedList<T> earns its place specifically when you're frequently inserting or removing in the middle, and rarely need positional access.var prices = new SortedList<string, decimal>();
prices.Add("Widget", 9.99m);
prices.Add("Anvil", 149.99m);
prices.Add("Gadget", 24.99m);
foreach (var (name, price) in prices)
Console.WriteLine($"{name}: {price:C}");
// Anvil: $149.99 ← always visited in sorted key order, automatically
// Gadget: $24.99
// Widget: $9.99var prices = new SortedDictionary<string, decimal>();
prices.Add("Widget", 9.99m);
prices.Add("Anvil", 149.99m); // O(log n) insert — a red-black tree underneathSortedList<TKey,TValue>, but backed by a balanced binary search tree (a red-black tree) instead of a sorted array — insertion and removal are O(log n) rather than O(n), at the cost of somewhat higher memory overhead per entry and no fast indexed access by position.var ids = new SortedSet<int> { 42, 7, 19, 7, 3 }; // duplicate 7 silently ignored
foreach (int id in ids)
Console.Write($"{id} ");
// 3 7 19 42 ← unique AND sorted, automaticallyHashSet<T>'s uniqueness guarantee, combined with SortedDictionary's tree-based always-sorted ordering — the set-flavored member of the sorted family, useful whenever you need both "no duplicates" and "always in order" at once.// Same data, four different collections, four different trade-offs
List<string> asList = ["Charlie", "Alice", "Bob"];
Console.WriteLine(string.Join(", ", asList)); // Charlie, Alice, Bob (insertion order)
LinkedList<string> asLinked = new(asList);
Console.WriteLine(string.Join(", ", asLinked)); // Charlie, Alice, Bob (insertion order)
SortedSet<string> asSortedSet = new(asList);
Console.WriteLine(string.Join(", ", asSortedSet)); // Alice, Bob, Charlie (always sorted, unique)
HashSet<string> asHashSet = new(asList);
Console.WriteLine(string.Join(", ", asHashSet)); // unordered, unique — order not guaranteedCode → Meaning → Result:
List<T> and LinkedList<T> preserve insertion order; SortedSet<T> imposes sort order; HashSet<T> makes no ordering promise at all.A generic Repository<T> for an e-commerce product catalog needs to keep products sorted by SKU for fast, ordered browsing, while a "recently viewed" feature needs fast insert/remove at both ends with a bounded history — two different jobs, two different collection choices, inside the same application.
public record Product(string Sku, string Name, decimal Price);
public class ProductCatalog
{
// Sorted by SKU automatically, O(log n) insert/lookup — great for a browsable, ordered catalog
private readonly SortedDictionary<string, Product> _bySku = new();
public void Add(Product product) => _bySku[product.Sku] = product;
public IEnumerable<Product> BrowseInSkuOrder() => _bySku.Values;
}
public class RecentlyViewedTracker
{
private const int MaxHistory = 10;
// Fast add/remove at both ends — perfect for a bounded, order-sensitive history
private readonly LinkedList<string> _recentSkus = new();
public void Track(string sku)
{
_recentSkus.Remove(sku); // if already present, drop the stale position
_recentSkus.AddFirst(sku); // most recent goes to the front
if (_recentSkus.Count > MaxHistory)
_recentSkus.RemoveLast(); // evict the oldest — O(1), no shifting
}
public IEnumerable<string> MostRecentFirst() => _recentSkus;
}
var catalog = new ProductCatalog();
catalog.Add(new Product("WID-003", "Widget", 9.99m));
catalog.Add(new Product("ANV-001", "Anvil", 149.99m));
catalog.Add(new Product("GAD-002", "Gadget", 24.99m));
foreach (var p in catalog.BrowseInSkuOrder())
Console.WriteLine(p.Sku);
// ANV-001, GAD-002, WID-003 — sorted, with zero manual sorting codeNeither collection here was picked arbitrarily — SortedDictionary<TKey,TValue> earns its place because the catalog genuinely needs "always sorted by key, efficient insert," and LinkedList<T> earns its place because the tracker genuinely needs "cheap insert/remove at both ends, bounded size." A plain List<T> would work for both, technically — but it would mean manually re-sorting the catalog after every insert, and shifting every element on every eviction from the front of the history.
Think of the generic collections as a toolbox, not a single all-purpose gadget. A List<T> is a shelf of labeled slots — fast to grab item #5, slower to insert a new item in the middle since everything after it has to shift down. A LinkedList<T> is a chain of paper clips — trivially easy to add or remove a clip anywhere in the chain, but to find the 5th clip you have to count from one end, one at a time. A SortedDictionary<TKey,TValue> is a filing cabinet that reorganizes itself the instant you add a folder, so it's always alphabetized — convenient for browsing, at the cost of a little extra work on every insert.
None of these is "the best" tool in general — each is the best tool for a specific job, and the whole point of learning the toolbox is knowing which one to reach for.
GetHashCode(). Lookup, insert, and remove are all O(1) on average — the next lesson dedicates itself entirely to exactly how this works. No ordering is preserved, since bucket placement depends on the hash, not insertion sequence.SortedList<TKey,TValue>, SortedDictionary<TKey,TValue>, and SortedSet<T> maintain their sort order continuously, as items are added and removed — you never call a Sort() method, because there's never a moment where the collection is out of order to begin with. This is different from calling List<T>.Sort() once, which sorts the current contents but doesn't keep future insertions sorted.
2. SortedList vs SortedDictionary — same guarantee, different internals, real trade-offBoth keep keys sorted; they're not interchangeable performance-wise. SortedList<TKey,TValue> uses less memory per entry and is faster for read-heavy, rarely-modified data (its array-backed indexer lookup is efficient). SortedDictionary<TKey,TValue> is the better choice when you're inserting and removing frequently, since its tree-based O(log n) insert beats the array's O(n) shifting.
LinkedList<T> is rarely the right default, despite sounding fundamentalNew developers often reach for LinkedList<T> because it sounds like "the real data structure," while List<T> sounds like "just an array." In practice, List<T>'s contiguous memory layout makes it faster for the vast majority of real workloads, even ones with some insertions — modern CPUs are extremely fast at sequential memory access, and the shifting cost is often smaller in practice than the pointer-chasing cost of a linked structure. Reach for LinkedList<T> only when you've measured a genuine, frequent middle-insertion bottleneck.
LinkedList<T> the way you would a List<T> Wrong — doesn't compile; LinkedList<T> has no indexer at all:
var chain = new LinkedList<string>();
string third = chain[2]; // compile error — no indexer on LinkedList<T> Correct — walk the nodes, or reconsider whether you actually need positional access (if you do, List<T> is probably the better fit in the first place):
LinkedListNode<string>? node = chain.First;
for (int i = 0; i < 2 && node is not null; i++) node = node.Next;
string? third = node?.Value;SortedDictionary when you actually need positional, index-based access Reaching for SortedDictionary<TKey,TValue> and then trying to get "the 5th entry by position" — trees don't support efficient index-based access. If both sorted order and fast index access matter, SortedList<TKey,TValue>'s array backing is the better fit.
Defaulting to List<T> for everything, including cases with heavy duplicate-checking (better: HashSet<T>) or a need for continuous sorted order (better: SortedSet<T> or a sorted dictionary). Ask "how will this collection actually be read and modified?" first — insertion pattern, lookup pattern, ordering needs — then pick the collection whose trade-offs match.
LinkedList<T> — frequent inserts/removals at known positions (especially both ends), and you rarely need indexed access.SortedList<TKey,TValue> — data is mostly built once, read often, and you want it always sorted with a lower memory footprint.SortedDictionary<TKey,TValue> — frequent inserts/removals, and you still need everything sorted by key at all times.SortedSet<T> — you need both "no duplicates" and "always sorted" simultaneously.List<T> remains the right general-purpose default for most sequences — don't reach for LinkedList<T> "just in case."Dictionary<TKey,TValue> / HashSet<T> beat their sorted counterparts whenever you don't actually need sorted iteration — their average O(1) operations are faster than a tree's O(log n).List<T>, Dictionary<TKey,TValue>, or HashSet<T> — they're the right default for the overwhelming majority of everyday code. Reach for one of the four newer collections only once you can name the specific access pattern (frequent middle insertion, continuous sort order) that the familiar five don't handle well.
<T> mechanics you've studied all module, just applied.List<T>, Dictionary<TKey,TValue>, HashSet<T>, Stack<T>, and Queue<T> were generic classes the entire time — the collections work you did in Foundations already put generics into practice.LinkedList<T> gives O(1) insert/remove at known positions, at the cost of O(n) positional access and no indexer.SortedList<TKey,TValue> and SortedDictionary<TKey,TValue> both keep keys continuously sorted — the array-backed list favors memory and read speed, the tree-backed dictionary favors frequent insert/remove.SortedSet<T> combines uniqueness with continuous sort order.You've reconnected the familiar collections to generics, and met four new ones. Let's check your understanding.
1. Why is inserting into the middle of a List<T> an O(n) operation, while inserting at a known node in a LinkedList<T> is O(1)?
Correct: B
Why B is correct: As covered in "Under the Hood," List<T>'s contiguous array layout means a middle insertion must shift every following element to make room, while LinkedList<T>'s separate nodes only need their neighboring pointers updated — no shifting of unrelated data at all.
Why A is incorrect: This is a fundamental structural trade-off of contiguous storage, not an implementation flaw — the same trade-off appears in essentially every programming language's array-backed list.
Why C is incorrect: LinkedList<T> stores every element, just distributed across individually-allocated nodes rather than one contiguous block.
Why D is incorrect: The complexities genuinely differ — this is precisely why each collection earns its place for different access patterns.
Reinforcement: Contiguous memory favors fast indexed access and slow middle insertion; linked nodes favor the exact opposite trade-off.
2. You need a collection of product IDs that is always kept sorted, and you'll be inserting and removing IDs frequently as products come and go. Which collection best fits?
Correct: B
Why B is correct: As covered in "Common Confusion," the tree-backed sorted collections handle frequent inserts/removals far better than the array-backed SortedList<TKey,TValue>, whose array shifting makes each insert O(n).
Why A is incorrect: SortedList<TKey,TValue> is actually the weaker choice specifically for frequent modification — it shines when data is built once and read often instead.
Why C is incorrect: Re-sorting the whole list after every single change is far more expensive than maintaining sort order incrementally, which the sorted collections do automatically.
Why D is incorrect: LinkedList<T> makes no sorting guarantee at all — you'd have to manually find the correct insertion point yourself every time, which defeats the purpose.
Reinforcement: When both "always sorted" and "frequent modification" matter together, a tree-backed sorted collection is the natural fit.
3. What is the key difference between calling List<T>.Sort() once and using a SortedSet<T>?
Correct: B
Why B is correct: As explained in "Common Confusion," List<T>.Sort() is a one-time operation — adding a new item afterward can leave the list unsorted again until you call Sort() once more. A SortedSet<T> keeps itself sorted at all times, and as a set, also silently rejects duplicates.
Why A is incorrect: List<T> has no ongoing sorting guarantee — a later Add can easily break the order established by an earlier Sort() call.
Why C is incorrect: Whether one is "faster" depends entirely on the access pattern — repeated re-sorting of a frequently-changing list can easily be slower overall than a self-maintaining sorted collection.
Why D is incorrect: This reverses the actual behavior — List<T> allows duplicates freely; SortedSet<T>, being a set, rejects them.
Reinforcement: "Sorted" as a collection name means continuously self-maintaining order, not a one-off operation you have to remember to repeat.
You now know the full generic collections toolkit and how to pick the right one. Next: how Dictionary<TKey,TValue> actually achieves that average O(1) lookup — hash buckets, GetHashCode, and collision handling, under the hood.
dotnetmadeeasy.com — Learn C# and .NET, the right way.