Data Structures & Algorithms (DSA)

Data Structures and Algorithms (DSA) form the backbone of programming and efficient problem-solving. This tutorial will guide you through the most essential data structures and algorithms using C#.

1. Understanding Data Structures

1.1 What Are Data Structures?

Data structures are ways of organizing and storing data to perform operations efficiently. Common types include:

• Arrays
• Lists
• Stacks
• Queues
• Trees
• Graphs
• Hash Tables

2. Arrays

Definition

Arrays are fixed-size, contiguous memory collections of elements of the same type.

Code Example

using System;

class Program
{
    static void Main()
    {
        int[] numbers = { 1, 2, 3, 4, 5 };
        Console.WriteLine("Array Elements:");
        foreach (var num in numbers)
        {
            Console.WriteLine(num);
        }
    }
}

3. Lists

Definition

Lists are dynamic arrays that can grow or shrink in size.

Code Example

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> numbers = new List<int> { 10, 20, 30 };
        numbers.Add(40); // Add an element
        numbers.Remove(20); // Remove an element

        Console.WriteLine("List Elements:");
        foreach (var num in numbers)
        {
            Console.WriteLine(num);
        }
    }
}

4. Stack

Definition

A stack follows the LIFO (Last In, First Out) principle.

Code Example

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(10);
        stack.Push(20);
        stack.Push(30);

        Console.WriteLine("Stack Elements:");
        while (stack.Count > 0)
        {
            Console.WriteLine(stack.Pop());
        }
    }
}

5. Queue

Definition

A queue follows the FIFO (First In, First Out) principle.

Code Example

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Queue<string> queue = new Queue<string>();
        queue.Enqueue("Alice");
        queue.Enqueue("Bob");
        queue.Enqueue("Charlie");

        Console.WriteLine("Queue Elements:");
        while (queue.Count > 0)
        {
            Console.WriteLine(queue.Dequeue());
        }
    }
}

---

6. Binary Trees

Definition

A tree is a hierarchical data structure consisting of nodes. Each node has:

• Data
• Left Child
• Right Child

Code Example

using System;

class Node
{
    public int Data;
    public Node Left, Right;

    public Node(int data)
    {
        Data = data;
        Left = Right = null;
    }
}

class BinaryTree
{
    public Node Root;

    public void InOrderTraversal(Node node)
    {
        if (node == null) return;
        InOrderTraversal(node.Left);
        Console.WriteLine(node.Data);
        InOrderTraversal(node.Right);
    }
}

class Program
{
    static void Main()
    {
        BinaryTree tree = new BinaryTree();
        tree.Root = new Node(1);
        tree.Root.Left = new Node(2);
        tree.Root.Right = new Node(3);
        tree.Root.Left.Left = new Node(4);
        tree.Root.Left.Right = new Node(5);

        Console.WriteLine("InOrder Traversal:");
        tree.InOrderTraversal(tree.Root);
    }
}

7. Graphs

Definition

Graphs consist of nodes (vertices) and edges. They can be:

• Directed or Undirected
• Weighted or Unweighted

Code Example

using System;
using System.Collections.Generic;

class Graph
{
    private Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();

    public void AddEdge(int source, int destination)
    {
        if (!adjList.ContainsKey(source))
            adjList[source] = new List<int>();
        adjList[source].Add(destination);
    }

    public void PrintGraph()
    {
        foreach (var vertex in adjList)
        {
            Console.Write($"{vertex.Key}: ");
            foreach (var neighbor in vertex.Value)
            {
                Console.Write($"{neighbor} ");
            }
            Console.WriteLine();
        }
    }
}

class Program
{
    static void Main()
    {
        Graph graph = new Graph();
        graph.AddEdge(1, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 4);

        Console.WriteLine("Graph Adjacency List:");
        graph.PrintGraph();
    }
}

8. Sorting Algorithms

Bubble Sort

using System;

class Program
{
    static void BubbleSort(int[] array)
    {
        int n = array.Length;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (array[j] > array[j + 1])
                {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    static void Main()
    {
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };
        BubbleSort(array);

        Console.WriteLine("Sorted Array:");
        Console.WriteLine(string.Join(", ", array));
    }
}

9. Searching Algorithms

Binary Search

using System;

class Program
{
    static int BinarySearch(int[] array, int key)
    {
        int left = 0, right = array.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (array[mid] == key) return mid;
            if (array[mid] < key) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    static void Main()
    {
        int[] array = { 2, 3, 4, 10, 40 };
        int key = 10;

        int result = BinarySearch(array, key);
        if (result != -1)
            Console.WriteLine($"Element found at index {result}");
        else
            Console.WriteLine("Element not found");
    }
}

Conclusion

This tutorial covers foundational data structures and algorithms in C#. Understanding these concepts will enhance your problem-solving skills and prepare you for advanced topics like dynamic programming and graph algorithms