📘 Chapter One: Data Structures and Algorithms

🔶 1.0 Introduction

In Form Five, you explored:

 Problem-solving techniques
 Programming with C++
 Algorithms and pseudocode

These skills prepare you to understand data structures and algorithms, which are essential in
building fast and efficient software.

💡 Key Takeaway:

Data structures help you organize and store data. Algorithms help you work with that data
efficiently.

🔷 1.1 Concept of Data Structure

A data structure is a way of organizing, managing, and storing data to make it easy to access
and modify.

 It builds logical relationships between data elements.

 Helps improve the efficiency of programs, saving time and memory.
 Used in almost every computer program — from websites to mobile apps.

🔷 🔑 Importance of Data Structures

Benefit Explanation
✅ Efficient data access Helps in finding, updating, or deleting data quickly.
✅ Memory optimization Stores data in a way that reduces memory usage.
✅ Better performance Speeds up program execution by using suitable structures.
✅ Organized data
Makes complex data easier to manage and work with.
handling
Common data structures (like lists or stacks) can be reused in many
✅ Code reusability
programs.

🎯 Goals of Data Structures

A good data structure is designed to achieve these goals:

Goal Description
🎯 Efficiency Perform operations (like search, insert, delete) quickly.
🎯 Simplicity Keep the structure easy to understand and use.
🎯 Modularity Break complex systems into smaller, manageable parts.
🎯 Reusability Allow the same structure to be used in different programs.
🎯 Scalability Handle increasing amounts of data smoothly.

⚖️Factors to Consider When Choosing a Data Structure

Before choosing a data structure, a programmer must consider:

Factor Explanation
🧩 Type of data What kind of data are you working with? Numbers, names, records?
Operations to perform Will you search, sort, insert, delete, or update the data?
💾 Memory usage How much memory does the structure require?
🚀 Performance (speed) How fast can the structure do tasks (e.g., searching or sorting)?
🧠 Complexity Is it easy to implement and debug?
🔁 Frequency of updates How often will data be added, removed, or changed?

🔶 1.2 Classification of Data Structures

Data structures help organize and store data efficiently. They are classified based on how they
handle and relate data.
🔷 A. Main Classification

Type Description

🧱 Primitive Data These are the basic data types built into most programming languages. They
Structures include numbers, characters, and boolean values.

🏗️Non-Primitive Data These are more complex and are built using primitive types. They allow storing
Structures and managing collections of data in various ways.

🔷 B. Other Classifications

Classification Examples Description

Linear structures store elements in sequence;

Linear: Arrays, Stacks, Queues;
📏 Linear vs Non-linear Non-linear structures store data in branching or
Non-linear: Trees, Graphs
network forms.

Static structures have a fixed size. Dynamic

Static: Array; Dynamic: Linked
💾 Static vs Dynamic structures can grow or shrink as needed during
List, Stack, Queue
program execution.

Homogeneous: Array;
🧬 Homogeneous vs Homogeneous stores one data type;
Heterogeneous: Structures in
Heterogeneous Heterogeneous stores mixed types of data.
C/C++

🔷 C. Classification Diagram from Figure 1.1

mathematica
CopyEdit
Data Structure
├── Primitive
│ ├── Integer
│ ├── Float
│ ├── Character
│ └── Boolean
└── Non-Primitive
├── Linear
│ ├── Static
│ │ └── Array
│ └── Dynamic
│ ├── Linked List
 │ ├── Stack
│ └── Queue
└── Non-Linear
├── Tree
└── Graph

🔷 D. Detailed Explanation of Types

✅ Primitive Data Structures

 Definition: Simple and basic data types built into the language.
 Examples:
o int: Whole numbers (e.g., 10, 20)
o float: Decimal numbers (e.g., 3.14)
o char: Single characters (e.g., 'A', 'b')
o bool: Boolean values (True/False)
 Use: Used for simple operations, calculations, and condition checking.

✅ Non-Primitive Data Structures

These structures store multiple data values and provide ways to manage them.

1. Linear Data Structures

 Data is arranged in a line or sequence.

