Lesson 1: Core Interfaces & Linear Data Structures

Understand the hierarchy of collection interfaces and the performance characteristics of List<T>.

Why Collection Interfaces Matter

In C#, the collection framework is built on a layered system of interfaces. Each interface in the chain adds more capabilities. Understanding these layers is not just academic — it directly impacts the APIs you design. When you accept an IEnumerable<T> as a parameter, you're telling callers "I only need to read your data." When you require an IList<T>, you're saying "I need random access." This informs your consumers about your intent, keeps coupling low, and makes your code far more testable.

IEnumerable<T> — The Root of Everything

IEnumerable<T> lives in System.Collections.Generic and is the most fundamental collection interface in .NET. It exposes a single method: GetEnumerator(), which returns an IEnumerator<T>. That enumerator has three members:

• Current — Returns the element at the current position.
• MoveNext() — Advances the enumerator to the next element. Returns false when there are no more elements.
• Reset() — Resets the enumerator back to the beginning (rarely used and often not implemented).

Under the hood, a foreach loop is syntactic sugar for calling GetEnumerator() and advancing with MoveNext():

// What the compiler generates from a foreach loop
IEnumerator<int> enumerator = collection.GetEnumerator();
try
{
    while (enumerator.MoveNext())
    {
        int item = enumerator.Current;
        // Use item...
    }
}
finally
{
    enumerator.Dispose();  // IEnumerator<T> implements IDisposable
}

yield return — Lazy Sequences

One of the most powerful features tied to IEnumerable<T> is the yield return keyword. It allows you to build a state machine that produces elements one at a time, on demand. No array or list is created in memory — the values are generated as the consumer iterates:

public static IEnumerable<int> FibonacciSequence(int count)
{
    int a = 0, b = 1;
    for (int i = 0; i < count; i++)
    {
        yield return a;
        int temp = a;
        a = b;
        b = temp + b;
    }
}

// Usage — nothing runs until we iterate
foreach (var num in FibonacciSequence(10))
{
    Console.WriteLine(num);
}

ICollection<T> — Adding Mutation

ICollection<T> extends IEnumerable<T> and introduces the ability to mutate the collection. It adds:

