Data Structures in C#

Here are ten commonly used data structures in C#:

1. Arrays:
   Arrays are the simplest form of data structures in C#. They are a fixed-size collection of elements of the same data type, accessed by their index. Arrays provide fast random access but have a fixed size.
2. Lists:
   Lists are dynamic arrays in C# that automatically resize as needed. They are part of the System.Collections.Generic namespace and provide easy insertion and removal of elements.
3. Dictionaries:
   Dictionaries, represented by Dictionary<TKey, TValue>, are key-value pairs that provide fast lookup based on keys. They are useful for storing and retrieving data based on unique identifiers.
4. Stacks:
   Stacks are a Last-In, First-Out (LIFO) data structure. You can use the Stack<T> class to push and pop elements from the top of the stack.
5. Queues:
   Queues are a First-In, First-Out (FIFO) data structure. You can use the Queue<T> class to enqueue elements to the back and dequeue from the front.
6. LinkedLists:
   Linked lists are collections of nodes, where each node contains a value and a reference to the next node. They provide efficient insertion and removal of elements in the middle of the list.
7. HashSet:
   A HashSet<T> is an unordered collection of unique elements. It’s useful for quickly checking for the existence of an element and ensuring uniqueness.
8. SortedSet:
   A SortedSet<T> is similar to a HashSet, but it maintains elements in sorted order. It provides efficient operations for finding minimum and maximum values.
9. Stack-based Collections:
   C# provides several stack-based collections like Stack<T>, Queue<T>, and ConcurrentStack<T> for thread-safe stack operations.
10. Tree Structures:
    C# does not provide built-in tree structures, but you can implement binary trees, AVL trees, or other tree-based structures using custom classes.

These are some of the commonly used data structures in C#.

Depending on the application and requirements, may also be encountered other specialized data structures such as heaps, graphs, and hash tables that are not part of the standard C# libraries but can be implemented or found in third-party libraries.

The choice of data structure depends on the specific use case and the performance characteristics needed for the application.

Heaps

In C#, heaps are often implemented as priority queues using data structures like binary heaps. Priority queues are useful for managing elements with priorities, and they ensure that the element with the highest (or lowest) priority is always at the top of the queue. Here’s an example of how to use a binary heap (min-heap) in C#:

using System;
using System.Collections.Generic;

class MinHeap<T> where T : IComparable<T>
{
    private List<T> heap = new List<T>();

    public int Count => heap.Count;

    public void Add(T item)
    {
        heap.Add(item);
        int currentIndex = Count - 1;
        while (currentIndex > 0)
        {
            int parentIndex = (currentIndex - 1) / 2;
            if (heap[currentIndex].CompareTo(heap[parentIndex]) >= 0)
                break;

            // Swap the current element with its parent
            T temp = heap[currentIndex];
            heap[currentIndex] = heap[parentIndex];
            heap[parentIndex] = temp;

            currentIndex = parentIndex;
        }
    }

    public T ExtractMin()
    {
        if (Count == 0)
            throw new InvalidOperationException("Heap is empty.");

        T min = heap[0];
        int lastIndex = Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
        lastIndex--;

        int currentIndex = 0;
        while (true)
        {
            int leftChildIndex = 2 * currentIndex + 1;
            int rightChildIndex = 2 * currentIndex + 2;
            int smallestChildIndex = -1;

            if (leftChildIndex <= lastIndex)
                smallestChildIndex = leftChildIndex;

            if (rightChildIndex <= lastIndex && heap[rightChildIndex].CompareTo(heap[leftChildIndex]) < 0)
                smallestChildIndex = rightChildIndex;

            if (smallestChildIndex == -1 || heap[currentIndex].CompareTo(heap[smallestChildIndex]) <= 0)
                break;

            // Swap the current element with its smallest child
            T temp = heap[currentIndex];
            heap[currentIndex] = heap[smallestChildIndex];
            heap[smallestChildIndex] = temp;

            currentIndex = smallestChildIndex;
        }

        return min;
    }
}

class Program
{
    static void Main()
    {
        MinHeap<int> minHeap = new MinHeap<int>();

        minHeap.Add(4);
        minHeap.Add(2);
        minHeap.Add(8);
        minHeap.Add(1);
        minHeap.Add(9);

        Console.WriteLine("Extracted Min: " + minHeap.ExtractMin()); // 1
        Console.WriteLine("Extracted Min: " + minHeap.ExtractMin()); // 2
    }
}

In this example, we define a MinHeap<T> class that represents a min-heap, where T is a type that implements IComparable<T>. The class provides methods to add elements to the heap (Add) and extract the minimum element (ExtractMin). The MinHeap ensures that the minimum element is always at the root of the heap.

