Deepangshi S.What is Data Structures and Algorithms? 🤓
Data Structures:
A data structure is a way to organize and store data so that it can be accessed and modified efficiently. Think of it as a container for data. There are different types of containers depending on what you want to do with the data (insert, delete, search, etc.).
Algorithms:
An algorithm is a set of steps or instructions designed to solve a specific problem. It’s like a recipe for solving problems using the data stored in data structures.
Types of Data Structures 🤔
💡 Let’s start by introducing the main types of data structures:
Primitive Data Structures:
- Integer
- long
- Float
- double
- Character
- string
- Boolean
Non-Primitive Data Structures:
- Arrays (Static size, same data type)
- Linked Lists (Dynamic size, nodes)
- Stacks (Last In, First Out - LIFO)
- Queues (First In, First Out - FIFO)
- Trees (Hierarchical, like a family tree)
- Graphs (Nodes and edges)
- Hash Tables (Key-value pairs)
Basic Algorithms 🧐
There are different types of algorithms you will use in combination with data structures:
- Searching algorithms (e.g., Binary Search, Linear Search)
- Sorting algorithms (e.g., Bubble Sort, Merge Sort, Quick Sort)
- Traversal algorithms (for trees and graphs)
- Dynamic Programming (breaking problems into smaller subproblems)
- Greedy Algorithms (making the best choice at each step)
Let’s start with a foundational data structure:
- Arrays (Static Size, Same Data Type)
An array in C# is a fixed-size, strongly-typed data structure that holds a collection of elements of the same data type. The size is defined when the array is initialized and cannot be changed later.
using System;
class ArrayExample
{
static void Main()
{
// Declaring an array of size 5
int[] numbers = new int[5] { 10, 20, 30, 40, 50 };
// Accessing array elements
Console.WriteLine("Element at index 0: " + numbers[0]);
// Iterating through the array
foreach (int num in numbers)
{
Console.WriteLine(num);
}
// Searching for an element (Linear Search)
int target = 30;
bool found = false;
for (int i = 0; i < numbers.Length; i++)
{
if (numbers[i] == target)
{
Console.WriteLine($"Element {target} found at index {i}");
found = true;
break;
}
}
if (!found)
{
Console.WriteLine("Element not found");
}
}
}
- Linked Lists (Dynamic Size, Nodes)
A linked list consists of nodes where each node contains a data field and a reference to the next node. C# provides a built-in LinkedList class that allows dynamic memory allocation and easy insertion and deletion of nodes.
using System;
using System.Collections.Generic;
class LinkedListExample
{
static void Main()
{
// Initializing a linked list of integers
LinkedList<int> linkedList = new LinkedList<int>();
// Adding nodes (values) to the linked list
linkedList.AddLast(10);
linkedList.AddLast(20);
linkedList.AddLast(30);
// Iterating over the linked list
foreach (int item in linkedList)
{
Console.WriteLine(item);
}
// Removing a node from the linked list
linkedList.Remove(20);
Console.WriteLine("After removing 20:");
foreach (int item in linkedList)
{
Console.WriteLine(item);
}
}
}
- Stacks (Last In, First Out - LIFO)
A stack follows the LIFO (Last In, First Out) principle. The most recently added item is the first one to be removed. In C#, the Stack class implements this data structure.
using System;
using System.Collections.Generic;
class StackExample
{
static void Main()
{
// Initializing a stack of integers
Stack<int> stack = new Stack<int>();
// Pushing elements onto the stack
stack.Push(10);
stack.Push(20);
stack.Push(30);
// Popping elements (removing from stack)
Console.WriteLine("Popped: " + stack.Pop()); // 30
Console.WriteLine("Popped: " + stack.Pop()); // 20
// Peeking the top element without removing it
Console.WriteLine("Top element: " + stack.Peek()); // 10
}
}
- Queues (First In, First Out - FIFO)
A queue follows the FIFO (First In, First Out) principle. The first item added is the first one to be removed. C# provides a Queue class for this purpose.
using System;
using System.Collections.Generic;
class QueueExample
{
static void Main()
{
// Initializing a queue of integers
Queue<int> queue = new Queue<int>();
// Enqueuing elements (adding to the queue)
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);
// Dequeuing elements (removing from the queue)
Console.WriteLine("Dequeued: " + queue.Dequeue()); // 10
Console.WriteLine("Dequeued: " + queue.Dequeue()); // 20
// Peeking at the front element
Console.WriteLine("Front element: " + queue.Peek()); // 30
}
}
- Trees (Hierarchical, Like a Family Tree)
A tree is a hierarchical data structure where each node has zero or more children, with a single root node at the top. The most common type of tree is a binary tree, where each node has at most two children (left and right).
Here’s a simple implementation of a binary tree in C#:
using System;
class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int value)
{
Value = value;
Left = null;
Right = null;
}
}
class BinaryTree
{
public TreeNode Root;
public void InOrderTraversal(TreeNode node)
{
if (node != null)
{
InOrderTraversal(node.Left);
Console.WriteLine(node.Value);
InOrderTraversal(node.Right);
}
}
}
class TreeExample
{
static void Main()
{
BinaryTree tree = new BinaryTree();
// Creating nodes manually
tree.Root = new TreeNode(1);
tree.Root.Left = new TreeNode(2);
tree.Root.Right = new TreeNode(3);
tree.Root.Left.Left = new TreeNode(4);
tree.Root.Left.Right = new TreeNode(5);
// In-order traversal of the tree
tree.InOrderTraversal(tree.Root);
}
}
- Graphs (Nodes and Edges)
A graph consists of nodes (or vertices) and edges connecting the nodes. Graphs can be directed or undirected. In C#, we can use adjacency lists (using Dictionary>) to represent a graph.
using System;
using System.Collections.Generic;
class Graph
{
// Adjacency list representation
private Dictionary<int, List<int>> adjacencyList = new Dictionary<int, List<int>>();
public void AddEdge(int vertex, int neighbor)
{
if (!adjacencyList.ContainsKey(vertex))
{
adjacencyList[vertex] = new List<int>();
}
adjacencyList[vertex].Add(neighbor);
}
public void PrintGraph()
{
foreach (var vertex in adjacencyList)
{
Console.Write(vertex.Key + " -> ");
foreach (var neighbor in vertex.Value)
{
Console.Write(neighbor + " ");
}
Console.WriteLine();
}
}
}
class GraphExample
{
static void Main()
{
Graph graph = new Graph();
// Adding edges to the graph
graph.AddEdge(1, 2);
graph.AddEdge(1, 3);
graph.AddEdge(2, 4);
graph.AddEdge(3, 5);
graph.AddEdge(4, 5);
// Printing the graph
graph.PrintGraph();
}
}
- Hash Tables (Key-Value Pairs)
In C#, the Dictionary class implements a hash table. It stores key-value pairs, allowing fast lookups by key.
using System;
using System.Collections.Generic;
class HashTableExample
{
static void Main()
{
// Creating a dictionary (hash table)
Dictionary<string, int> hashTable = new Dictionary<string, int>();
// Adding key-value pairs
hashTable["apple"] = 10;
hashTable["banana"] = 20;
hashTable["orange"] = 30;
// Accessing a value by key
Console.WriteLine("Value associated with 'apple': " + hashTable["apple"]);
// Iterating through the dictionary
foreach (var pair in hashTable)
{
Console.WriteLine($"{pair.Key}: {pair.Value}");
}
}
}
Why Learn DSA?
- Efficient code: DSA helps you write code that can solve problems in a more efficient way (faster or with less memory).
- Competitive programming: It’s essential for problem-solving and coding competitions.
