# Standard Data Structures in C# (.NET) with Examples

A complete reference of all standard and commonly used data structures in C#, with short explanations and examples.  
Ideal for university courses on Algorithms and Data Structures.

---

## 📘 Table of Contents

1. [Arrays](#1-arrays)
2. [List](#2-listt)
3. [LinkedList](#3-linkedlistt)
4. [Queue](#4-queuet)
5. [Stack](#5-stackt)
6. [Dictionary](#6-dictionarytkey-tvalue)
7. [HashSet](#7-hashsett)
8. [SortedList](#8-sortedlisttkey-tvalue)
9. [SortedDictionary](#9-sorteddictionarytkey-tvalue)
10. [SortedSet](#10-sortedsett)
11. [Custom Tree Example](#11-custom-tree-example)
12. [Graph (Adjacency List)](#12-graph-adjacency-list)
13. [Tuple / ValueTuple](#13-tuple--valuetuple)
14. [ArrayList (Legacy)](#14-arraylist-legacy)
15. [ObservableCollection](#15-observablecollectiont)
16. [BitArray](#16-bitarray)
17. [Immutable Collections](#17-immutable-collections)
18. [Summary Table](#18-summary-table)

---

## 1. Arrays

**Fixed-size**, indexed collection of elements of the same type.  
**Complexity:** Access O(1), Search O(n)

```csharp
int[] numbers = { 10, 20, 30 };
Console.WriteLine(numbers[1]); // Output: 20
```

---

## 2. List<T>

Dynamic array that resizes automatically.  
**Complexity:** Add O(1) amortized, Access O(1), Search O(n)

```csharp
List<string> names = new List<string> { "Alice", "Bob" };
names.Add("Charlie");
Console.WriteLine(names[2]); // Output: Charlie
```

---

## 3. LinkedList<T>

Doubly linked list — fast insertion/removal at both ends.  
**Complexity:** Insert O(1), Search O(n)

```csharp
LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.AddFirst(0);
foreach (int i in list) Console.WriteLine(i);
```

---

## 4. Queue<T>

FIFO (First-In, First-Out) structure.  
**Complexity:** Enqueue/Dequeue O(1)

```csharp
Queue<string> queue = new Queue<string>();
queue.Enqueue("first");
queue.Enqueue("second");
Console.WriteLine(queue.Dequeue()); // Output: first
```

---

## 5. Stack<T>

LIFO (Last-In, First-Out) structure.  
**Complexity:** Push/Pop O(1)

```csharp
Stack<int> stack = new Stack<int>();
stack.Push(10);
stack.Push(20);
Console.WriteLine(stack.Pop()); // Output: 20
```

---

## 6. Dictionary<TKey, TValue>

Hash table — fast key-value lookup.  
**Complexity:** Average O(1)

```csharp
Dictionary<string, int> ages = new Dictionary<string, int>
{
    ["Alice"] = 25,
    ["Bob"] = 30
};
Console.WriteLine(ages["Bob"]); // Output: 30
```

---

## 7. HashSet<T>

Unordered collection of **unique** elements.  
**Complexity:** Add/Contains O(1) average

```csharp
HashSet<int> numbers = new HashSet<int> { 1, 2, 3 };
numbers.Add(3); // Ignored (duplicate)
Console.WriteLine(numbers.Count); // Output: 3
```

---

## 8. SortedList<TKey, TValue>

Stores key-value pairs sorted by key.  
Uses less memory than `SortedDictionary`, slower insertions.  
**Complexity:** O(log n) access

```csharp
SortedList<string, int> sl = new SortedList<string, int>();
sl["Banana"] = 2;
sl["Apple"] = 5;
foreach (var item in sl)
    Console.WriteLine($"{item.Key}: {item.Value}");
```

---

## 9. SortedDictionary<TKey, TValue>

Balanced binary search tree — sorted by key.  
Better for frequent updates.  
**Complexity:** O(log n)

```csharp
SortedDictionary<string, int> sd = new SortedDictionary<string, int>();
sd.Add("b", 2);
sd.Add("a", 1);
foreach (var pair in sd)
    Console.WriteLine($"{pair.Key}: {pair.Value}");
```

---

## 10. SortedSet<T>

Keeps elements in **sorted order**, no duplicates.  
**Complexity:** O(log n)

```csharp
SortedSet<int> ss = new SortedSet<int> { 5, 1, 3 };
foreach (var n in ss)
    Console.WriteLine(n); // 1, 3, 5
```

---

## 11. Custom Tree Example

Binary Search Tree (BST) example.

```csharp
class Node
{
    public int Value;
    public Node? Left, Right;
    public Node(int value) => Value = value;
}

class BinaryTree
{
    public Node? Root;
    public void Insert(int value)
    {
        Root = InsertRec(Root, value);
    }
    private Node InsertRec(Node? root, int value)
    {
        if (root == null) return new Node(value);
        if (value < root.Value) root.Left = InsertRec(root.Left, value);
        else if (value > root.Value) root.Right = InsertRec(root.Right, value);
        return root;
    }
}
```

---

## 12. Graph (Adjacency List)

Implemented using a dictionary of lists.

```csharp
class Graph
{
    private Dictionary<int, List<int>> adj = new();
    public void AddEdge(int u, int v)
    {
        if (!adj.ContainsKey(u)) adj[u] = new List<int>();
        adj[u].Add(v);
    }
    public void Print()
    {
        foreach (var kvp in adj)
            Console.WriteLine($"{kvp.Key}: {string.Join(",", kvp.Value)}");
    }
}
```

---

## 13. Tuple / ValueTuple

Lightweight structure for grouping multiple values.

```csharp
var person = (Name: "Alice", Age: 25);
Console.WriteLine($"{person.Name} is {person.Age}");
```

---

## 14. ArrayList (Legacy)

Older, non-generic version of `List<T>` (avoid in new code).

```csharp
ArrayList arr = new ArrayList { 1, "text", 3.14 };
foreach (var x in arr) Console.WriteLine(x);
```

---

## 15. ObservableCollection<T>

Collection that notifies listeners about changes.  
Used in WPF and MVVM.  
**Complexity:** O(1) add/remove

```csharp
ObservableCollection<string> oc = new ObservableCollection<string>();
oc.CollectionChanged += (s, e) => Console.WriteLine("Changed!");
oc.Add("Test");
```

---

## 16. BitArray

Efficient storage for bits (true/false values).  
**Complexity:** O(n)

```csharp
BitArray bits = new BitArray(5);
bits.Set(1, true);
bits.Set(3, true);
for (int i = 0; i < bits.Length; i++)
    Console.Write(bits[i] ? 1 : 0); // 01010
```

---

## 17. Immutable Collections

Immutable versions of List, Dictionary, etc.  
**Namespace:** `System.Collections.Immutable`

```csharp
using System.Collections.Immutable;
var immutableList = ImmutableList.Create(1, 2, 3);
var newList = immutableList.Add(4);
Console.WriteLine(string.Join(",", newList)); // 1,2,3,4
```

---

## 18. Summary Table

| Category | Type | Description | Ordered | Unique | Mutable | Complexity (Access) |
|-----------|------|-------------|----------|---------|----------|---------------------|
| Array | `int[]` | Fixed-size indexed collection | ✅ | ❌ | ❌ | O(1) |
| List | `List<T>` | Resizable array | ✅ | ❌ | ✅ | O(1) |
| Linked List | `LinkedList<T>` | Doubly linked nodes | ✅ | ❌ | ✅ | O(n) |
| Queue | `Queue<T>` | FIFO structure | ✅ | ❌ | ✅ | O(1) |
| Stack | `Stack<T>` | LIFO structure | ✅ | ❌ | ✅ | O(1) |
| Dictionary | `Dictionary<TKey,TValue>` | Key-value lookup | ❌ | ✅ | ✅ | O(1) |
| HashSet | `HashSet<T>` | Unique unordered collection | ❌ | ✅ | ✅ | O(1) |
| SortedList | `SortedList<TKey,TValue>` | Sorted by key | ✅ | ✅ | ✅ | O(log n) |
| SortedDictionary | `SortedDictionary<TKey,TValue>` | BST map | ✅ | ✅ | ✅ | O(log n) |
| SortedSet | `SortedSet<T>` | Unique sorted set | ✅ | ✅ | ✅ | O(log n) |
| BitArray | `BitArray` | Efficient bit storage | ✅ | ❌ | ✅ | O(1) |
| Immutable | `ImmutableList<T>` etc. | Immutable data | ✅ | ❌ | ❌ | O(1) |

---

**Author:** Dr. Stoyan Cheresharov  
**University:** Plovdiv University “Paisii Hilendarski”  
**Course:** Algorithms and Data Structures in C# (.NET)

---