🔹 Array

 Collection of elements stored in contiguous memory locations.

 Fixed size.
 Example: int scores[5] = {90, 85, 78, 92, 88};

🔹 Linked List

 Elements (nodes) linked together using pointers.

 Dynamic size – can grow or shrink.
 Each node contains data + a pointer to the next node.

🔹 Stack

 Follows Last-In, First-Out (LIFO) principle.

 You can only access the top element.
 Example: Undo function in a word processor.
🔹 Queue

 Follows First-In, First-Out (FIFO) principle.

 Example: Printer job queue.

2. Non-Linear Data Structures

 Data is arranged in a hierarchy or network.

🔹 Tree

 Hierarchical structure with root, branches, and leaves.

 Commonly used in file systems or family trees.

🔹 Graph

 Set of nodes (vertices) connected by edges.

 Useful in social networks, maps, and routing.

✅ Quick Comparison Table

Type Structure Growth Access Real-world Example

Array Linear, Static Fixed By index Student marks

Linked List Linear, Dynamic Flexible Sequential Music playlist

Stack Linear, Dynamic Flexible Top only Undo in MS Word

Queue Linear, Dynamic Flexible First in, first out Customer queue

Tree Non-linear Hierarchical Parent-child File explorer

Graph Non-linear Networked Any node City map or Facebook friends

📂 Topic: Static Data Structures

✅ What is a Static Data Structure?

A static data structure is a data structure where the size and memory are fixed at compile
time (before running the program). Once created, the size cannot be changed during execution.
📌 Example: When you declare an array of size 5, it will always hold exactly 5 elements during
program execution.

🟢 Advantages of Static Data Structures

Advantage Explanation

✅ Easy to use Simple to declare and access.

Data is stored in a continuous memory block, allowing fast retrieval using

⚡ Fast access
indices.

📏 Predictable memory usage Because size is fixed, it's easy to manage and optimize memory.

🔴 Disadvantages of Static Data Structures

Disadvantage Explanation

Wastes memory if not fully used, or causes overflow if space is

❌ Fixed size
insufficient.

🔄 Inefficient insertion/deletion Requires shifting elements manually.

💾 Memory inflexible Cannot grow dynamically to accommodate more data during execution.

🔷 Arrays
An array is a group of similar data elements stored in consecutive memory locations. It is the
most common static data structure.

📌 Example in C++
cpp
CopyEdit
int marks[5] = {50, 60, 70, 80, 90};

🛠️Common Operations on Arrays

 Operation Description Example

📥 Insertion Add a new element at a specific position. Insert 100 at index 2.

❌ Deletion Remove an element and shift others. Delete item at index 1.

🔍 Searching Find if a value exists. Search for 60.

🧭 Traversal Visit each element. Print all elements.

🔃 Sorting Rearrange elements. Sort 5, 2, 3 → 2, 3, 5

💻 Code Examples

Insertion:

cpp
CopyEdit
int arr[6] = {1, 2, 4, 5};
int n = 4, pos = 2, val = 3;

for (int i = n; i > pos; i--) {

arr[i] = arr[i - 1];
}
arr[pos] = val;
n++;

Deletion:

cpp
CopyEdit
int pos = 2;
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
n--;

Linear Search:

cpp
CopyEdit
int target = 45;
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
cout << "Found at index " << i;
}
}
🟡 Types of Arrays

1. Single-Dimensional Array

 Stores elements in a single row.

cpp
CopyEdit
int nums[3] = {10, 20, 30};
cout << nums[1]; // Outputs 20

2. Multi-Dimensional Array

 Used to represent tables/matrices.

cpp
CopyEdit
int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
cout << matrix[1][2]; // Outputs 6

✅ Advantages of Arrays

Advantage Explanation

🚀 Fast element access Any element can be accessed instantly using its index.

🛠️Easy to use Syntax is straightforward.

📊 Suitable for linear data Best for storing lists of similar values (e.g. marks, prices).

❌ Disadvantages of Arrays

Disadvantage Explanation

❌ Fixed size Can't grow/shrink during program execution.

🔄 Insertion/deletion is costly Requires shifting elements manually.

🔧 Same data type only Can't mix different types (e.g., number and text).

🧭 Pointers
A pointer is a variable that stores the memory address of another variable. It is a powerful tool
in low-level memory handling.

📌 Example:
cpp
CopyEdit
int a = 10;
int *p = &a;
cout << *p; // Outputs 10

🔁 Pointer Operations

Operation Description Example

📌 Declaration Declare a pointer variable. int *p;

🏷️Address storage Assign address of another variable. p = &x;

🧾 Dereferencing Access the value at the address. *p

➕ Pointer arithmetic Navigate through arrays. *(p + 1)

🔗 Pointers with Arrays

Pointers and arrays are tightly linked. When you declare an array:

cpp
CopyEdit
int arr[4] = {10, 20, 30, 40};
int *ptr = arr;

You can access array elements using pointers:

cpp
CopyEdit
cout << *(ptr + 2); // Outputs 30

🔄 Traversing Array with Pointer

cpp
CopyEdit
for (int i = 0; i < 4; i++) {
cout << *(ptr + i) << " ";
}
✅ Advantages of Pointers

Advantage Explanation

🧠 Powerful Can handle dynamic memory and complex structures.

🔗 Works with arrays Easy to move through array elements.

📦 Enables data sharing Functions can directly modify original variables.

❌ Disadvantages of Pointers

Disadvantage Explanation

❌ Complex to understand Beginners may find pointer concepts confusing.

🐞 Risky Misuse can cause memory errors or crashes.

⚠️Uninitialized pointers Can point to garbage memory and crash programs.

🗂️Records (Structures)
A record (called struct in C++) is a collection of different data types grouped under one
name.

📌 Example:
cpp
CopyEdit
struct Student {
int id;
char name[20];
float grade;
};

📥 Creating and Using Records

cpp
CopyEdit
Student s1;
s1.id = 101;
strcpy(s1.name, "Jane");
s1.grade = 89.5;

cout << s1.name; // Outputs: Jane

📦 Array of Records

You can use records to store multiple entries:

cpp
CopyEdit
Student students[3];

for (int i = 0; i < 3; i++) {

cin >> students[i].id >> students[i].name >> students[i].grade;
}

🧰 Operations on Records

Operation Description

🏗️Creation Define structure type using struct.

➕ Insertion Assign data to each field.

📤 Access Print or use the values.

📚 Use with arrays Store multiple records like a database.

✅ Advantages of Records

Advantage Explanation

📦 Multiple data types Can store a mix of values like name, age, and grade.

🧠 Logical grouping Keeps related info together for better organization.

🔄 Reusable Can define once and use many times.

❌ Disadvantages of Records
 Disadvantage Explanation

❌ No dynamic memory Size of fields is fixed.

🛠️Manual field access Each field must be accessed individually.

🔄 Complex with large data Managing many records can become harder.

🧠 Summary
Structure Key Use Advantage Limitation

Store list of
Array Fast access Fixed size
same type

Access
Flexible, Risky,
Pointer memory
powerful complex
directly

Store
different
Record
types
together
 Structure Key Use Advantage Limitation

📘 Dynamic Data Structures

🔍 Definition

Dynamic data structures are data structures that can change size
during program execution. Unlike static data structures (like
arrays), which have a fixed size, dynamic structures grow or
shrink as needed, making them more flexible and memory-
efficient.

📌 Key Characteristics

 Memory is allocated at runtime.

 Can expand or contract depending on the program's
needs.
 Often involve the use of pointers to link data elements.
 Common dynamic data structures include:
o Linked Lists
o Stacks
o Queues
o Trees
o Graphs
 Structure Key Use Advantage Limitation

✅ Advantages of Dynamic Data Structures

Advantage Description
They can grow or shrink as needed
✅ Flexible Size
during runtime.
Use only as much memory as needed,
✅ Memory Efficient
avoiding wastage.
✅ Better for Unknown Ideal when the amount of data is not
Sizes known in advance.

❌ Disadvantages of Dynamic Data Structures

Disadvantage Description
Accessing elements is slower compared
❌ Slower Access
to arrays.
❌ Complex Requires knowledge of pointers and
Implementation memory management.
❌ Risk of Memory Improper handling of memory
Leaks allocation/deallocation can cause leaks.

🧠 Comparison: Static vs Dynamic Data Structures

Dynamic (e.g., Linked

Feature Static (e.g., Array)
List)
Fixed at compile
Size Can change at runtime
time
Memory May waste
Uses memory efficiently
Usage memory
Easier to
Ease of Use Requires more coding skills
implement
Flexibility Less flexible More flexible
Faster element Slower due to pointer
Speed
access navigation
A linked list in C++ is a linear collection of nodes where each
node contains:

 Data (e.g., int, float, string, etc.)

 Structure Key Use Advantage Limitation

 A pointer to the next node

It allows dynamic memory allocation, making it ideal for

scenarios where the number of elements is not known in
advance.

🧱 Node Structure in C++

cpp
CopyEdit
#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
};

✅ Advantages of Linked Lists

Advantage Explanation
✅ Dynamic Size Can grow or shrink during runtime
Easy insertion/deletion compared to
✅ No Shifting Needed
arrays
✅ Efficient Memory No unused memory like in fixed-size
Use arrays

❌ Disadvantages of Linked Lists

Disadvantage Explanation
❌ Extra Memory Uses extra space for storing pointers
No random access; must traverse node
❌ Slower Access
by node
❌ More Complex
Requires pointer manipulation
Code

🛠️Common Operations (Singly Linked

 Structure Key Use Advantage Limitation

List in C++)
🔹 1. Insertion at the Beginning
cpp
CopyEdit
void insertAtBeginning(Node*& head, int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = head;
head = newNode;
}

🔹 2. Insertion at the End

void insertAtEnd(Node*& head, int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = NULL;

if (head == NULL) {
head = newNode;
return;
}

Node* temp = head;

while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}

🔹 3. Traversing the List

void traverse(Node* head) {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}

🔹 4. Delete Node by Value

void deleteNode(Node*& head, int value) {
if (head == NULL) return;

if (head->data == value) {
Node* toDelete = head;
 Structure Key Use Advantage Limitation

head = head->next;
delete toDelete;
return;
}

Node* temp = head;

while (temp->next != NULL && temp->next->data !
= value)
temp = temp->next;

if (temp->next == NULL) return;

Node* toDelete = temp->next;

temp->next = temp->next->next;
delete toDelete;
}

🔹 5. Search for a Value

cpp
CopyEdit
bool search(Node* head, int value) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == value)
return true;
temp = temp->next;
}
return false;
}

🧪 Sample Main Program

cpp
CopyEdit
int main() {
Node* head = NULL;

insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtEnd(head, 30);

cout << "Linked List: ";

traverse(head);

cout << "Searching for 30: " << (search(head,

30) ? "Found" : "Not Found") << endl;

deleteNode(head, 10);
cout << "After Deleting 10: ";
traverse(head);
 Structure Key Use Advantage Limitation

return 0;
}

🔎 Output:
rust
CopyEdit
Linked List: 20 -> 10 -> 30 -> NULL
Searching for 30: Found
After Deleting 10: 20 -> 30 -> NULL

📚 1. STACK
🔍 Definition:

A Stack is a linear data structure that follows the LIFO principle:

Last In, First Out — the last element added is the first one to be removed.

📦 Stack Real-Life Example:

 A stack of plates: you add on top and remove from the top.

✅ Advantages of Stack:

Advantage Description
✅ Easy to implement Simple logic using arrays or linked lists
✅ Supports recursion Helps in function call management
✅ Memory efficient If implemented using linked list, uses dynamic memory

❌ Disadvantages:

Disadvantage Description
❌ Limited Size (Array) Array-based stack has a fixed size
❌ No Random Access You can't access elements in the middle directly
🛠️Stack Operations (with Time Complexity)

Operation Description Time Complexity

