- ELearnHub

1. Getting Started with Data Structures

What is a Data Structure?

A data structure is a way of organizing and storing data so that a program can use that data efficiently.

Imagine that you have 1,000 student records. If all information is stored without any organization, finding one particular student could become difficult and slow. A suitable data structure helps us organize those records according to how we need to use them.

Simple definition:

A data structure is a method of organizing data so that operations such as searching, inserting, deleting and updating can be performed efficiently.

Real-World Examples

A queue of people waiting at a counter.
A stack of books placed one above another.
A family hierarchy represented as a tree.
Road connections between cities represented as a graph.
Student marks stored in an array.

Why Do We Need Data Structures?

A program can store data without explicitly thinking about data structures, but the choice of structure can dramatically affect how efficiently the program works.

Consider searching for a student in a list of one million records. A simple sequential search may need to inspect many records. If the data is organized in an appropriate structure, the same operation may be performed much more efficiently.

The key idea:

We do not choose a data structure only because it can store data. We choose it based on the operations our application needs to perform frequently.

Types of Data Structures

Type	Examples
Linear	Array, Linked List, Stack, Queue
Non-Linear	Tree, Graph
Static	Traditional fixed-size arrays
Dynamic	Linked Lists, Dynamic Collections

Linear Data Structure

In a linear data structure, elements are arranged in a sequential manner.

Array → Element → Element → Element → Element

Linked List → Node → Node → Node → Node

Non-Linear Data Structure

In a non-linear structure, data does not have to follow one simple sequence.

Tree
├── Child
└── Child

Graph
A ─── B
│ │
C ─── D

Abstract Data Type

An Abstract Data Type, or ADT, describes what operations can be performed on a data structure without necessarily describing how those operations are implemented.

For example, a Stack ADT may define:

Push
Pop
Peek
IsEmpty

The actual implementation could use an array or a linked list.

2. Algorithms & Complexity Analysis

What is an Algorithm?

An algorithm is a step-by-step procedure used to solve a problem or perform a task.

Think of an algorithm like a cooking recipe. A recipe gives you a sequence of steps for producing a result. Similarly, an algorithm gives a computer a sequence of steps for solving a problem.

Example: Find the largest number

1. Start with the first number.
2. Compare it with the next number.
3. Keep the larger number.
4. Continue until all numbers are checked.
5. The remaining value is the largest number.

C# Example

int[] numbers = { 12, 45, 7, 89, 23 };

int largest = numbers[0];

for (int i = 1; i < numbers.Length; i++)
{
    if (numbers[i] > largest)
    {
        largest = numbers[i];
    }
}

Console.WriteLine(largest);

What is Time Complexity?

Time complexity describes how the amount of work performed by an algorithm grows as the input size increases.

It does not normally mean the exact number of seconds that a program takes. Different computers have different processors, memory and environments.

Instead of asking:
"How many seconds does this program take?"

We ask:
"How does the amount of work grow when the input becomes larger?"

Example

Suppose a program checks every element in an array. If the array contains 10 elements, it may perform roughly 10 checks.

If the array contains 1,000 elements, it may perform roughly 1,000 checks.

The amount of work grows with the input size. We describe this as O(n).

What is Space Complexity?

Space complexity describes how much additional memory an algorithm needs as the input size increases.

For example, if an algorithm creates another array containing n elements, the additional memory grows with n.

int[] copy = new int[n];

The additional space is proportional to n, so its space complexity is O(n).

Remember:

Time Complexity → How computation grows.

Space Complexity → How additional memory grows.

Big-O Notation

Big-O notation is a mathematical way of describing how the running time or memory requirement of an algorithm grows as the input size increases.

You do not need advanced mathematics to understand Big-O. The most important idea is to recognize how the number of operations grows.

Notation	Name	Simple Meaning
O(1)	Constant	Work does not grow with input size
O(log n)	Logarithmic	Problem becomes much smaller each step
O(n)	Linear	Work grows with the number of items
O(n log n)	Linearithmic	Common in efficient sorting algorithms
O(n²)	Quadratic	Often involves two nested loops
O(2ⁿ)	Exponential	Work can grow extremely quickly

Understanding Complexity with Simple Examples

O(1) — Constant Time

int first = numbers[0];

We directly access one element. Whether the array has 10 elements or 10 million elements, this operation accesses one location.

Time: O(1)

O(n) — Linear Time

for (int i = 0; i < n; i++)
{
    Console.WriteLine(i);
}

If n becomes twice as large, approximately twice as many iterations are performed.

Time: O(n)

O(n²) — Quadratic Time

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        Console.WriteLine(i + "," + j);
    }
}

The outer loop runs n times and the inner loop also runs n times. Therefore the total work is approximately n × n.

Time: O(n²)

O(log n) — Logarithmic Time

Binary search is a classic example. Instead of checking every item, it repeatedly cuts the search space roughly in half.

1,000 items → 500 → 250 → 125 → 62 → 31 → ...

Only a small number of steps are needed compared with checking all 1,000 items.

3. Arrays

What is an Array?

An array stores multiple values of the same type in an indexed sequence.

Think of an array as a row of numbered boxes.

Index: 0 1 2 3
Value: 10 20 30 40

C#

int[] numbers = { 10, 20, 30, 40 };

Console.WriteLine(numbers[0]);
Console.WriteLine(numbers[2]);

Array indexing starts from zero in C#.

Array Operations

Operation	Typical Complexity
Access by index	O(1)
Search	O(n)
Update by index	O(1)
Insert in middle	O(n)
Delete from middle	O(n)

Why is array access O(1)?

An array stores elements in a contiguous memory layout. The computer can calculate the location of an element from its index, so it does not need to inspect every previous element.

Accessing:
numbers[3]

does not require checking:
numbers[0] → numbers[1] → numbers[2] → numbers[3]

The location can be calculated directly.

Array Complexity in Practice

Searching an Array

int target = 30;

for (int i = 0; i < numbers.Length; i++)
{
    if (numbers[i] == target)
    {
        Console.WriteLine("Found");
        break;
    }
}

In the worst case, the target may be at the last position or may not exist at all.

Time Complexity: O(n)

Extra Space: O(1)

Multi-Dimensional Arrays

A two-dimensional array can represent data in rows and columns.

int[,] marks =
{
    { 80, 75, 90 },
    { 70, 85, 88 }
};

Console.WriteLine(marks[0, 1]);

Two-dimensional arrays are useful for tables, matrices and grid-based problems.

4. Linked Lists

What is a Linked List?

A linked list is a collection of nodes where each node contains data and a reference to another node.

Node → Node → Node → Node → NULL

Each node knows where the next node is located.

Unlike an array, linked-list elements do not need to be stored next to each other in memory.

Singly Linked List

In a singly linked list, each node contains data and a reference to the next node.

C# Node

class Node
{
    public int Data;

    public Node Next;

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

Creating Nodes

Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);

first.Next = second;
second.Next = third;

10 → 20 → 30 → NULL

Doubly Linked List

A doubly linked list stores references to both the previous and next nodes.

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

class Node
{
    public int Data;

    public Node Previous;

    public Node Next;
}

This allows traversal in both directions, at the cost of additional memory for the previous reference.

Circular Linked List

In a circular linked list, the final node points back to the first node instead of pointing to NULL.

10 → 20 → 30
↑___________↓

Circular structures are useful in applications where processing repeatedly cycles through a collection.

Linked List Complexity

Operation	Typical Complexity
Access by position	O(n)
Search	O(n)
Insert at beginning	O(1)
Delete at beginning	O(1)
Insert after known node	O(1)

Key difference:

Array → Fast direct access.
Linked List → Efficient insertion/removal when the relevant node or position is already known.

5. Stacks & Queues

Stack

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

Think about a stack of plates. The plate placed last on top is normally the first one removed.

PUSH 30
┌─────┐
│ 30 │ ← TOP
├─────┤
│ 20 │
├─────┤
│ 10 │
└─────┘

Stack Operations

Push — Add an element.
Pop — Remove the top element.
Peek — View the top element.
IsEmpty — Check whether the stack is empty.

C# Stack

Stack<int> stack = new Stack<int>();

stack.Push(10);
stack.Push(20);
stack.Push(30);

Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Peek());

Push: O(1)
Pop: O(1)
Peek: O(1)

Applications of Stack

Undo and redo operations.
Browser navigation history.
Expression evaluation.
Parentheses matching.
Function call management.
Depth-first search.

Example: In many programming languages, function calls are managed using a call stack.

Queue

A queue follows the principle FIFO — First In, First Out.

Think about people waiting in a line. Normally the person who arrives first is served first.

FRONT
10 → 20 → 30 → 40
↑ ↑
Remove Add
FRONT REAR

C#

Queue<int> queue = new Queue<int>();

queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);

Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Peek());

Enqueue: O(1)
Dequeue: O(1)
Peek: O(1)

Circular Queue

A circular queue treats the storage as a circular structure. When the rear reaches the end, it can reuse available positions at the beginning.

Circular queues are useful in fixed-size buffers and scheduling systems.

Queue Complexity

Operation	Complexity
Enqueue	O(1)
Dequeue	O(1)
Peek	O(1)
Search	O(n)

6. Trees

Tree Fundamentals

A tree is a non-linear data structure consisting of nodes connected by edges in a hierarchical structure.

50 / \ 30 70 / \ / \ 20 40 60 80

Important Terminology

Root: Topmost node.
Parent: Node connected to child nodes.
Child: Node below a parent.
Leaf: Node without children.
Edge: Connection between nodes.
Height: Longest path from a node to a leaf, depending on the convention used.

Binary Tree

A binary tree is a tree in which each node has at most two children.

class TreeNode
{
    public int Data;

    public TreeNode Left;

    public TreeNode Right;

    public TreeNode(int data)
    {
        Data = data;
    }
}

Binary Search Tree

A Binary Search Tree, or BST, organizes values according to an ordering rule.

Values smaller than the node → Left subtree

Values greater than the node → Right subtree

For example:

50 / \ 30 70 / \ / \ 20 40 60 80

Searching for 60 begins at 50. Since 60 is greater than 50, move right. At 70, 60 is smaller, so move left.

In a reasonably balanced BST, search, insertion and deletion can be approximately O(log n).

In the worst case, an unbalanced BST can behave like a linked list and become O(n).

Tree Traversal

Traversal means visiting every node in a tree according to a particular order.

Inorder

Left → Root → Right

void InOrder(TreeNode node)
{
    if (node == null)
        return;

    InOrder(node.Left);

    Console.WriteLine(node.Data);

    InOrder(node.Right);
}

Preorder

Root → Left → Right

Postorder

Left → Right → Root

Tree traversal visits every node once.

Typical time complexity: O(n)

Tree Complexity

Operation	Balanced BST	Worst-Case Unbalanced BST
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Traversal	O(n)	O(n)

7. Searching & Sorting Algorithms

Linear Search

Linear search checks elements one by one until the target is found or the collection ends.

int[] numbers = { 10, 20, 30, 40, 50 };

int target = 40;

for (int i = 0; i < numbers.Length; i++)
{
    if (numbers[i] == target)
    {
        Console.WriteLine("Found at index " + i);
        break;
    }
}

Best Case: O(1)
Worst Case: O(n)
Space: O(1)

Linear search does not require the data to be sorted.

Binary Search

Binary search works on sorted data. Instead of checking every element, it compares the target with the middle element and eliminates approximately half of the remaining search space.

Search:
10 20 30 40 50 60 70 80

Target = 70

Check middle → 40
70 is greater → ignore left half
Check new middle → continue

C#

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

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

        if (numbers[middle] == target)
            return middle;

        if (numbers[middle] < target)
            left = middle + 1;
        else
            right = middle - 1;
    }

    return -1;
}

Best Case: O(1)
Worst Case: O(log n)
Space: O(1)

Binary search requires the data to be sorted.

Bubble Sort

Bubble Sort repeatedly compares neighboring elements and swaps them when they are in the wrong order.

Example:

5 3 8 1
Compare 5 and 3 → swap
3 5 8 1
Continue until larger values gradually move toward the end.

for (int i = 0; i < numbers.Length - 1; i++)
{
    for (int j = 0; j < numbers.Length - i - 1; j++)
    {
        if (numbers[j] > numbers[j + 1])
        {
            int temp = numbers[j];

            numbers[j] = numbers[j + 1];

            numbers[j + 1] = temp;
        }
    }
}

Average Time: O(n²)
Worst Time: O(n²)
Extra Space: O(1)

Bubble Sort is useful for learning how sorting works, but it is generally not the preferred choice for large datasets.

Selection Sort

Selection Sort repeatedly finds the smallest remaining value and places it in the correct position.

for (int i = 0; i < numbers.Length - 1; i++)
{
    int minIndex = i;

    for (int j = i + 1;
         j < numbers.Length;
         j++)
    {
        if (numbers[j] < numbers[minIndex])
        {
            minIndex = j;
        }
    }

    int temp = numbers[i];

    numbers[i] = numbers[minIndex];

    numbers[minIndex] = temp;
}

