Data Structures in C#: A Beginner's Guide : Mastering

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.