Collections in C#

Interview-ready overview of collection types, interfaces, and patterns.

---

Memory hook

"IEnumerable = iterate; ICollection = count + modify; IList = index; IDictionary = key-value; ISet = unique set; IQueryable = query (e.g. EF)"

---

IEnumerable<T>
      ↓
ICollection<T>
      ↓
  ├── IList<T>
  │      ├── List<T>
  │      └── T[] (Array)
  │
  ├── IDictionary<TKey, TValue>
  │      ├── Dictionary<TKey, TValue>
  │      ├── SortedDictionary<TKey, TValue>
  │      └── SortedList<TKey, TValue>
  │
  ├── ISet<T>
  │      ├── HashSet<T>
  │      └── SortedSet<T>
  │
  ├── LinkedList<T>
  │
  ├── Queue<T>
  │
  └── Stack<T>

Categories

Type	Use case	Key APIs	Implements / Inherits
Array	Fixed size, known length	Length, indexer [], Clone, CopyTo, IndexOf, LastIndexOf, Reverse, Sort,ForEach,	IList<T>, ICollection<T>, IEnumerable<T>
List<T>	Dynamic, index access	Count, Add, AddRange, Insert, InsertRange, Remove, RemoveAt, RemoveAll, RemoveRange, Clear, Contains, IndexOf, LastIndexOf, Sort, Reverse, ToArray, ForEach, Find, FindAll, Exists, CopyTo, indexer [], GetEnumerator	IList<T>, ICollection<T>, IEnumerable<T>
Dictionary<K,V>	Key-value lookup	Count, Remove, Clear, ContainsKey, TryGetValue, Keys, Values, indexer [], GetEnumerator,ForEach, GetValueOrDefault	IDictionary<K,V>, ICollection<KeyValuePair<K,V>>, IEnumerable<KeyValuePair<K,V>>
SortedDictionary<K,V>	Sorted key-value map	Count, Add, Remove, Clear, ContainsKey, ContainsValue, TryGetValue, Keys, Values, indexer [], GetEnumerator, sorted by key	IDictionary<K,V>, ICollection<KeyValuePair<K,V>>, IEnumerable<KeyValuePair<K,V>>
SortedList<K,V>	Sorted list/dictionary hybrid	Count, Capacity, Add, Remove, Clear, ContainsKey, ContainsValue, TryGetValue, Keys, Values, indexer [], GetEnumerator, IndexOfKey, IndexOfValue, sorted by key	IDictionary<K,V>, ICollection<KeyValuePair<K,V>>, IEnumerable<KeyValuePair<K,V>>
HashSet<T>	Unique items, fast Contains	Count, Add, Contains, Remove, ExceptWith, IntersectWith, UnionWith, IsProperSubsetOf, IsProperSupersetOf, IsSubsetOf, IsSupersetOf, Overlaps, SetEquals, Clear, CopyTo, GetEnumerator	ISet<T>, ICollection<T>, IEnumerable<T>
Queue<T>	FIFO	Count, Enqueue, Dequeue, Peek, Clear, Contains, CopyTo, ToArray, TrimExcess, GetEnumerator	ICollection<T>, IEnumerable<T>
Stack<T>	LIFO	Count, Push, Pop, Peek, Clear, Contains, CopyTo, ToArray, TrimExcess, GetEnumerator	ICollection<T>, IEnumerable<T>
LinkedList<T>	Insert/remove in middle	Count, AddFirst, AddLast, AddBefore, AddAfter, Remove, RemoveFirst, RemoveLast, Clear, Contains, Find, FindLast, First, Last, CopyTo, GetEnumerator	ICollection<T>, IEnumerable<T>

---

Core collection types: Storage and Time Complexity

Type	Memory Storage	Access []	Insert / Add	Remove	Search/Contains
Array	Contiguous block (fixed size), on heap	O(1)	N/A (fixed size)	N/A (fixed size)	O(n)
List<T>	Dynamic array (wraps internal array)	O(1)	O(1) amortized	O(n) (by index)	O(n)
Dictionary<K,V>	Hash table (buckets, array of slots + links)	~O(1)	~O(1)	~O(1)	~O(1) (by key)
HashSet<T>	Hash table (like Dictionary w/o value)	~O(1)	~O(1)	~O(1)	~O(1) (by value)
Queue<T>	Circular buffer (array)	N/A	O(1) Enqueue	O(1) Dequeue	O(n)
Stack<T>	Array (grows dynamically)	N/A	O(1) Push	O(1) Pop	O(n)
LinkedList<T>	Doubly linked list (nodes on heap)	O(n)	O(1) (at ends/node)	O(1) (at node)	O(n)

Key notes:

