What are the differences between `List<T>`, `HashSet<T>`, and `Dictionary<TKey, TValue>`?

List<T>

• Structure: Dynamic array (ordered collection)
• Duplicates: Allows duplicates
• Access: Index-based (O(1) by index)
• Search: O(n) for Contains/Find
• Insertion: O(1) at end, O(n) at beginning/middle
• Use Case: When order matters and you need indexed access

var list = new List { 1, 2, 3, 2, 1 }; // Duplicates allowed
list.Add(4); // O(1)
var item = list[2]; // O(1) - indexed access
bool exists = list.Contains(3); // O(n)

HashSet<T>

• Structure: Hash table (unordered collection)
• Duplicates: No duplicates (enforced)
• Access: No indexing
• Search: O(1) average for Contains
• Insertion: O(1) average
• Use Case: Unique items, fast lookups, set operations

var hashSet = new HashSet { 1, 2, 3, 2, 1 }; // Only {1, 2, 3}
hashSet.Add(4); // O(1)
bool exists = hashSet.Contains(3); // O(1) - fast!
// No indexed access: hashSet[0] is invalid

// Set operations
var set1 = new HashSet { 1, 2, 3 };
var set2 = new HashSet { 3, 4, 5 };
set1.UnionWith(set2); // {1, 2, 3, 4, 5}
set1.IntersectWith(set2); // {3}

Dictionary<TKey, TValue>

• Structure: Hash table with key-value pairs
• Duplicates: Unique keys, duplicate values allowed
• Access: By key (O(1) average)
• Search: O(1) for key lookup
• Insertion: O(1) average
• Use Case: Key-value mappings, fast lookups by key

var dict = new Dictionary
{
    { 1, "One" },
    { 2, "Two" },
    { 3, "Three" }
};

dict.Add(4, "Four"); // O(1)
string value = dict[2]; // O(1) - by key
bool exists = dict.ContainsKey(3); // O(1)
bool hasValue = dict.ContainsValue("Two"); // O(n)

Comparison Table: