Collections in C#

List<T> is a resizable array that allows random access via an index. It automatically grows in size as new elements are added.

• Stores elements sequentially like an array.
• Allows index-based access.
• Automatically resizes as needed.
• Supports methods like Add(), Remove(), Insert(), Sort(), Find() etc.

• Use List<T> when you need a flexible, indexable, and resizable collection similar to arrays.

Stack<T> represents a LIFO collection where the last element added is the first one removed. It is useful for scenarios like expression evaluation, undo/redo operations or recursive algorithms.

• Push(item) : Adds an element to the top.
• Pop() : Removes and returns the top element.
• Peek() : Returns the top element without removing it.

• Use Stack<T> when you need to process elements in reverse order of insertion.

Queue<T> implements a First-In, First-Out (FIFO) collection. The first element enqueued (added) is the first one to be dequeued (removed). It’s ideal for scenarios like scheduling, buffering, breadth-first traversal, messaging systems or any workflow where order matters and you process items in the arrival sequence.

• Enqueue(T item) : adds an item to the back of the queue.
• Dequeue() : removes and returns the item from the front of the queue.
• Peek() : returns the front item without removing it.
• Count property : gives the number of elements

• Use Queue<T> when you need to process elements in the order they arrive.

LinkedList<T> stores items as nodes connected by links. Each node holds a Value plus references to both the previous and next node, making it a doubly‐linked list.

• Efficient insertions/removals anywhere : You can insert or remove nodes in constant time O(1) when you already have a reference to the node.
• Slower for random access : There is no indexer (list[i]) for fast direct access. To get the n-th element, traversal from a starting node must occur, costing O(n).
• Count is O(1) : The Count property is maintained internally and returns in constant time.
• Node structure : Each item is wrapped in a LinkedListNode<T> which links to Previous and Next nodes.
• Memory overhead : Because each node stores two pointers (prev, next), a LinkedList<T> typically has more memory overhead compared to a List<T> of the same number of elements.

• Use LinkedList<T> when you frequently insert or remove elements in the middle of the collection.
• You do not need fast random indexing access.

HashSet<T> stores only unique elements. It uses hashing internally to provide very fast lookups, making it ideal for membership checks, deduplication and set operations.

• No duplicates allowed : Attempting to add an element that’s already present returns false and does not change the set.
• Unordered collection : It does not preserve insertion order. The internal ordering is based on hashing.
• Average O(1) for Add, Remove, Contains : These operations usually run in constant time, making HashSet<T> very efficient for lookups.
• Mathematical set operations built-in : Methods like UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith and others are supported
• Capacity auto-scaling : The internal structure expands automatically as more elements are added

• Use HashSet<T> when you want to store unique items and perform fast lookups.
• You don’t care about ordering or indexing of items.

SortedSet<T> is a collection that stores unique elements in a sorted order. It is implemented using a balanced binary search tree (red-black tree), which provides efficient insertion, deletion and search operations. This class is part of the System.Collections.Generic namespace and implements the ISet<T> interface.

• Unique and Sorted: Automatically stores elements without duplicates in sorted order.
• Set Operations: Supports mathematical operations such as UnionWith, IntersectWith and ExceptWith.
• Optimal Performance: Add(), Remove() and Contains() operations have O(log n) time complexity, where n is the number of elements in the set.
• Custom Sorting: Allows specifying a custom comparer to define the sorting order.
• Efficient Range Queries: Provides methods like GetViewBetween() to efficiently retrieve subsets of elements within a specified range.

• You need a collection that maintains elements in a sorted order.
• You require uniqueness of elements without duplicates.
• You want to perform efficient set operations like union, intersection and difference.
• You need to efficiently retrieve subsets of elements within a specified range.

Dictionary<TKey, TValue> is a generic collection in C# that stores data as key-value pairs. It utilizes hashing to provide fast lookups, making it ideal for scenarios where quick data retrieval is essential.

• Unique Keys: Each key must be unique within the dictionary. Attempting to add a duplicate key will throw an ArgumentException.
• Value Types: Values can be of any type and can be duplicated. Only keys are required to be unique.
• Fast Lookups: Operations like Add(), Remove() and ContainsKey() have an average time complexity of O(1), thanks to the underlying hash table implementation.
• Safe Retrieval: Use TryGetValue() to safely retrieve values without throwing exceptions if the key doesn't exist.
• Enumerator Support: Supports enumeration over key-value pairs, allowing iteration through the dictionary.

• You need to store data with a unique identifier (key) and associated value.
• Fast retrieval, insertion and deletion operations are required.
• You need to perform operations like checking for the existence of a key or removing key-value pairs efficiently.

SortedDictionary<TKey, TValue> is a generic collection in C# that stores key-value pairs in sorted order based on the keys. It is implemented using a balanced binary search tree (red-black tree), which ensures that operations like insertion, deletion and lookup are efficient.

• Sorted Order : Elements are automatically sorted by key in ascending order. You can specify a custom comparer to define the sorting order.
• Unique Keys : Each key must be unique within the dictionary. Attempting to add a duplicate key will throw an ArgumentException.
• Fast Operations: Operations like Add(), Remove() and ContainsKey() have an average time complexity of O(log n), thanks to the underlying red-black tree implementation.
• Enumerator Support : Supports enumeration over key-value pairs, allowing iteration through the dictionary in sorted order.
• Capacity Auto-Scaling : The internal structure expands automatically as more elements are added.

• You need a collection that maintains elements in a sorted order based on the keys.
• Fast retrieval, insertion and deletion operations are required.
• You need to perform operations like checking for the existence of a key or removing key-value pairs efficiently.

SortedList<TKey, TValue> is a generic collection in C# that stores key-value pairs in sorted order based on the keys. Unlike SortedDictionary<TKey, TValue>, it allows index-based access to elements, providing efficient retrieval by both key and index.

• Sorted Order : Elements are automatically sorted by key in ascending order. You can specify a custom comparer to define the sorting order.
• Unique Keys : Each key must be unique within the list. Attempting to add a duplicate key will throw an ArgumentException.
• Efficient Index Access : Provides fast access to elements by index, similar to a list. This is not available in SortedDictionary<TKey, TValue>
• Memory Efficiency : Uses less memory compared to SortedDictionary<TKey, TValue>, making it suitable for scenarios with limited memory resources.
• Slower Insertions : Insertion and removal operations are slower compared to SortedDictionary<TKey, TValue> due to the need to maintain sorted order.

• You need a collection that maintains elements in a sorted order based on the keys.
• When you need a sorted dictionary with index-based access.
• Insertion and removal operations are infrequent or can tolerate slower performance.