• Array: Elements are stored in a continuous block of memory. Direct index access is O(1).
• List<T>: Backed by an array internally; resizes by allocating a larger array when needed (amortized O(1) for add, but O(n) worst case during resize). Remove at arbitrary position or search is O(n).
• Dictionary<K,V> / HashSet<T>: Use hash table strategy. Good hash distribution provides O(1) lookup, add, remove; worst-case O(n) if too many collisions (rare).
• Queue<T> / Stack<T>: Use array (circular for Queue). Both provide O(1) operations for core use (Enqueue/Dequeue/Push/Pop).
• LinkedList<T>: Nodes allocated on heap, not contiguous. Fast O(1) insert/remove at known node (and at ends), but O(n) search or random access.

Arrays vs Generic Collections

• Arrays: Fixed size, indexed by integer, fast access. E.g., int[]. Good for simple, known-size data.
• Generic Collections: Flexible size, strong typing with <T>, avoid boxing/unboxing. Types include List<T> (dynamic array), Dictionary<K,V> (key-value), HashSet<T> (unique items), Queue<T> (FIFO), Stack<T> (LIFO), LinkedList<T> (fast insert/remove).
• All can hold value types, reference types, or any generic T. Using generics ensures compile-time type safety.

---

Interface hierarchy

IEnumerable<T>;  →  ICollection<T>;  →  IList<T>;
     (iterate)           (+ Count, Add, Remove)    (+ indexer)

IEnumerable<T>;  → IQueryable<T>;

// Difference:
// - IEnumerable<T>: Represents a sequence of objects you can iterate over in memory (supports foreach/LINQ). Used with in-memory collections like arrays, List&lt;T&gt, etc.
// - IQueryable<T>: Used for querying remote data sources (e.g., databases via Entity Framework). Supports deferred execution and can translate LINQ expressions to queries like SQL.

// Usage Examples:

// IEnumerable<T> example (most common, in-memory)
var fruits = new List<string> { "apple", "banana", "cherry" };
IEnumerable<string> result = fruits.Where(f => f.StartsWith("a")); // Filtering is done in memory

// IQueryable<T> example (Entity Framework, remote data)
IQueryable<User> adults = dbContext.Users.Where(u => u.Age > 18); // Query is translated and run in the database

// Note: IQueryable<T> is typically used internally by ORMs (like Entity Framework) for remote querying. In most application code, you usually work with IEnumerable&lt;T&gt unless you need to build queries for external data sources.

• IEnumerable — GetEnumerator(), foreach, LINQ
• ICollection — Count, Add, Remove, Clear
• IList — indexer, Insert, RemoveAt
• IQueryable — expression trees; used by EF (queries translated to SQL)

---

Iterator and yield

"yield return = lazy sequence; compiles to state machine using IEnumerator; elements not generated until needed."

When you use yield return, the compiler generates a hidden class that implements IEnumerator<T>. This allows your method to pause and resume between each value, without storing all results up front.

How it works:

• Each call to MoveNext() advances to the next yield return.
• The value is accessible via Current.
• The sequence can be infinite, or expensive to produce, but items are only computed as needed.

public static IEnumerable<int> GetNumbers()
{
    yield return 1;        // On first MoveNext(), Current==1
    yield return 2;        // On second MoveNext(), Current==2
    yield return 3;        // On third MoveNext(), Current==3
}

// Manual illustration:
var enumerator = GetNumbers().GetEnumerator();
while (enumerator.MoveNext()) // Calls method up to next yield, returns false at end
{
    Console.WriteLine(enumerator.Current); // 1, then 2, then 3
}
// OR simply:
foreach (var n in GetNumbers()) { Console.WriteLine(n); }

Why use it?

• Deferred execution: values aren't created until you move through the sequence.
• Minimal memory: doesn't need to build a List.
• Great for filtering, reading files/streams, generators (Fibonacci, etc.).

Cheat:
yield lets you write “lazy” iterators—methods that look like a loop, but which return values one-at-a-time whenever the caller asks for them via IEnumerator.MoveNext()/Current.

• Compiler generates state machine
• Execution is deferred until enumeration
• Use for large or infinite sequences

---

Custom collection

• Implement IEnumerable<T> (and optionally ICollection<T> / IList<T>)
• Or inherit Collection<T> and override as needed

public class MyCollection<T> : ICollection<T>
{
    private readonly List<T> _items = new();
    public int Count => _items.Count;
    public void Add(T item) => _items.Add(item);
    public bool Remove(T item) => _items.Remove(item);
    public IEnumerator<T> GetEnumerator() => _items.GetEnumerator();
}

---

ICollection vs List – When & Why?

Quick hierarchy:

IEnumerable<T> → ICollection<T> → IList<T> → Lis<T>

Use ICollection<T> for navigation properties (e.g. EF Core):

• It's an abstraction—lets you swap implementations, exposes only needed operations.
• Promotes flexible, clean API design.

public class Blog
{
    public ICollection<Post> Posts { get; set; } = new List<Post>();
}

Rule:
Use ICollection<T> for entity collections. Use List<T> if you actually require indexing.

---

Cheat sheet

List = dynamic + index
Dictionary = key → value
HashSet = unique + Contains
Queue = FIFO; Stack = LIFO
IEnumerable = foreach; IQueryable = EF query
yield = lazy iteration