push(x) Add item on top O(1)
pop() Remove top item O(1)
peek() View top item O(1)
isEmpty() Check if stack is empty O(1)

💡 Stack Using Array in C++

cpp
CopyEdit
#define SIZE 100
class Stack {
int top;
int arr[SIZE];

public:
Stack() { top = -1; }

void push(int x) {
if (top >= SIZE - 1)
cout << "Stack Overflow\n";
else
arr[++top] = x;
}

void pop() {
if (top < 0)
cout << "Stack Underflow\n";
else
top--;
}

int peek() {
if (top < 0) return -1;
return arr[top];
}

bool isEmpty() {
return top == -1;
}

void display() {
for (int i = top; i >= 0; i--)
cout << arr[i] << " ";
cout << endl;
}
};
💡 Stack Using Linked List in C++
cpp
CopyEdit
struct Node {
int data;
Node* next;
};

class Stack {
Node* top = NULL;

public:
void push(int x) {
Node* newNode = new Node;
newNode->data = x;
newNode->next = top;
top = newNode;
}

void pop() {
if (top == NULL)
cout << "Stack Underflow\n";
else {
Node* temp = top;
top = top->next;
delete temp;
}
}

int peek() {
if (top == NULL)
return -1;
return top->data;
}

bool isEmpty() {
return top == NULL;
}

void display() {
Node* temp = top;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

📚 2. QUEUE
🔍 Definition:
A Queue is a linear data structure that follows the FIFO principle:

First In, First Out — the first element added is the first one to be removed.

📦 Queue Real-Life Example:

 People standing in a line: the first person to join the line is the first to be served.

✅ Advantages of Queue:

Advantage Description
✅ Maintains order Elements processed in the same order they arrive
✅ Useful in simulations Like printers, task scheduling
✅ Easy to implement Simple to code using arrays or linked lists

❌ Disadvantages:

Disadvantage Description
May cause overflow even when space is available (solved by circular
❌ Fixed size (array)
queue)
❌ No Random Access Cannot access middle elements directly

🛠️Queue Operations (with Time Complexity)

Operation Description Time Complexity

enqueue(x)Add item at rear O(1)
dequeue() Remove item from front O(1)
peek() View front item O(1)
isEmpty() Check if empty O(1)

💡 Queue Using Array in C++

cpp
CopyEdit
#define SIZE 100
class Queue {
int front, rear;
int arr[SIZE];
public:
Queue() {
front = rear = -1;
}

void enqueue(int x) {
if (rear == SIZE - 1)
cout << "Queue Overflow\n";
else {
if (front == -1) front = 0;
arr[++rear] = x;
}
}

void dequeue() {
if (front == -1 || front > rear)
cout << "Queue Underflow\n";
else
front++;
}

int peek() {
if (front == -1 || front > rear)
return -1;
return arr[front];
}

bool isEmpty() {
return (front == -1 || front > rear);
}

void display() {
for (int i = front; i <= rear; i++)
cout << arr[i] << " ";
cout << endl;
}
};

💡 Queue Using Linked List in C++

cpp
CopyEdit
struct Node {
int data;
Node* next;
};

class Queue {
Node *front, *rear;

public:
Queue() {
front = rear = NULL;
}
 void enqueue(int x) {
Node* newNode = new Node;
newNode->data = x;
newNode->next = NULL;
if (rear == NULL)
front = rear = newNode;
else {
rear->next = newNode;
rear = newNode;
}
}

void dequeue() {
if (front == NULL) {
cout << "Queue Underflow\n";
return;
}
Node* temp = front;
front = front->next;
if (front == NULL)
rear = NULL;
delete temp;
}

int peek() {
if (front == NULL)
return -1;
return front->data;
}

bool isEmpty() {
return front == NULL;
}

void display() {
Node* temp = front;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

✅ Summary: Stack vs Queue

Feature Stack (LIFO) Queue (FIFO)
Insert Push (Top) Enqueue (Rear)
Remove Pop (Top) Dequeue (Front)
Access Only Top Only Front
Use Cases Recursion, Undo, Parsing Scheduling, Queues, Buffers