Time: O(n²)
Extra Space: O(1)

Insertion Sort

Insertion Sort builds the sorted portion of an array one element at a time.

Think about arranging playing cards in your hand.

You take one new card and insert it into the correct position among the cards already arranged.

for (int i = 1; i < numbers.Length; i++)
{
    int key = numbers[i];

    int j = i - 1;

    while (j >= 0 && numbers[j] > key)
    {
        numbers[j + 1] = numbers[j];

        j--;
    }

    numbers[j + 1] = key;
}

Best Case: O(n)
Average Case: O(n²)
Worst Case: O(n²)
Extra Space: O(1)

Merge Sort

Merge Sort uses a divide-and-conquer strategy. It repeatedly divides the collection into smaller parts, sorts those parts and merges them together.

Example:

[8, 3, 5, 1]
↓
[8, 3] [5, 1]
↓
[3, 8] [1, 5]
↓
[1, 3, 5, 8]

Merge Sort has predictable O(n log n) time complexity.

Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Extra Space: O(n)

Quick Sort

Quick Sort is another divide-and-conquer sorting algorithm. It chooses a pivot and partitions values around that pivot.

Smaller values ← Pivot → Larger values

The exact performance depends on pivot selection and how balanced the partitions are.

Average Case: O(n log n)
Worst Case: O(n²)
Typical auxiliary space: O(log n)

The exact space usage can vary depending on the implementation and recursion behavior.

8. Advanced Concepts

Recursion

Recursion occurs when a function calls itself to solve a smaller version of the same problem.

Every recursive solution needs a condition that stops the recursion. This is called the base case.

Factorial Example

int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Factorial(4)
= 4 × Factorial(3)
= 4 × 3 × Factorial(2)
= 4 × 3 × 2 × Factorial(1)
= 24

Recursive algorithms often use the call stack, so recursion affects space complexity as well as time complexity.

Hashing

Hashing is a technique that uses a hash function to map a key to a location or bucket, allowing efficient lookup in many practical cases.

C# Dictionary

Dictionary<int, string> students =
    new Dictionary<int, string>();

students[101] = "Rahul";
students[102] = "Priya";

Console.WriteLine(students[101]);

Dictionary is a common C# implementation based on hashing concepts.

Average-case lookup, insertion and deletion in a well-designed hash table are commonly described as O(1), although worst-case behavior can be O(n) depending on collisions and implementation details.

Graphs

A graph consists of vertices, also called nodes, and edges that connect those vertices.

A ─── B
│ │
C ─── D

Graphs can represent roads, social networks, computer networks, dependencies and many other real-world relationships.

Important Terms

Vertex
Edge
Degree
Path
Cycle
Directed Graph
Undirected Graph
Weighted Graph

Breadth-First Search — BFS

BFS explores a graph level by level. It commonly uses a queue.

Start
↓
Visit immediate neighbors
↓
Visit the next level
↓
Continue until all reachable nodes are processed.

For a graph represented using an adjacency list, BFS typically runs in:

Time: O(V + E)
Space: O(V)

Here V represents vertices and E represents edges.

Depth-First Search — DFS

DFS explores as far as possible along one path before backtracking.

DFS can be implemented using recursion or an explicit stack.

Conceptual C# Example

void DFS(int node)
{
    visited[node] = true;

    foreach (int neighbor in graph[node])
    {
        if (!visited[neighbor])
        {
            DFS(neighbor);
        }
    }
}

Time: O(V + E)
Space: O(V)

Data Structure & Algorithm Comparison

Structure / Algorithm	Main Operation	Typical Complexity
Array	Index Access	O(1)
Linked List	Sequential Access	O(n)
Stack	Push / Pop	O(1)
Queue	Enqueue / Dequeue	O(1)
Balanced BST	Search	O(log n)
Hash Table	Lookup	Average O(1)
Linear Search	Search	O(n)
Binary Search	Search	O(log n)
Merge Sort	Sorting	O(n log n)
Bubble Sort	Sorting	O(n²)

How Do We Choose a Data Structure?

There is no single data structure that is best for every problem. The correct choice depends on what operations your application performs most frequently.

Requirement	Possible Choice
Fast access by index	Array
Frequent insertion/removal at beginning	Linked List
Last-in-first-out processing	Stack
First-in-first-out processing	Queue
Hierarchical information	Tree
Fast average key lookup	Hash Table / Dictionary
Network relationships	Graph

