C# Data Structures — Complete Tutorial
1. What is a Data Structure?
A Data Structure is a way of storing and organizing data so that we can efficiently perform operations such as:
- Insert
- Delete
- Search
- Update
- Traverse
For example, suppose we want to store marks:
10 20 30 40 50
We can use an Array.
But if our requirement is:
- Last inserted item should be removed first → Stack
- First inserted item should be removed first → Queue
- Data should be connected node-to-node → Linked List
- Search in a sorted collection efficiently → Binary Search
2. Array
An Array stores multiple values of the same data type in contiguous memory locations.
int[] numbers = { 10, 20, 30, 40, 50 };
Conceptually:
Index: 0 1 2 3 4 ------------------------- Value: | 10 | 20 | 30 | 40 | 50 | -------------------------
Complete Array Program
using System; class Program { static void Main() { int[] numbers = new int[5]; // Insert numbers[0] = 10; numbers[1] = 20; numbers[2] = 30; numbers[3] = 40; numbers[4] = 50; // Display Console.WriteLine("Array Elements:"); for (int i = 0; i < numbers.Length; i++) { Console.WriteLine(numbers[i]); } } }
Output
Array Elements: 10 20 30 40 50
Important Point
Array index starts from:
0
So:
numbers[0] // 10 numbers[1] // 20 numbers[4] // 50
3. Linked List
A Linked List consists of nodes.
Each node contains:
Data + Next
For example:
10 → 20 → 30 → 40 → NULL
Each node points to the next node.
3.1 Creating Node
class Node { public int Data; public Node Next; public Node(int data) { Data = data; Next = null; } }
Here:
Data → stores value Next → stores address/reference of next node
3.2 Complete Linked List Program
using System; class Node { public int Data; public Node Next; public Node(int data) { Data = data; Next = null; } } class LinkedList { Node head; // Insert at end public void Add(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; return; } Node current = head; while (current.Next != null) { current = current.Next; } current.Next = newNode; } // Display public void Display() { Node current = head; while (current != null) { Console.Write(current.Data + " -> "); current = current.Next; } Console.WriteLine("NULL"); } } class Program { static void Main() { LinkedList list = new LinkedList(); list.Add(10); list.Add(20); list.Add(30); list.Add(40); Console.WriteLine("Linked List:"); list.Display(); } }
Output
Linked List: 10 -> 20 -> 30 -> 40 -> NULL
4. Linked List — How It Works
Initially:
head = null
After:
list.Add(10);
head ↓ 10 → NULL
After:
list.Add(20);
head ↓ 10 → 20 → NULL
After:
list.Add(30);
head ↓ 10 → 20 → 30 → NULL
The head always points to the first node.
5. Stack Using Array
A Stack follows:
LIFO — Last In, First Out
Real-life example:
Stack of Plates
If we put:
Plate 1 Plate 2 Plate 3
We remove Plate 3 first.
Push 10 Push 20 Push 30
Stack:
30 ← TOP 20 10
Pop() removes 30.
6. Stack Operations
| Operation | Meaning |
|---|---|
| Push | Insert |
| Pop | Remove |
| Peek | View top |
| Display | Show elements |
7. Stack Using Array — Complete Program
We will not use Stack<T> here because the purpose is to teach students how Stack works internally.
using System; class Stack { int[] arr; int top; int size; public Stack(int size) { this.size = size; arr = new int[size]; top = -1; } // Push public void Push(int value) { if (top == size - 1) { Console.WriteLine("Stack Overflow"); return; } top++; arr[top] = value; Console.WriteLine(value + " pushed"); } // Pop public int Pop() { if (top == -1) { Console.WriteLine("Stack Underflow"); return -1; } int value = arr[top]; top--; return value; } // Peek public int Peek() { if (top == -1) { Console.WriteLine("Stack is empty"); return -1; } return arr[top]; } // Display public void Display() { if (top == -1) { Console.WriteLine("Stack is empty"); return; } Console.WriteLine("Stack Elements:"); for (int i = top; i >= 0; i--) { Console.WriteLine(arr[i]); } } } class Program { static void Main() { Stack stack = new Stack(5); stack.Push(10); stack.Push(20); stack.Push(30); Console.WriteLine(); stack.Display(); Console.WriteLine(); Console.WriteLine("Top: " + stack.Peek()); Console.WriteLine(); Console.WriteLine("Popped: " + stack.Pop()); Console.WriteLine(); stack.Display(); } }
Output
10 pushed 20 pushed 30 pushed Stack Elements: 30 20 10 Top: 30 Popped: 30 Stack Elements: 20 10
8. Understanding top
Initially:
top = -1
After:
Push(10)
top = 0
After:
Push(20)
top = 1
After:
Push(30)
top = 2
Array:
Index: 0 1 2 3 4 ------------------------- Array: | 10 | 20 | 30 | | | ------------------------- ↑ TOP
9. Stack Overflow
Suppose:
Stack stack = new Stack(3);
Maximum capacity is 3.
If we execute:
stack.Push(10); stack.Push(20); stack.Push(30); stack.Push(40);
The fourth element cannot be inserted.
This is:
Stack Overflow
Condition:
if (top == size - 1)
10. Stack Underflow
If Stack is empty:
top = -1
and we call:
stack.Pop();
There is nothing to remove.
This is:
Stack Underflow
11. Queue Using Array
Queue follows:
FIFO — First In, First Out
Real-life example:
Ticket Counter
People stand in a queue:
Person 1 → Person 2 → Person 3
Person 1 gets served first.
12. Queue Operations
| Operation | Meaning |
|---|---|
| Enqueue | Insert |
| Dequeue | Remove |
| Peek | View front |
| Display | Show elements |
13. Queue Variables
For an array-based Queue we use:
int[] arr; int front; int rear;
front
Points to the element that should be removed.
rear
Points to the last inserted element.
Initially:
front = -1 rear = -1
14. Queue Using Array — Complete Program
using System; class Queue { int[] arr; int front; int rear; int size; public Queue(int size) { this.size = size; arr = new int[size]; front = -1; rear = -1; } // Enqueue public void Enqueue(int value) { if (rear == size - 1) { Console.WriteLine("Queue Overflow"); return; } if (front == -1) { front = 0; } rear++; arr[rear] = value; Console.WriteLine(value + " inserted"); } // Dequeue public int Dequeue() { if (front == -1 || front > rear) { Console.WriteLine("Queue Underflow"); return -1; } int value = arr[front]; front++; return value; } // Peek public int Peek() { if (front == -1 || front > rear) { Console.WriteLine("Queue is empty"); return -1; } return arr[front]; } // Display public void Display() { if (front == -1 || front > rear) { Console.WriteLine("Queue is empty"); return; } Console.WriteLine("Queue Elements:"); for (int i = front; i <= rear; i++) { Console.Write(arr[i] + " "); } Console.WriteLine(); } } class Program { static void Main() { Queue queue = new Queue(5); queue.Enqueue(10); queue.Enqueue(20); queue.Enqueue(30); Console.WriteLine(); queue.Display(); Console.WriteLine(); Console.WriteLine("Front: " + queue.Peek()); Console.WriteLine(); Console.WriteLine("Deleted: " + queue.Dequeue()); Console.WriteLine(); queue.Display(); } }
Output
10 inserted 20 inserted 30 inserted Queue Elements: 10 20 30 Front: 10 Deleted: 10 Queue Elements: 20 30
15. Queue Visualization
After:
Enqueue(10); Enqueue(20); Enqueue(30);
we have:
FRONT REAR ↓ ↓ ┌──────┬──────┬──────┬──────┬──────┐ │ 10 │ 20 │ 30 │ │ │ └──────┴──────┴──────┴──────┴──────┘
After:
Dequeue();
10 is removed logically:
FRONT REAR ↓ ↓ ┌──────┬──────┬──────┬──────┬──────┐ │ 10 │ 20 │ 30 │ │ │ └──────┴──────┴──────┴──────┴──────┘ ↑ logically removed
Now:
20 30
16. Linear Search
Linear Search checks elements one by one.
Suppose:
10 20 30 40 50
Search:
40
Process:
10 ❌ 20 ❌ 30 ❌ 40 ✅
17. Linear Search Algorithm
Start ↓ Take first element ↓ Compare with target ↓ Found? ├── Yes → Return index └── No ↓ Move to next element ↓ Continue
18. Linear Search — Complete C# Program
using System; class Program { static int LinearSearch(int[] arr, int target) { for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) { return i; } } return -1; } static void Main() { int[] numbers = { 10, 20, 30, 40, 50 }; Console.Write("Enter number to search: "); int target = Convert.ToInt32( Console.ReadLine()); int result = LinearSearch( numbers, target); if (result != -1) { Console.WriteLine( "Element found at index: " + result); } else { Console.WriteLine( "Element not found"); } } }
Example
Enter number to search: 40 Element found at index: 3
19. Linear Search Complexity
If there are n elements:
Best Case → O(1) Worst Case → O(n)
Example:
10 20 30 40 50
Searching 10:
1 comparison
Searching 50:
5 comparisons
20. Binary Search
Binary Search is a faster searching algorithm.
Important:
Binary Search requires a sorted array.
Example:
10 20 30 40 50 60 70
We search for:
60
Instead of checking every element, we check the middle.
21. Binary Search Concept
Array:
10 20 30 40 50 60 70
Middle:
40
We need:
60
Since:
60 > 40
Ignore the left side.
Now:
50 60 70
Middle:
60
Found!
22. Binary Search Variables
We use:
int left = 0; int right = arr.Length - 1;
Then:
int middle = left + (right - left) / 2;
Why not simply:
(left + right) / 2
The first version avoids potential integer overflow for very large indexes.
23. Binary Search — Complete Program
using System; class Program { static int BinarySearch( int[] arr, int target) { int left = 0; int right = arr.Length - 1; while (left <= right) { int middle = left + (right - left) / 2; if (arr[middle] == target) { return middle; } if (arr[middle] < target) { left = middle + 1; } else { right = middle - 1; } } return -1; } static void Main() { int[] numbers = { 10, 20, 30, 40, 50, 60, 70 }; Console.Write("Enter number to search: "); int target = Convert.ToInt32( Console.ReadLine()); int result = BinarySearch( numbers, target); if (result != -1) { Console.WriteLine( "Element found at index: " + result); } else { Console.WriteLine( "Element not found"); } } }
24. Binary Search Dry Run
Array:
10 20 30 40 50 60 70
Target:
60
Step 1
left = 0 right = 6 middle = 3
Value:
arr[3] = 40
Compare:
60 > 40
Therefore:
left = middle + 1 left = 4
Step 2
left = 4 right = 6 middle = 5
Value:
arr[5] = 60
Found!
Index = 5
25. Binary Search Complexity
Best Case → O(1) Worst Case → O(log n) Average → O(log n)
This is why Binary Search can be much faster than Linear Search for large sorted datasets.
26. Linear Search vs Binary Search
| Feature | Linear Search | Binary Search |
|---|---|---|
| Sorted required? | No | Yes |
| Approach | One-by-one | Divide and conquer |
| Best | O(1) | O(1) |
| Worst | O(n) | O(log n) |
| Easy to implement | Yes | Yes |
| Large sorted data | Less efficient | More efficient |
27. Complete Summary
At this point students should understand:
DATA STRUCTURES │ ┌──────────────────┼─────────────────┐ │ │ │ Array Linked List Linear Structures │ ┌──────┴──────┐ │ │ Stack Queue
And searching:
SEARCHING │ ┌────────┴────────┐ │ │ Linear Search Binary Search O(n) O(log n)
28. All Important Terms to Remember
Array
Index Length Element Traversal
Linked List
Node Data Next Head NULL Traversal
Stack
LIFO Push Pop Peek Top Overflow Underflow
Queue
FIFO Enqueue Dequeue Peek Front Rear Overflow Underflow
Searching
Linear Search Binary Search Target Index Sorted Array
29. Recommended Teaching Sequence
For a classroom, I recommend teaching these topics in this exact sequence:
Day 1 — Array
What is Array? Declaration Initialization Index Traversal Insert Update Delete Search
Day 2 — Linked List
What is Node? Data Next Head Create Node Insert Display Search Delete
Day 3 — Stack
LIFO Push Pop Peek Top Overflow Underflow Stack using Array
Day 4 — Queue
FIFO Enqueue Dequeue Peek Front Rear Overflow Underflow Queue using Array
Day 5 — Searching
Linear Search Binary Search Dry Run Complexity Comparison
After these topics
Move students to:
Sorting ↓ Bubble Sort Selection Sort Insertion Sort ↓ Recursion ↓ Circular Queue ↓ Stack using Linked List ↓ Queue using Linked List ↓ Binary Tree ↓ Binary Search Tree ↓ Heap ↓ Graph
0 Comments
POST Answer of Questions and ASK to Doubt