• Add(T item) — Adds an element to the collection.
• Remove(T item) — Removes the first occurrence of a specific element.
• Contains(T item) — Determines whether the collection contains a specific element.
• Clear() — Removes all elements from the collection.
• Count — Gets the number of elements (this is a property, not a method — unlike LINQ's .Count()).
• IsReadOnly — Indicates whether the collection is read-only.
• CopyTo(T[] array, int index) — Copies elements to an array starting at a particular index.

IList<T> — Random Access

IList<T> extends both ICollection<T> and IEnumerable<T>. Its major addition is index-based access:

• this[int index] — The indexer. Allows you to get or set elements by position (e.g., list[5]).
• IndexOf(T item) — Returns the zero-based index of the first occurrence of a value.
• Insert(int index, T item) — Inserts an element at the specified index.
• RemoveAt(int index) — Removes the element at the specified index.

Choosing between these interfaces in method signatures is about communicating intent:

// "I will only read through your data"
public void PrintAll(IEnumerable<string> items) { ... }

// "I need to add or remove elements"
public void ProcessQueue(ICollection<string> items) { ... }

// "I need to access items by their position"
public void SwapFirstAndLast(IList<string> items) { ... }

IReadOnlyCollection<T> and IReadOnlyList<T>

A parallel branch of the hierarchy that is critical for modern API design and frequently tested in interviews:

• IReadOnlyCollection<T> — Extends IEnumerable<T> and adds only Count. No mutation methods at all.
• IReadOnlyList<T> — Extends IReadOnlyCollection<T> and adds the read-only indexer this[int index].

// Exposing data safely: return IReadOnlyList, not List
public class OrderService
{
    private readonly List<Order> _orders = new();

    // BAD: Caller can cast to List<Order> and call .Add()
    public IEnumerable<Order> GetOrdersUnsafe() => _orders;

    // BETTER: IReadOnlyList exposes Count + indexer, no mutation
    public IReadOnlyList<Order> GetOrders() => _orders.AsReadOnly();
    // .AsReadOnly() returns a ReadOnlyCollection<T> wrapper
    // that throws on any mutation attempt, even after casting
}

The Interface Hierarchy

Visualizing the relationship helps cement the concept. The mutable and read-only branches both stem from IEnumerable<T>:

            ┌──────────────────────────────┐
            │   IEnumerable<T>             │  GetEnumerator()
            └──────────────┬───────────────┘
                 ┌─────────┴─────────┐
          mutable branch       read-only branch
                 │                   │
  ┌──────────────▼────┐   ┌──────────▼──────────────────┐
  │ ICollection<T>    │   │ IReadOnlyCollection<T>      │
  │ Add, Remove, Count│   │ Count (no mutation)         │
  └──────────────┬────┘   └──────────┬──────────────────┘
                 │                   │
  ┌──────────────▼────┐   ┌──────────▼──────────────────┐
  │ IList<T>          │   │ IReadOnlyList<T>            │
  │ this[i], Insert   │   │ this[i] (read-only)         │
  └──────────────┬────┘   └──────────┬──────────────────┘
                 │                   │
                 └─────────┬─────────┘
            ┌──────────────▼───────────────┐
            │   List<T>                    │  Implements BOTH branches
            └──────────────────────────────┘

List<T> — Under the Hood

List<T> is the most commonly used collection in C#. It implements IList<T> and is backed by an internal array (T[]). Understanding its internals is crucial for performance-sensitive code.

How the Internal Array Grows

When you call Add() and the internal array is full, List<T> allocates a new array of double the current capacity, copies all existing elements, and then adds the new one. This means:

• If the array has room, Add() is O(1).
• If the array needs to resize, that single call is O(n) due to the copy.
• Averaged over many additions, this "doubling strategy" yields an amortized O(1) per addition.

However, if you know the expected size upfront, you can eliminate resizing entirely by setting the capacity in the constructor:

// BAD: Will resize multiple times as elements are added
List<int> numbers = new List<int>();

// GOOD: Pre-allocate for 10,000 elements — no resizing needed
List<int> numbers = new List<int>(10000);

Big O Summary for List<T>

Other Useful List<T> Methods

Beyond the basics, List<T> offers several methods worth knowing for interviews:

• FindAll(Predicate<T>) — Returns a new List<T> containing all matching elements.
• Exists(Predicate<T>) — Returns true if any element matches the predicate.
• TrueForAll(Predicate<T>) — Returns true if every element matches.
• ConvertAll<TOutput>(Converter) — Projects each element into a new form (similar to LINQ's Select).
• GetRange(int index, int count) — Extracts a shallow copy of a range of elements.
• TrimExcess() — Reduces the capacity to the actual count (useful after heavy deletions).

Polymorphic Views of the Same Object

Because List<T> implements all three interfaces, a single list object can be referenced through different "lenses," each exposing a different level of capability:

// Pre-defining capacity keeps Add() at O(1)
List<int> numbers = new List<int>(1000);
numbers.Add(42);
numbers.Add(99);
numbers.Add(7);

// View 1: Read-only iteration (no access to Add, Remove, or indexer)
IEnumerable<int> readOnlyView = numbers;

// View 2: Full indexable access
IList<int> indexableView = numbers;
int value = indexableView[0]; // 42 — Allowed!

// View 3: Mutation without indexing
ICollection<int> collectionView = numbers;
collectionView.Add(55);     // Allowed
// collectionView[0];         // NOT allowed — ICollection has no indexer

Bonus: Arrays and Other Linear Structures

Arrays (T[])

Arrays are the most primitive collection in C#. They have a fixed size set at creation time and offer the fastest possible element access. Arrays implement IList<T> but throw NotSupportedException for Add() and Remove() since they cannot be resized. Use arrays when the size is known and fixed, and performance is critical.

LinkedList<T>

A doubly-linked list where each node points to its previous and next neighbor. It excels at O(1) insertions and deletions at known positions (via LinkedListNode<T>) but has O(n) search and no indexing. It is rarely used in modern C# because List<T>'s CPU cache locality typically makes it faster in practice for most workloads.

Queue<T> and Stack<T>

Queue<T> is a FIFO (First-In, First-Out) collection — elements are enqueued at the back and dequeued from the front. Stack<T> is LIFO (Last-In, First-Out) — elements are pushed and popped from the top. Both offer O(1) for their primary operations.

// Queue: FIFO
Queue<string> printJobs = new Queue<string>();
printJobs.Enqueue("Report.pdf");
printJobs.Enqueue("Invoice.pdf");
string next = printJobs.Dequeue(); // "Report.pdf"

// Stack: LIFO
Stack<string> undoHistory = new Stack<string>();
undoHistory.Push("Typed 'Hello'");
undoHistory.Push("Deleted line");
string lastAction = undoHistory.Pop(); // "Deleted line"

PriorityQueue<TElement, TPriority> (.NET 6+)

A min-heap-based priority queue that dequeues elements in order of their priority value. Unlike Queue<T> (FIFO), it always returns the element with the lowest priority first. This is essential for algorithms like Dijkstra's shortest path, event scheduling, and merging K sorted lists.

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

pq.Enqueue("Low priority task", 10);
pq.Enqueue("Critical fix", 1);
pq.Enqueue("Medium task", 5);

string next = pq.Dequeue(); // "Critical fix" (priority 1 — lowest first)

// Peek without removing
pq.TryPeek(out string element, out int priority);
// element = "Medium task", priority = 5

public static IList<string> FilterLongStrings(IEnumerable<string> input)
{
    // We can't know the exact count from IEnumerable alone,
    // but if the underlying type is ICollection, we can get a hint.
    int estimatedCapacity = 16; // sensible default

    if (input is ICollection<string> collection)
    {
        // At most, all items match, so use the collection's count
        estimatedCapacity = collection.Count;
    }

    List<string> result = new List<string>(estimatedCapacity);

    foreach (string s in input)
    {
        if (s != null && s.Length >= 5)
        {
            result.Add(s);
        }
    }

    // Optional: reclaim unused memory if the result is much smaller
    result.TrimExcess();

    return result;
}

// Usage:
string[] words = { "cat", "elephant", "dog", "giraffe", "owl", "zebra" };
IList<string> longWords = FilterLongStrings(words);
// Result: ["elephant", "giraffe", "zebra"]