Important Principle: The goal of learning data structures is not to memorize definitions. The goal is to understand the trade-offs and select a suitable structure for a problem.

Mini Project — Student Record Manager

Build a console-based Student Record Manager in C# that demonstrates multiple data structures and algorithms.

Project Requirements

Store student records in a suitable collection.
Add new students.
Search students by ID.
Sort students by marks.
Remove a student.
Display students in different orders.
Use at least one stack.
Use at least one queue.
Compare linear search with binary search.
Document the time complexity of the important operations.

Example Student Model

class Student
{
    public int Id { get; set; }

    public string Name { get; set; }

    public double Marks { get; set; }
}

Complexity Cheat Sheet

O(1) Constant — input size has little or no effect on the number of operations.

O(log n) Logarithmic — the problem is repeatedly reduced, often by half.

O(n) Linear — work grows approximately with the number of input elements.

O(n log n) Common in efficient comparison-based sorting.

O(n²) Quadratic — commonly caused by two nested loops over the same input.

O(2ⁿ) Exponential — grows extremely rapidly as input increases.

Exam Tip: Do not confuse the complexity classes. When analyzing code, first identify how many times the important operations execute and then express how that count grows with input size.

Practice Challenges

Beginner Level

Find the largest value in an array.
Find the smallest value in an array.
Calculate the sum of array elements.
Reverse an array.
Count even and odd numbers.

Intermediate Level

Implement a singly linked list.
Implement a stack.
Implement a queue.
Implement linear search.
Implement binary search.
Implement Bubble Sort.
Implement Insertion Sort.

Advanced Level

Implement a Binary Search Tree.
Implement tree traversal.
Implement Merge Sort.
Implement Quick Sort.
Implement BFS.
Implement DFS.
Compare the complexity of your solutions.

Course Summary

Data structures and algorithms are fundamental to computer science because they teach us how to organize information and solve computational problems efficiently.

In this course, you learned the concepts progressively: first understanding data organization, then algorithms and complexity, followed by individual data structures and finally searching, sorting and graph algorithms.

Data structure fundamentals
Linear and non-linear structures
Algorithms
Time complexity
Space complexity
Big-O notation
Arrays
Linked Lists
Stacks
Queues
Trees
Binary Search Trees
Searching algorithms
Sorting algorithms
Recursion
Hashing
Graphs
BFS and DFS
Algorithm comparison

Final Learning Goal: By the end of this course, you should not only know what an array, stack, queue, tree or graph is. You should be able to look at a problem, identify the operations it requires, choose an appropriate data structure, implement the solution in C#, and explain its time and space complexity.

Learn. Grow. Succeed.

Data Structures & Algorithms

1. Getting Started with Data Structures

What is a Data Structure?

Real-World Examples

Why Do We Need Data Structures?

Types of Data Structures

Linear Data Structure

Non-Linear Data Structure

Abstract Data Type

2. Algorithms & Complexity Analysis

What is an Algorithm?

What is Time Complexity?

Example

What is Space Complexity?

Big-O Notation

Understanding Complexity with Simple Examples

O(1) — Constant Time

O(n) — Linear Time

O(n²) — Quadratic Time

O(log n) — Logarithmic Time

3. Arrays

What is an Array?

Array Operations

Why is array access O(1)?

Array Complexity in Practice

Multi-Dimensional Arrays

4. Linked Lists

What is a Linked List?

Singly Linked List

Creating Nodes

Doubly Linked List

Circular Linked List

Linked List Complexity

5. Stacks & Queues

Stack

Stack Operations

Applications of Stack

Queue

Circular Queue

Queue Complexity

6. Trees

Tree Fundamentals

Important Terminology

Binary Tree

Binary Search Tree

Tree Traversal

Inorder

Preorder

Postorder

Tree Complexity

7. Searching & Sorting Algorithms

Linear Search

Binary Search

Bubble Sort

Selection Sort

Insertion Sort

Merge Sort

Quick Sort

8. Advanced Concepts

Recursion

Hashing

Graphs

Important Terms

Breadth-First Search — BFS

Depth-First Search — DFS

Data Structure & Algorithm Comparison

How Do We Choose a Data Structure?

Mini Project — Student Record Manager

Project Requirements

Example Student Model

Complexity Cheat Sheet

Practice Challenges

Beginner Level

Intermediate Level

Advanced Level

Course Summary