Graphs in c#

Working with graphs in C# often involves creating custom classes to represent the graph and its components. Here’s an example of how to create a simple directed graph and perform basic operations like adding vertices and edges, as well as traversing the graph using Depth-First Search (DFS):

using System;
using System.Collections.Generic;

class Graph<T>
{
    private Dictionary<T, List<T>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<T, List<T>>();
    }

    public void AddVertex(T vertex)
    {
        if (!adjacencyList.ContainsKey(vertex))
            adjacencyList[vertex] = new List<T>();
    }

    public void AddEdge(T from, T to)
    {
        if (!adjacencyList.ContainsKey(from))
            throw new ArgumentException("Vertex 'from' does not exist in the graph.");

        if (!adjacencyList.ContainsKey(to))
            throw new ArgumentException("Vertex 'to' does not exist in the graph.");

        adjacencyList[from].Add(to);
    }

    public void DepthFirstSearch(T startVertex)
    {
        HashSet<T> visited = new HashSet<T>();
        DFS(startVertex, visited);
    }

    private void DFS(T vertex, HashSet<T> visited)
    {
        if (!visited.Contains(vertex))
        {
            Console.WriteLine(vertex);
            visited.Add(vertex);

            if (adjacencyList.ContainsKey(vertex))
            {
                foreach (T neighbor in adjacencyList[vertex])
                {
                    DFS(neighbor, visited);
                }
            }
        }
    }
}

class Program
{
    static void Main()
    {
        Graph<string> graph = new Graph<string>();

        graph.AddVertex("A");
        graph.AddVertex("B");
        graph.AddVertex("C");
        graph.AddVertex("D");

        graph.AddEdge("A", "B");
        graph.AddEdge("A", "C");
        graph.AddEdge("B", "D");
        graph.AddEdge("C", "D");

        Console.WriteLine("Depth-First Search (DFS) starting from 'A':");
        graph.DepthFirstSearch("A");
    }
}

In this example:

1. We create a Graph<T> class that uses a dictionary to represent the adjacency list for the graph. Each vertex is a key in the dictionary, and its associated value is a list of neighboring vertices.
2. The AddVertex method allows us to add vertices to the graph, and the AddEdge method allows us to add directed edges between vertices.
3. The DepthFirstSearch method implements Depth-First Search (DFS) to traverse the graph starting from a given vertex. It prints the vertices in the order they are visited.
4. In the Main method, we create a graph with vertices “A,” “B,” “C,” and “D” and add edges between them. Then, we perform DFS starting from vertex “A” to explore the graph.

When you run this program, it will perform a DFS traversal starting from vertex “A” and print the vertices in the order they are visited:

Depth-First Search (DFS) starting from 'A':
A
B
D
C

Hash Tables

In C#, hash tables are commonly implemented using the Dictionary<TKey, TValue> class, which is part of the System.Collections.Generic namespace. Here’s an example of how to use a hash table (dictionary) in C#:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Create a dictionary (hash table) with string keys and int values
        Dictionary<string, int> scores = new Dictionary<string, int>();

        // Add key-value pairs to the dictionary
        scores["Alice"] = 85;
        scores["Bob"] = 92;
        scores["Charlie"] = 78;
        scores["David"] = 95;

        // Access values using keys
        Console.WriteLine("Alice's score: " + scores["Alice"]); // Output: 85

        // Check if a key exists in the dictionary
        if (scores.ContainsKey("Bob"))
        {
            Console.WriteLine("Bob's score: " + scores["Bob"]); // Output: 92
        }

        // Remove a key-value pair from the dictionary
        scores.Remove("Charlie");

        // Iterate through the dictionary
        foreach (var kvp in scores)
        {
            Console.WriteLine($"Name: {kvp.Key}, Score: {kvp.Value}");
        }
    }
}

In this example:

1. We create a dictionary scores with string keys (representing names) and int values (representing scores).
2. We add key-value pairs to the dictionary using the [] indexer notation.
3. We access values in the dictionary using keys. If a key is not found, an exception is thrown, so you should use ContainsKey to check if a key exists before accessing it.
4. We remove a key-value pair from the dictionary using the Remove method.
5. We iterate through the dictionary using a foreach loop, which allows us to access each key-value pair as a KeyValuePair<TKey, TValue>.

When you run this program, it will produce output similar to the following:

Alice's score: 85
Bob's score: 92
Name: Alice, Score: 85
Name: Bob, Score: 92
Name: David, Score: 95

This example demonstrates how to create, populate, access, and manipulate a hash table (dictionary) in C#. Hash tables are widely used for efficient key-value data storage and retrieval.