DSA in C# | Data Structure and Algorithm using C#:
Lecture 1: Introduction to Data Structures and Algorithms (1 Hour)
1.1 What are Data Structures?
Data Structures are ways to store and organize data so it can be used efficiently.
Think of data structures as containers that hold data in a specific format.
Types of Data Structures:
Primitive Data Structures: These are basic structures built into the language.
Example: int, float, char, bool in C#.
Example:
csharp
int age = 25; // 'age' stores an integer value.
bool isStudent = true; // 'isStudent' stores a boolean value.
Non-Primitive Data Structures: These are more complex and are built using primitive types.
They are divided into:
Linear: Arrays, Lists, Queues, Stacks (data is arranged in a sequence).
Non-Linear: Trees, Graphs (data is connected in more complex ways).
Example:
// Array is a simple linear data structure
int[] numbers = { 1, 2, 3, 4, 5 };
// Tree is a non-linear structure, will cover in later lectures.
Explanation:
A data structure helps to group and store data together. Imagine if you had to organize books
on a shelf. You can arrange them in many ways: by title, by author, or by genre
. Each method helps you find books faster, which is similar to how different data structures
help in organizing data for faster access or modification.
1.2 What are Algorithms?
An algorithm is a step-by-step process or set of instructions to solve a problem. It’s a recipe
that tells the computer how to process data.
Key Points:
Algorithms help in transforming input into output.
Every algorithm must have a defined beginning and end.
Time Complexity: Measures how the time to complete an algorithm increases with
the size of the input.
Example: Sorting a list of names.
Big-O Notation: Used to describe the efficiency of an algorithm (e.g., O(n), O(log n)).
Example: Simple algorithm to find the largest number in an array.
csharp
Copy code
int[] numbers = { 5, 3, 8, 6, 2 };
int max = numbers[0]; // Assume first number is largest
for (int i = 1; i < numbers.Length; i++)
{
if (numbers[i] > max)
{
max = numbers[i]; // Update max if larger number is found
}
}
Console.WriteLine("Largest number is: " + max);
Explanation: The above algorithm checks each number in the array and updates the largest number found.
This is an example of linear time complexity O(n) because it goes through each element once.
1.3 Why is DSA Important?
DSA is crucial because it allows us to handle data efficiently. In real-world applications like Google,
Amazon, or Netflix, handling large amounts of data quickly and efficiently is essential.
Importance of DSA:
Optimizes code performance.
Saves memory and processing time.
Helps in designing scalable systems.
Example: Imagine you are searching for a book in a library. Without any proper organization (data structure),
you’ll waste time. If the books are arranged alphabetically (efficient algorithm), you can find your book quickly.
1.4 Types of Data Structures: Primitive vs Non-Primitive (10 Minutes)
Primitive: Simple and store single values (like int, char).
Non-Primitive: Complex and store multiple values or relationships (like arrays, lists, trees).
Primitive Data Structure Example:
csharp
Copy code
int x = 10; // Integer (Primitive)
char letter = 'A'; // Character (Primitive)
Non-Primitive Data Structure Example:
csharp
Copy code
int[] numbers = { 10, 20, 30 }; // Array (Non-Primitive)
Explanation: Non-primitive structures help in handling more complex data scenarios. For example,
an array allows us to store multiple values of the same type together,
which makes it easier to process multiple items at once.
1.5 Example: Simple Addition Program in C#
Let’s finish the class with a simple program to show how data structures are used in practice.
Example: Adding two numbers.
csharp
Copy code
using System;
class Program
{
static void Main()
{
// Declare two integers
int num1 = 10;
int num2 = 20;
// Perform addition
int sum = num1 + num2;
// Output the result
Console.WriteLine("Sum is: " + sum);
}
}
Explanation:
This program uses two primitive data structures (int) and an arithmetic operation.
Console.WriteLine outputs the result to the screen.
This is a simple example to show how basic data is processed in C#.
1. Arrays as a Data Structure in C#
What is an Array?
An array is a linear data structure that stores a fixed-size sequential collection of elements of the same type. Arrays are one of the simplest
and most widely used data structures. They offer constant time (O(1)) access to elements via their index, but have limitations in terms of flexibility (fixed size).
Properties of Arrays:
Fixed Size: The size of an array is specified when it is created and cannot be changed
afterward. This means the memory allocation for the array is static.
Homogeneous Elements: All elements in an array must be of the same data type
(e.g., integers, strings).
Index-Based: Arrays allow fast random access to elements using indices (starting from 0).
Array Representation in Memory
The elements of an array are stored in contiguous memory locations.
This allows for fast access but can cause memory fragmentation if large
arrays are declared and not fully utilized.
Common Operations on Arrays:
1. Accessing an Element (O(1)):
You can access any element in an array by using its index, which provides fast O(1) time complexity.
csharp
Copy code
int[] numbers = {10, 20, 30, 40, 50};
int firstElement = numbers[0]; // Accessing the first element, Output: 10
2. Inserting an Element (O(n)):
Inserting an element into an array (especially in the middle) requires shifting elements,
making the time complexity O(n).
csharp
Copy code
int[] numbers = {10, 20, 30, 40};
numbers[2] = 25; // Modify the value at index 2.
3. Deleting an Element (O(n)):
Similar to insertion, removing an element from an array requires shifting all subsequent elements,
resulting in O(n) complexity.
csharp
Copy code
// In C#, arrays don't provide direct deletion, but you can shift elements manually.
int[] numbers = {10, 20, 30, 40};
numbers[2] = numbers[3]; // Copy the last element to overwrite the one being deleted.
4. Traversing an Array (O(n)):
To go through all elements of an array, you would use a for or foreach loop. This operation takes O(n) time.
csharp
Copy code
foreach (int number in numbers)
{
Console.WriteLine(number); // Output each number.
}
Limitations of Arrays:
Fixed Size: Arrays have a fixed size, and you cannot change their size once they are created. This can lead to wasted memory if the array is not fully utilized or memory overflow if more elements need to be added.
Costly Insertion and Deletion: Inserting or deleting elements in arrays requires shifting elements, which is inefficient and time-consuming for large datasets.
Contiguous Memory Requirement: Arrays must be stored in contiguous memory locations, which can lead to fragmentation and issues with memory allocation, especially in large arrays.
2. Collections in C#
Unlike arrays, collections in C# provide more flexibility in handling groups of objects. They allow dynamic memory allocation and offer additional features such as type safety with generics, easy insertion and deletion, and built-in methods for common operations.
Types of Collections in C#:
C# provides a wide variety of collections that allow dynamic memory management and offer
efficient ways to store, access, and manipulate data. These collections are part of the System.Collections and System.Collections.Generic namespaces.
KType of Collection Objects in C#:- 1) Generic Collection:- List Dictionary SortedList HashSet Stack Queue 2)Non Generic Collection:- ArrayList Hashtable SortedList Stack Queue What is ArrayList? ArrayList stores objects of any type like an array. However, there is no need to specify the size of the ArrayList like with an array as it grows automatically. class CollectionExample { static void Main() { ArrayList obj = new ArrayList(); obj.Add(1001); obj.Add("C"); obj.Add("CPP"); obj.Add(12.34F); obj.Remove(1001); foreach (Object o in obj) { Console.WriteLine(o); } Console.ReadKey(); } } List:-
a List is a collection that stores elements of the same type in a dynamic array-like structure. It is part of the System.Collections.Generic namespace, which provides a more type-safe, flexible, and efficient alternative to traditional arrays.
Here’s a deeper dive into List<T> in C#:
students.Add(new Student(2, "stu2", 34, 24000));
students.Add(new Student(3, "stu3", 54, 24000));
students.Add(new Student(4, "stu4", 34, 84000));
foreach (var student in students)
{
student.Display();
}
SortedList SortedList stores key and value pairs. It automatically arranges elements in ascending order of key by default. C# includes both, generic and non-generic SortedList collection. Example: SortedList obj = new SortedList();
obj.Add("D", 101);
obj.Add("B","CPP");
obj.Add("A",1);
obj.Add("C",true);
foreach (DictionaryEntry o in obj) { Console.WriteLine(o.Key+ " " + o.Value);
}
Stack
Stack stores the values in LIFO style (Last In First Out). It provides a Push() method to add a value and Pop() & Peek() methods to retrieve values. C# includes both, generic and nongeneric Stack.
Example:
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
stack.Push(4);
stack.Push(5);
while(stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}
Queue
Queue stores the values in FIFO style (First In First Out). It keeps the order in which the values were added. It provides an Enqueue() method to add values and a Dequeue() method to retrieve values from the collection. C# includes generic and non-generic Queue.
Example:
Queue<int> q = new Queue<int>();
q.Enqueue(1);
q.Enqueue(2);
q.Enqueue(3);
q.Enqueue(4);
q.Enqueue(5);
while (q.Count > 0)
{
Console.WriteLine(q.Dequeue());
}
Hashtable
Hashtable stores key and value pairs. It retrieves the values by comparing the hash value of the keys. BitArray BitArray manages a compact array of bit values, which are represented as Booleans, where true indicates that the bit is on (1) and false indicates the bit is off (0).
Example:
Hashtable obj = new Hashtable();
obj.Add("D", 101);
obj.Add("B","CPP");
obj.Add("A",1);
obj.Add("C",true);
foreach (DictionaryEntry o in obj)
{
Console.WriteLine(o.Key+ " " + o.Value);
}
Dictionary:-
a Dictionary is a collection that stores key-value pairs. It is part of the System.Collections.Generic namespace and provides an efficient way to look up, add, and manage data using keys, making it ideal when you need to map unique keys to corresponding values.
Key Characteristics of Dictionary in C#
Key-Value Pairs:
Each entry in a dictionary consists of a key and a value.
Example: A key could be a student’s roll number, and the value could be the student’s name.Unique Keys:
Each key must be unique. However, values can be duplicated.Fast Lookups:
Since it uses hashing internally, accessing elements by key is very efficient.Type-Safe:
Dictionary<TKey, TValue>is generic, meaning both key and value types must be specified, ensuring type safety.
Example:
Dictionary<String, Int32> obj1 = new Dictionary<String,Int32>(); obj1.Add("A", 101); obj1.Add("D", 455); obj1.Add("B", 201); obj1.Add("C", 301); foreach (KeyValuePair<String,Int32> o in obj1) { Console.WriteLine(o.Key + " " + o.Value); } HashSet:-
HashSet<T> is a collection of unique elements, optimized for fast lookups, additions, and deletions. It belongs to the System.Collections.Generic namespace and is implemented using hashing for high-performance operations. It is ideal when you need to store unique elements only and don’t care about the order of items.
Example:
HashSet<string> st = new HashSet<string>(); st.Add("a"); st.Add("b"); st.Add("c"); st.Add("b"); st.Add("b"); st.Add("d"); st.Add("e"); st.Remove("a"); foreach (var item in st) { Console.WriteLine(item); }
LinkedList:
a LinkedList<T> is a linear data structure consisting of nodes that are connected to each other by pointers. Each node contains two parts:
- Data – The value stored in the node.
- Reference (Pointer) – A link to the next and/or previous node.
Unlike arrays or lists, elements in a LinkedList are not stored contiguously in memory, making insertion and deletion operations efficient.
Key Characteristics of LinkedList in C#
Doubly Linked List:
C#'sLinkedList<T>is a doubly linked list, meaning each node has a reference to both its previous and next nodes.Dynamic Size:
The size of aLinkedListgrows or shrinks dynamically as elements are added or removed.Efficient Insertions/Deletions:
Adding or removing elements from the beginning, end, or middle is fast (O(1)) compared to aList, where shifting elements is required.No Indexing Support:
Unlike arrays or lists,LinkedListdoes not support direct access to elements using an index.
LinkedList<string> cities = new LinkedList<string>(); // Add elements cities.AddLast("New York"); cities.AddLast("London"); cities.AddFirst("Tokyo"); // Insert at the beginning // Remove an element cities.Remove("London"); // Display elements foreach (var city in cities) { Console.WriteLine(city); }
Example with AddBefore and AddAfter:
Comparison Between Arrays and Collections
Understanding and Implementing Searching and Sorting Algorithms in C#
In this article, we'll explore the fundamental concepts of searching and sorting algorithms using C#. We'll cover linear search, binary search, bubble sort, selection sort, and quick sort. Let's dive into the definition, algorithm, and implementation for each.
Searching Algorithms
Linear Search
Definition: Linear search is the simplest search algorithm. It sequentially checks each element in the data structure until the target element is found or the end of the list is reached.
Algorithm:
Start from the first element.
Compare each element with the target.
If the target is found, return the index.
If the target is not found, return -1.
C# Implementation:
int LinearSearch(int[] array, int key)
{
for (int i = 0; i < array.Length; i++)
{
if (array[i] == key)
return i;
}
return -1; // Element not found
}
Binary Search
Definition: Binary search is an efficient algorithm that works on sorted arrays by repeatedly dividing the search interval in half.
Algorithm:
Start with the middle element of the array.
If the target is equal to the middle element, return the index.
If the target is smaller, repeat the process for the left half.
If the target is larger, repeat the process for the right half.
C# Implementation:
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; // Element not found
}
Sorting Algorithms
Bubble Sort
Definition: Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Algorithm:
Repeatedly traverse the list.
Compare each pair of adjacent elements.
Swap them if they are in the wrong order.
Repeat until the list is sorted.
C# Implementation:
void BubbleSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
for (int j = 0; j < array.Length - i - 1; j++)
{
if (array[j] > array[j + 1])
{
// Swap array[j] and array[j + 1]
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
class BubbleSortDemo
{
static void Main()
{
int[] array = { 64, 34, 25, 12, 22, 11, 90 };
BubbleSort(array);
Console.WriteLine("Sorted array:");
foreach (var item in array)
{
Console.Write(item + " ");
}
}
}
Selection Sort
Definition: Selection sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.
Algorithm:
Repeatedly find the minimum element (considering ascending order) from the unsorted part.
Swap it with the first element of the unsorted part.
Move the boundary of the sorted part one position to the right.
Repeat until the array is sorted.
C# Implementation:
void SelectionSort(int[] array)
{
int n = array.Length;
for (int i = 0; i < n - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < n; j++)
{
if (array[j] < array[minIndex])
{
minIndex = j;
}
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
class SelectionSortDemo
{
static void Main()
{
int[] array = { 64, 25, 12, 22, 11 };
SelectionSort(array);
Console.WriteLine("Sorted array:");
foreach (var item in array)
{
Console.Write(item + " ");
}
}
}
Quick Sort
Definition: Quick sort is an efficient sorting algorithm that uses the divide-and-conquer approach to partition the array into smaller sub-arrays and then sorts them.
Algorithm:
Choose a pivot element.
Partition the array such that elements less than the pivot are on the left and elements greater are on the right.
Recursively apply the same process to the left and right sub-arrays.
Combine the sorted sub-arrays to form the final sorted array.
C# Implementation:
void QuickSort(int[] array, int low, int high)
{
if (low < high)
{
int pi = Partition(array, low, high);
QuickSort(array, low, pi - 1);
QuickSort(array, pi + 1, high);
}
}
int Partition(int[] array, int low, int high)
{
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++)
{
if (array[j] <= pivot)
{
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp1 = array[i + 1];
array[i + 1] = array[high];
array[high] = temp1;
return i + 1;
}
class QuickSortDemo
{
static void Main()
{
int[] array = { 10, 7, 8, 9, 1, 5 };
int n = array.Length;
QuickSort(array, 0, n - 1);
Console.WriteLine("Sorted array:");
foreach (var item in array)
{
Console.Write(item + " ");
}
}
}
POST Answer of Questions and ASK to Doubt