Data Structures and Algorithms in C#

# CHAPTER 29

Data Structures and Algorithms in C# #

1. Introduction #

2. Learning Objectives #

• Understand Big O Notation.

• Implement a custom Linked List.

• Understand how a Binary Search Algorithm works.

• Understand basic Sorting Algorithms (Bubble Sort).

3. Big O Notation (Time Complexity) #

• O(1) - Constant Time: Excellent. The time does not change regardless of data size. (e.g., Looking up a value in a Dictionary).

• O(N) - Linear Time: Fair. The time increases linearly with the data. (e.g., A foreach loop iterating through a List).

• O(N^2) - Quadratic Time: Terrible. The time skyrockets as data grows. (e.g., A loop nested inside another loop).

4. Custom Data Structure: Linked List #

Advantage: Inserting an item at the beginning of a Linked List is O(1) (instant). Doing that in a List<T> requires shifting every other item down, which is O(N).

using System;

// 1. The Node Class
class Node
{
    public int Data;
    public Node Next; // Points to the next node in the chain
    
    public Node(int data) { Data = data; }
}

// 2. The LinkedList Class
class MyLinkedList
{
    public Node Head;

    public void AddFirst(int data)
    {
        Node newNode = new Node(data);
        newNode.Next = Head; // New node points to the old head
        Head = newNode;      // New node becomes the new head
    }

    public void PrintAll()
    {
        Node current = Head;
        while (current != null)
        {
            Console.Write(current.Data + " -> ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }
}

class Program
{
    static void Main()
    {
        MyLinkedList list = new MyLinkedList();
        list.AddFirst(3);
        list.AddFirst(2);
        list.AddFirst(1);
        list.PrintAll(); // Output: 1 -> 2 -> 3 -> null
    }
}

*(Note: C# provides a built-in LinkedList<T>, but building one is a classic interview question).*

5. Algorithm: Binary Search #

This is Binary Search. It finds an item in a sorted array in O(log N) time (extremely fast).

static int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

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

        if (arr[mid] == target) 
            return mid; // Found it!

        if (arr[mid] < target) 
            left = mid + 1; // Discard left half
        else 
            right = mid - 1; // Discard right half
    }
    return -1; // Not found
}

6. Algorithm: Bubble Sort #

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

7. Built-in C# Sorting and Searching #

int[] numbers = { 5, 2, 8, 1, 9 };

// Sorts the array in-place (Uses Quicksort/Introsort O(N log N))
Array.Sort(numbers); 

// Uses Binary Search (Array MUST be sorted first!)
int index = Array.BinarySearch(numbers, 8); 

8. Common Mistakes #

• Running Binary Search on an Unsorted Array: Binary Search logic fundamentally relies on the array being sorted in ascending order. If you run it on an unsorted array, it will fail unpredictably.

• Using Nested Loops unnecessarily: If you write a loop inside a loop, you have created an O(N^2) algorithm. If N is 10,000, your code will execute 100,000,000 times! Always look for ways to optimize using Dictionaries.

9. Best Practices #

• Prefer Dictionary<TKey, TValue> for lookups when you have a unique Key, as its O(1) time complexity is unbeatable.

10. Exercises #

1. 1. Hand-write the Binary Search algorithm on paper.

1. 2. Given an array { 10, 20, 30, 40, 50 }, trace the steps of Binary Search if looking for the number 40.

11. MCQs with Answers #

12. Interview Questions #

• Q: What is the difference in memory layout between an Array and a Linked List?

• Q: Explain O(log N) time complexity. Give an example.

• Q: Why is Bubble Sort considered highly inefficient for large datasets?

13. Summary #

14. Next Chapter Recommendation #