LESSON 1 – Introduction to Data Structures

Learning Outcomes

At the end of this lesson, the student should be able to:

➤ Understand the basic data structures
➤ Learn the classification of data structures
➤ Develop their own program using data structures
➤ Convert the program into algorithm, pseudo codes and flowchart

Introduction – Before introducing data structures we should understand that computers do

store, retrieve, and process a large amount of data if the data is stored in well organized way
on storage media and in computer's memory then it can be accessed quickly for processing
that further reduces the latency and the user is provided fast response.

Data structure – refers to a scheme for organizing data, or in other words a data structure is
an arrangement of data in computer's memory in such a way that it could make the data
quickly available to the processor for required calculations. A data structure should be seen
as a logical concept that must address two fundamental concerns. First, how the data will be
stored, and second, what operations will be performed on it? As data structure is a scheme
for data organization so the functional definition of a data structure should be independent of
its implementation.

Example:
A calculator app stores previous results in memory using a list, allowing you to recall or redo
operations.

Easy Example:
Like keeping tools in a toolbox where each type has its own section—so you find what you
need fast.

[Wrenches] [Hammers] [Screwdrivers]

—
Two Main Concerns of a Data Structure:

1. How will the data be stored? (e.g., list, stack, queue)

2. What operations will be performed on it? (e.g., add, delete, search)

Example:
In a music player, songs are stored in a queue so they play one after another.

Easy Example:
Like lining up songs in a playlist:

[Song 1] → [Song 2] → [Song 3]

---
Independent of Implementation:

1
The concept of a data structure focuses on what it does, not how it's coded. The logic
remains the same even in different programming languages.

Example:
A stack works the same whether coded in Java, Python, or C++.

Easy Example:
Like playing the same game on different consoles—rules stay the same, just different
controllers.

ADT (Abstract Data Type) – The functional definition of a data structure is known as ADT
(Abstract Data Type) which is independent of implementation. The Implementation part is left
on developers who decide which technology better suits to their project needs.

Example:
A Stack ADT lets you push and pop items (like undo actions), but doesn’t say whether it’s
built using an array or linked list.

Easy Example:
Like describing a vending machine:

●​ You insert a coin

●​ Select a snack
●​ Get the item

Data Structure – is specialized format to store and organized data in a computer's memory
or disk.

Example:
An array stores a list of student names in a fixed order in memory.

Easy Example:
Like putting books in numbered shelves so you know exactly where each book is.

Visual:

Computer Memory:
[0] → "Anna"
[1] → "Ben"
[2] → "Cara"
(Data stored in organized, accessible format)

Data structure – is also a collection of variables, possibly of several different data types
connected in various ways.

Example:
A structure (or record) that stores a student’s name (string), age (integer), and grade (float)
together.

2
Easy Example:
Like a folder that holds a student’s ID, photo, and report card—different types of information
grouped together.

Visual:

Student Record:
{
Name: "Lena" → [Text]
Age: 18 → [Number]
Grade: 89.5 → [Decimal]
}
(A collection of different data types stored together)

Data structures – can be broadly classified in two categories linear structures and
hierarchical structures. Arrays, linked lists, stacks, and queues are linear structures, while
trees, graphs, heaps etc. are hierarchical structures.
– Every data structure has its own strengths, and weaknesses. Also, every data structure
specially suits to specific problem types depending upon the operations performed and the
data organization. For example, an array is suitable for read operations. Following is a quick
introduction to important data structures.

Example:
Test scores like 85, 92, 78 before calculating the average.

Easy Example:
Like ingredients (flour, sugar, eggs) before baking a cake—they're raw and unprocessed.

Visual:

Raw Data:
[85] [92] [78]

→ Processing → Result: Average = 85

Structure – refers to the way in which the parts of a system or object are arranged or
organized, or a system arranged in this way.

Types of Data Structures

1. Array

Example:
Stores a list of exam scores: [85, 90, 78, 92]

Easy Example:
Like numbered lockers—each item has a fixed position.

3
Visual:

Index: 0 1 2 3
Data: 85 90 78 92

2. Linked List

Example:
A dynamic list of names: Anna → Ben → Cara → Dave

Easy Example:
Like a train, where each coach links to the next.

Visual:

[Anna] → [Ben] → [Cara] → [Dave] → null

3. Stacks

Example:
Used in undo actions: Action3 → Action2 → Action1

Easy Example:
Like stacking plates—last in, first out (LIFO).

Visual:

Top → [Action3]
[Action2]
[Action1]

4. Queues

Example:
Printer jobs line: Job1 → Job2 → Job3

Easy Example:
Like a line at a cashier—first in, first out (FIFO).

Visual:

Front → [Job1] → [Job2] → [Job3] → Rear

5. Trees

Example:
Represents folder structure in a file system.

4
Easy Example:
Like a family tree with parent-child relationships.

Visual:

Root
/ \
Left Right
/ \
Child1 Child2

6. Hash Tables

Example:
Stores key-value pairs: {"ID101": "Anna", "ID102": "Ben"}

Easy Example:
Like a dictionary—you look up a word (key) to get its meaning (value).

Visual:

Key → Value
"ID101" → "Anna"
"ID102" → "Ben”

Data Types – These are the data that a variable can hold in a programming language, that
we need to determine the type of data which is being stored into the memory of the
computer.
– All programming languages have a set of built-in data types

Example:
int age = 18; → The variable age holds an integer type.

Easy Example:
Like choosing the right container for what you’re storing: use a bottle for water, a box for
shoes.

Visual:

Data Types:
- int → 123 (whole number)
- float → 12.5 (decimal number)
- char → 'A' (single letter)
- string → "Hello" (text)
- bool → true/false (yes or no)

5
Abstract Data Types – The specification of a set of data and set of operations performed in
a data. The storage for data defined in terms of set of operations to be performed on the
data.

Example:
A Queue ADT defines operations like enqueue, dequeue, and peek, without saying how it's
stored.

Easy Example:
Like a remote control—you know what buttons do (volume up, channel change), but not how
it works inside.

Visual:

ADT Focuses On:

✔ What you can do:
- add(item)
- remove(item)
- view(item)

✖ How it's done (implementation is hidden)

Algorithms – It is a finite set of instructions that specify a sequence of operations to be

carried out. It is a recipe for solving a problem. All the tasks that can be carried out by a
computer can be stated as algorithms.

Example:
An algorithm to sort numbers from smallest to largest (e.g., bubble sort).

Easy Example:
Like a recipe for baking a cake—step-by-step instructions to get the final result.

Visual:

Algorithm = Step-by-step instructions

Example:
1. Apply to wet hair
2. Massage gently
3. Leave on for a few moments
4. Rinse off

Criteria for Algorithm – Every algorithm must satisfy the following criteria:
1. Input – zero or more quantities are externally supplied.

Example:
Accepting two numbers from a user.

6
Easy Example:
Like a recipe needing ingredients before cooking.

Visual:

Input → [5, 3]

2. Output – At least one quantity is produced.

Example:
Produces the sum of two numbers.

Easy Example:
Like the finished cake from following a recipe.

Visual:

Output → [8]

3. Definiteness – each instruction must be clear and unambiguous

Example:
“Add A and B” is clear; “Maybe add A” is not.

Easy Example:
Like step-by-step instructions that make sense (not “Do something cool”).

Visual:

Clear: Add 2 + 3
Unclear: Add something to something

4. Finiteness – all instructions of an algorithm will terminate after a finite number of steps.

Example:
The algorithm must stop after a number of steps.

Easy Example:
Like a game with an end—no infinite play.

Visual:

Start → Step 1 → Step 2 → ... → End

5. Effectiveness – each operation must be definite, but must also be feasible.

Example:
Each step must be doable (e.g., basic math operations).

7
Easy Example:
Like using tools and steps you actually have at home to cook.

Visual:

✔ Possible: Divide 10 by 2
✘ Not Possible: Divide 10 by a unicorn

Inputs – These are the data items presented to the algorithms. An algorithm has either no
input or a predetermined number of them.

Example:
An algorithm that calculates the sum of two numbers takes num1 and num2 as inputs.

Easy Example:
Like giving ingredients to a recipe—flour and eggs go in first.

Visual:

Inputs:
num1 = 5
num2 = 10

→ Algorithm → Output: 15

Outputs – These are data items presented to the outside world as the result of the
execution of a program based on the algorithms. An algorithm ought to produce a least one
output.

Example:
After adding two numbers, the algorithm gives the result 15 as output.

Easy Example:
Like the cake you get after following a recipe—the final result.

Visual:

Inputs: 5 + 10
→ Algorithm →
Output: 15

Procedures – These are essential tool in programming that generalizes the notion of an
operator. These are used to encapsulate parts of an algorithm by localizing in one section of
a program all the statements relevant to a certain aspect of a program.

Example:
A procedure named calculateTotal() contains all the steps to compute a bill.

8
Easy Example:
Like a mini-recipe inside a cookbook—you use it every time you need to bake the same
cake.

Visual:

Main Program
↓
[Procedure: calculateTotal()]
- Add prices
- Apply tax
- Return total

Data Structures and Algorithms

• Raw data – is an input to a computer and an algorithm is used to transform this into a
refined data.

Example:
Raw scores: 80, 85, 90 → Algorithm calculates the average → Output: 85

Easy Example:
Like turning raw vegetables into a cooked dish using a recipe.

Visual:

Raw Data (Input): [80, 85, 90]

→ Algorithm →
Refined Data (Output): Average = 85

Computer Science – also refers to the study of data which includes the following:
1. Machines that holds data

Example:
Computers, servers, smartphones that store and process information.

Easy Example:
Like a cabinet that holds all your documents.

Visual:

PC | Phone | Cloud
(Devices where data lives)

2. Languages for describing data manipulation

Example:
Programming languages like Python, C++, Java used to process data.

9
Easy Example:
Like using a recipe to tell someone how to cook a meal.

Visual:

Python: total = a + b
C++: int total = a + b;

3. Foundations which describe what kinds of refined data can be produced from raw
data

Example:
Algorithms and logic define what outputs can be generated from inputs.

Easy Example:
Like knowing that mixing flour + water = dough, but not cake yet.

Visual:

Input → [Logic & Rules] → Valid Output

(Only certain results are possible)

4. Structures for representing data

Example:
Using arrays, trees, graphs to store data logically.

Easy Example:
Like organizing files into folders and subfolders.

Visual:

Data
├── Images
├── Documents
└── Videos

Pseudo Codes – It is a textual presentation of a flowchart

•Close to a natural languages
•The control structures impose the logic
–It may become part of the program documentation
–It could be translated into a program.

Example:

Start
Set total = 0

10
For each number in the list:
Add number to total
Display total
End

Easy Example:
Like writing cooking steps in simple words before turning them into real code.

Visual:

Pseudocode:
- Looks like plain English
- Shows logic, not syntax
- Can be turned into real code

Example:
IF score > 75
PRINT "Passed"
ELSE
PRINT "Failed”

Stepwise Refinement – The process by which a programmer refines an initial idea to a

problem's solution into more specific terms. It is the phase of refinement results in a program
ready to be coded for execution.

Example:
Start with: “Calculate student average”
Refine to:

1. Input 3 grades

2. Add grades

3. Divide by 3

4. Display result

Easy Example:
Like planning a trip:
Start with “Go to Baguio” → Then plan transportation, budget, stops, etc.

Visual:

11
Initial Idea: Calculate average
↓
Step 1: Get inputs
↓
Step 2: Add values
↓
Step 3: Divide total
↓
Final Step: Show average
→ Program Ready to Code

Analysis of Algorithms – It determines the amount of resources necessary to execute it

such as time and storage. It is usually in terms of Central Processing Unit time and memory
requirements.

Example:
Comparing two sorting algorithms to see which one runs faster and uses less memory.

Easy Example:
Like choosing the fastest and most fuel-efficient route on Google Maps.

Visual:

Analysis Measures:
- Time (CPU time)
- Space (Memory used)

Goal: Find the most efficient solution

Analysis of Algorithms
1. Best – case analysis

Example:
Searching for the first item in a list — found immediately.

Easy Example:
Like finding your keys right where you left them.

Visual:

Best Case → Fastest possible outcome

Steps: Minimum

2. Worst – case analysis

Example:
Searching for an item that's not in the list — you check every element.

12
Easy Example:
Like checking every drawer in your house before finding your keys.

Visual:

Worst Case → Slowest/most steps

Steps: Maximum

3. Average – Case analysis

Example:
On average, you find the item after checking half the list.

Easy Example:
Like usually finding your keys in the 3rd out of 6 drawers.

Visual:

Average Case → Expected performance

Steps: Between best and worst

Example:

Problem:
Create an algorithm, pseudo codes and flowchart that will determine if the number if positive
or negative numbers. If the number is greater than zero display positive, otherwise display
negative.

Algorithm
1. Input number from the keyboard
2. Create condition
3. Display the result

Pseudo Codes
Enter number from the keyboard.
If the number is positive then
print positive
otherwise
print negative

Flowchart

13
Problem:
Create a program that will input grades for prelim, midterm and final and compute their final
average. Determine if the final average is greater than 75 then print Passed otherwise print
Failed. Convert it into, algorithm, pseudo codes and flowchart. Submit your activity within this
week once you finished studying the lesson.

1. Algorithm
1. Start
2. Input Prelim Grade
3. Input Midterm Grade
4. Input Final Grade
5. Compute Average = (Prelim + Midterm + Final) / 3
6. If Average >= 75, then display "Passed"
7. Else, display "Failed"
8. End

2. Pseudo Code

14
Start
Input Prelim
Input Midterm
Input Final
Set Average = (Prelim + Midterm + Final) / 3
If Average >= 75 Then
Display "Passed"
Else
Display "Failed"
End If
End

3. Flowchart Description

You can draw this using flowchart symbols:

Terminator (oval) for Start and End

Parallelogram for Input and Output

Rectangle for Process (like computing average)

Diamond for Decision (checking if average ≥ 75)

Flow:

[Start]
↓
[Input Prelim]
↓
[Input Midterm]
↓
[Input Final]
↓
[Compute Average = (Prelim + Midterm + Final) / 3]
↓
┌───────────────────────────────────┐
│ Is Average >= 75? │
└───────────────────────────────────┘
↓Yes ↓No
[Display "Passed"] [Display "Failed"]
↓ ↓
[End]

15
4. Sample Code (Python)

# Input grades
prelim = float(input("Enter Prelim Grade: "))
midterm = float(input("Enter Midterm Grade: "))
final = float(input("Enter Final Grade: "))

# Compute average
average = (prelim + midterm + final) / 3

# Output result
print(f"Average: {average:.2f}")
if average >= 75:
print("Passed")
else:
print("Failed")

LESSON 2 – Array & Linked List Concepts

Learning Outcomes

At the end of this lesson, the student should be able to:

➤ Introduce the array concepts
➤ Discuss the types and function of Array
➤ Discuss the Linked Concept
➤ Create a program that will apply array and linked list concept

Array – is a container which can hold a fix number of items and these items should be of the
same type. Most of the data structures make use of arrays to implement their algorithms.

Example:
An array to store 5 test scores: [85, 90, 78, 92, 88]

Easy Example:
Like a row of egg cartons—each slot holds one egg of the same kind.

Visual:

Array (Same Type, Fixed Size):

Index: 0 1 2 3 4
Data: 85 90 78 92 88

Following are the important terms to understand the concept of Array:

Element – Each item stored in an array is called an element.

Example:
In the array [10, 20, 30], the values 10, 20, and 30 are elements.

16
Easy Example:
Like individual books placed on a shelf.

Visual:

Array: [10] [20] [30]

Element: ↑ ↑ ↑

Index – Each location of an element in an array has a numerical index, which is used to
Identify the element.

Example:
In [10, 20, 30], 10 is at index 0, 20 at index 1, and so on.

Easy Example:
Like shelf numbers used to find the exact position of each book.

Visual:

Index: 0 1 2
Array: [10] [20] [30]

Array Representation – Arrays can be declared in various ways in different languages. For
illustration, let's take Java array declaration.

Example:
In Java, an array can be declared and initialized like this:

int[] scores = {85, 90, 78, 92};

Easy Example:
Like saying: "I want 4 boxes to store test scores" — and placing numbers inside them.

Visual:

Java Array Representation:

int[] scores = {85, 90, 78, 92};

Index: 0 1 2 3
Scores: [85] [90] [78] [92]

As per the above illustration, following are the important points to be considered:
• Index starts with 0.
• Array length is 10 which means it can store 10 elements.
• Arrayfruits[5]:
• Arrayfruits= ("Apple", "papaya", "atis", "santol", "mango")
• Arrayfruits[0];

17
• Each element can be accessed via its index. For example, we can fetch an element at
Index 6 as 9.

Basic Operations
Following are the basic operations supported by an array:
1. Traverse – print all the array elements one by one.

Example:
Printing elements of fruits[] = {"Apple", "Mango", "Banana"} from index 0 to 2.

Easy Example:
Like reading all the names on your class list one by one.

Visual:

Index: 0 1 2
Array: [Apple] [Mango] [Banana]

2. Insertion – Adds an element at the given index.

Example:
Insert "Orange" at index 1 → {"Apple", "Orange", "Mango"}

Easy Example:
Like putting a new book in between two books on a shelf.

Visual:

Before Insertion: [Apple] [Mango]

After Insertion: [Apple] [Orange] [Mango]
Index: 0 1 2

3. Deletion – Deletes an element at the given index.

Example:
Remove the element at index 1 from {"Apple", "Orange", "Mango"} → {"Apple", "Mango"}

Easy Example:
Like removing a sandwich from the middle of your lunchbox.

Visual:

Before Deletion: [Apple] [Orange] [Mango]

After Deletion: [Apple] [Mango]
Index: 0 2

4. Search – Searches an element using the given index or by the value.

18
Example:
Find "Mango" in {"Apple", "Mango", "Banana"} → Found at index 1

Easy Example:
Like finding your name in the attendance list.

Visual:

Array: [Apple] [Mango] [Banana]

Index: 0 1 2
Search: "Mango" is at index 1

5. Update – Updates an element at the given index.

Example:
Change index 2 value from "Banana" to "Grapes" → {"Apple", "Mango", "Grapes"}

Easy Example:
Like correcting a misspelled word in your school project.

Visual:

Before: [Apple] [Mango] [Banana]

Update: arr[2] = "Grapes"
After: [Apple] [Mango] [Grapes]
Index: 0 1 2

Types of Data Structure

1. Arrays

Example:
int nums[5] = {10, 20, 30, 40, 50};
nums[2] would access the value 30.

Easy Example:
Like a row of mailboxes numbered 0 to 4, each containing one item. To get the third letter,
you open box 2.

Visual:

Index: 0 1 2 3 4
[10] [20] [30] [40] [50]

2. Linked List

Example:
Node1 → Node2 → Node3 → NULL

19
Easy Example:
Like a treasure map where each clue (node) points to the next location (next node).

Visual:

[Data|Next] → [Data|Next] → [Data|NULL]

2.1 Simple linked List

Example:
Node1 → Node2 → Node3 → NULL

Easy Example:
Like a treasure map where each clue (node) points to the next location (next node).

Visual:

[Data|Next] → [Data|Next] → [Data|NULL]

2.2 Linked List with its Dummy node

Example:
Dummy → Node1 → Node2 → NULL

Easy Example:
Like having a starting “marker” before the first real station on a train line.

Visual:

[Dummy|Next] → [Data|Next] → [Data|NULL]

2.3 Array Implementation with Linked List

Example:
Use two arrays: one for data, one for “next” pointers.

Easy Example:
Like having a list of items in one column and directions to the next in another.

Visual:

Data: [A] [B] [C]

Next: 1 2 -1

3. Stacks

Example:
Push 10, Push 20, Pop → you get 20.

20
Easy Example:
Like stacking books: you take off the top book first.

Visual:

Top → [30]
[20]
[10]

4. Queues

Example:
Enqueue 10, Enqueue 20, Dequeue → you get 10.

Easy Example:
Like people lining up at a counter—first come, first served.

Visual:

Front → [10] → [20] → [30] → NULL

↑

Arrays – are statically implemented data structures by some programming languages like C
and C++; hence the size of this data structure must be known at compile time and cannot be
altered at run time. But modem programming languages, for example, Java implements
arrays as objects and give the programmer a way to alter the size of them at run time. Arrays
are the most common data structure used to store data.

Example:

In C:

int numbers[5] = {1, 2, 3, 4, 5};

– You cannot add a 6th element later.

In Java:

int[] numbers = new int[5];

numbers = new int[10]; // Resizing is allowed

Easy Example:

Imagine buying a tray with 5 egg slots.

In C/C++, once you buy it, you can’t change it.
In Java, it’s like having a flexible tray that you can stretch to hold more eggs later.

21
Visual:

C/C++ (Fixed Size):

Index: 0 1 2 3 4
[1] [2] [3] [4] [5]

Java (Resizable):
Initial: [1] [2] [3] [4] [5]
Resize → [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Arrays – are unarguably easier data structures to use and access. But inserting an item to
an array and deleting it from the array are situation dependent. if you want to insert an item
at a particular position which is already occupied by some element then you have to shift all
items one position right from the position new element has to be inserted then insert the new
item. The time taken by insert operation is depend on how big the array is, and at which
position the item is being inserted. The same is true about deletion of an item.

Example:

Original Array:
[10, 20, 30, 40]

Insert 25 at index 2:
Shift 30 and 40 → [10, 20, 25, 30, 40]

Delete at index 1:
Remove 20 and shift others → [10, 25, 30, 40]

Easy Example:

It’s like adding a book in the middle of a full bookshelf:

→ You need to move the books on the right to insert the new one!

Visual:

Insert 25 at index 2

Before:

Index: 0 1 2 3
Array: [10][20][30][40]

After shifting:

Index: 0 1 2 3 4
Array: [10][20][25][30][40]

Delete at index 1

22
Before:

Index: 0 1 2 3
Array: [10][20][25][30]

After deletion:

Index: 0 1 2
Array: [10][25][30]

Arrays – If the array is unsorted then search operation is also proved costly and takes O(N)
time in worst case, where N is size of the array. But if the array is sorted then search
performance is improved magically and takes O(logN) time in worst case.

Example:

Unsorted Array:
[42, 17, 8, 91, 33]
Searching for 91: you may have to look at every element.

Sorted Array:
[8, 17, 33, 42, 91]
You can perform binary search — check the middle value, then eliminate half each time.

Easy Example:

Unsorted: Like looking for your keys in a messy room — you check every spot.

Sorted: Like looking for a word in a dictionary — you skip pages smartly using alphabetical
order.

Visual:

Unsorted Array (Linear Search)

[42][17][8][91][33] → Check one by one → Found at index 3

Time: O(N)

Sorted Array (Binary Search)

[8][17][33][42][91]

Step 1: Check middle → 33

Step 2: 91 is greater → go right → 42
Step 3: 91 is greater → go right → 91 → Found

23
Time: O(log N)

Two Types of Array

1. Single Array – A list of elements stored in a single row. Each element is accessed using
a single index.

Example:

Marks[5] = [89, 78, 92, 84, 75]

Marks[0] = 89

Easy Example: Think of a train with several coaches (each coach holds one item).

Visual:

Index → 0 1 2 3 4
Marks → [89][78][92][84][75]

2. Two Dimensional Array – A table or matrix-like structure with rows and columns. Each
element is accessed using two indices.

Example:

Matrix[2][3] = [
[1, 2, 3],
[4, 5, 6]
]
Matrix[1][2] = 6

Easy Example:
Like a chessboard — rows and columns, and each square has something.

Visual:

Matrix:
Col0 Col1 Col2
Row0 → [ 1 ][ 2 ][ 3 ]
Row1 → [ 4 ][ 5 ][ 6 ]

24
Problem 1: Student Grades Average

Scenario: Create a program that accepts the grades of 5 students and computes the
average grade

Activity:
1. Declare an array to store 5 grades.
2. Ask the user to input each grade.
3. Compute and display the average.

25
Problem 2: Sales of Products

Scenario: A store sells 3 products. Each product's sales are recorded over 4 weeks. Create
a program that stores this data in a 2D array and computes the total sales per product and
total sales per week.

Activity:
1. Use a 2D array sales[3][4] for 3 products x 4 weeks.
2. Fill in the array using user input.
3. Display:

•Total sales per product

•Total sales per week

26
Activity 3: Reverse an Array (1D)

Task: Ask user for 5 numbers, store them in an array, and print them in reverse order.

import java.util.Scanner;

public class Activity3_ReverseArray {

27
 public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] numbers = new int[5];

// Input 5 numbers
System.out.println("Enter 5 numbers:");
for (int i = 0; i < 5; i++) {
System.out.print("Number " + (i + 1) + ": ");
numbers[i] = scanner.nextInt();
}

// Print in reverse order

System.out.println("Reversed order:");
for (int i = 4; i >= 0; i--) {
System.out.println(numbers[i]);
}

scanner.close();
}
}

Activity 4: Search in 2D Array

Task: Ask the user for a number, then search if it exists in a 3x3 matrix

import java.util.Scanner;

public class Activity4_Search2DArray {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] matrix = new int[3][3];

// Input 3x3 matrix

System.out.println("Enter 9 numbers for the 3x3 matrix:");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.print("Element [" + (i + 1) + "][" + (j + 1) + "]: ");
matrix[i][j] = scanner.nextInt();
}
}

// Input number to search

System.out.print("Enter number to search: ");
int search = scanner.nextInt();

// Search the matrix

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

28
 for (int j = 0; j < 3; j++) {
if (matrix[i][j] == search) {
found = true;
break;
}
}
if (found) break;
}

// Display result
if (found) {
System.out.println("Number Found");
} else {
System.out.println("Number Not Found");
}

scanner.close();
}
}

Linked List – Linked list data structure provides better memory management than arrays.
Because linked list is allocated memory at run time, so, there is no waste of memory.
Performance wise linked list is slower than array because there is no direct access to linked
list elements.

Example:

Let’s say we store names using a linked list:

[“Ana”] → [“Ben”] → [“Cai”] → NULL

Each box contains a name and a link to the next.

Easy Example:

Imagine a treasure map, where each clue leads you to the next spot. You can't jump
ahead—you have to follow one by one.

Visual:

+------+ +------+ +------+ +------+

| Ana | --> | Ben | --> | Cai | --> | NULL |
+------+ +------+ +------+ +------+
(head) (next) (next) (end)

Linked list – is proved to be a useful data structure when the number of elements to be
stored is not known ahead of time.

29
Example:

A music playlist where you keep adding songs while listening. You don’t know how many
songs you’ll add, but you can always insert a new song at any point.

Easy Example:

Imagine a growing train—you can keep adding more train cars anytime, one after another,
without needing to know how long the train will be.

Visual:

+---------+ +---------+ +---------+

| Song 1 | --> | Song 2 | --> | Song 3 | --> NULL
+---------+ +---------+ +---------+

There are many flavors of linked list you will see: linear, circular, doubly, and doubly circular.

30
Activities:

1. Rearranging

31
1.1 ALGORITHM → MHTIROGLA

(Reverse the letters)

Before:

A → L → G → O → R → I → T → H → M → NULL

After:

M → H → T → I → R → O → G → L → A → NULL

1.2 DATA STRUCTURE → STRUCTURE DATA

(Swap the words)

Before:

DATA → STRUCTURE → NULL

After:

STRUCTURE → DATA → NULL

2. Insertion

2.1 Insert "INFORMATION" after "COMPUTER"

Before:

COMPUTER → TECHNOLOGY → NULL

After:

COMPUTER → INFORMATION → TECHNOLOGY → NULL

2.2 Insert "ANALYSIS" after "ALGO"

Before:

ALGO → RITHM → NULL

After:

ALGO → ANALYSIS → RITHM → NULL

3. Deletion

32
3.1 Delete "LOGY" from "COMPUTER TECHNOLOGY"

(Remove "LOGY" in "TECHNOLOGY")

Before:

COMPUTER → TECHNOLOGY → NULL

After:

COMPUTER → TECHNO → NULL

3.2 Delete "THM" from "ALGORITHM"

Before:

A → L → G → O → R → I → T → H → M → NULL

After:

A → L → G → O → R → I → NULL

Assignment:
Give and draw your own 5 examples of Rearranging, Insertion and Deletion Operations.
Write it in 1 whole bond paper long or MSWord

Assignment: Data Structure Operations

Name: [Your Name]

Subject: Computer Programming
Topic: Rearranging, Insertion, and Deletion Operations in Linked Lists
Date: [Today’s Date]

I. Rearranging (Reversing or Shuffling Order)

1.1

Before:
B → O → O → K → NULL
After:
K → O → O → B → NULL

1.2

Before:
M → A → T → H → NULL
After:
H → T → A → M → NULL

33
1.3

Before:
S → T → U → D → Y → NULL
After:
Y → D → U → T → S → NULL

1.4

Before:
F → R → U → I → T → NULL
After:
T → I → U → R → F → NULL

1.5

Before:
C → O → D → E → NULL
After:
E → D → O → C → NULL

II. Insertion (Add a New Node)

2.1

Insert "LOVE" after "I"

Before:
I → YOU → NULL
After:
I → LOVE → YOU → NULL

2.2

Insert "SUN" after "THE"

Before:
THE → BRIGHT → NULL
After:
THE → SUN → BRIGHT → NULL

2.3

Insert "HARDWORK" after "WITH"

Before:
SUCCESS → WITH → DEDICATION → NULL
After:
SUCCESS → WITH → HARDWORK → DEDICATION → NULL

34
2.4

Insert "IS" after "LIFE"

Before:
LIFE → BEAUTIFUL → NULL
After:
LIFE → IS → BEAUTIFUL → NULL

2.5

Insert "NOW" after "DO"

Before:
JUST → DO → IT → NULL
After:
JUST → DO → NOW → IT → NULL

III. Deletion (Remove a Node)

3.1

Delete "TIRED"
Before:
I → AM → TIRED → NOW → NULL
After:
I → AM → NOW → NULL

3.2

Delete "OLD"
Before:
DELETE → OLD → FILE → NULL
After:
DELETE → FILE → NULL

3.3

Delete "NOON"
Before:
MORNING → NOON → NIGHT → NULL
After:
MORNING → NIGHT → NULL

3.4

Delete "FAIL"
Before:
TRY → FAIL → TRY → NULL
After:

35
TRY → TRY → NULL

3.5

Delete "SAD"
Before:
BE → SAD → STRONG → NULL
After:
BE → STRONG → NULL

Problem 1: Manage To-Do List

Scenario: Create a simple task manager that allows the user to add, view, and remove tasks
using a LinkedList.

Activity:
•Use LinkedList<String> to store tasks.
•Display menu: Add task, Remove task, View all tasks, Exit.
•Implement input/output using Scanner.

36
37
Problem 2: Student Records (Manual Linked List)

Scenario: Build a manual linked list for storing student names. Allow insertion, deletion, and
display of nodes. Add 20 student records, delete 10 student records and view student
records. Write the output of this program in the provided box.

1. Filename: LinkListMain.java
package linkedlistmain;
import java.util.Scanner;
public class LinkedListMain
{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
StudentList list = new StudentList();
int choice;

do {
System.out.println("\n--- Student Linked List ---");
System.out.println("1. Add Student");
System.out.println("2. Delete Student");
System.out.println("3. View Students");
System.out.println("4. Exit");
System.out.print("Choose: ");
choice = input.nextInt();
input.nextLine();

switch (choice) {
case 1:
System.out.print("Enter student name: ");
list.add(input.nextLine());
break;
case 2:
System.out.print("Enter name to delete: ");
list.delete(input.nextLine());
break;
case 3:
System.out.println("Student List:");
list.display();
break;
case 4:
System.out.println("Exiting...");
break;
}
} while (choice != 4);
}
}
FileName: StudentList
package linkedlistmain;

38
class StudentList
{
Node head;

// Add student at end

public void add(String name) {
Node newNode = new Node(name);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
}
}

// Delete student by name

public void delete(String name) {
if (head == null) return;

if (head.data.equals(name)) {
head = head.next;
return;
}

Node temp = head;

while (temp.next != null && !temp.next.data.equals(name)) {
temp = temp.next;
}

if (temp.next != null) {
temp.next = temp.next.next;
}
}

// Display list
public void display() {
Node temp = head;
while (temp != null) {
System.out.println("- " + temp.data);
temp = temp.next;
}
}
}
Filename: Node.Java
package linkedlistmain;

39
class Node
{
String data;
Node next;

public Node(String data) {

this.data = data;
this.next = null;
}
}

Output:

LESSON 3 – Storage Allocation / Array With Implementation Of Linked List

Learning Outcomes

At the end of this lesson, the student should be able to:

➤ Define storage allocation
➤ Understand the key and next concept
➤ Determine how storage allocation works in arrays and linked lists
➤ Discuss the limitations of arrays and how linked lists overcome them
➤ Demonstrate the implementation of array behaviour using a linked list
➤ Create Real-world applications of these data structures

Introduction
Storage Allocation – In computer programming, storage allocation refers to how memory is
reserved for variables, data structures, and program instructions during program execution.
Efficient storage allocation is critical for performance, especially when managing large
amounts of data. Two primary structures for managing data in memory are arrays and linked
lists, each with its own characteristics, advantages, and trade-offs.

40
Example:

In C language:

int numbers[5]; // allocates memory for 5 integers

In Linked List (C-style):

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

Here, each node is dynamically allocated using malloc().

Easy Example:

Imagine a bookshelf:

An array is like a fixed shelf with 5 slots. You can't add more slots once it's built.

A linked list is like a flexible chain of book holders. You can always add more holders
anytime.

Visual:

Array (Fixed Allocation):

+-------+-------+-------+-------+-------+
| 10 | 20 | 30 | 40 | 50 |
+-------+-------+-------+-------+-------+
Index: 0 1 2 3 4

Memory is reserved all at once.

You must know size ahead of time.

Linked List (Dynamic Allocation):

[10] -> [20] -> [30] -> [40] -> [50] -> NULL

Memory is reserved as needed.

You can add or remove nodes anytime.

Array – is a collection of elements stored in contiguous memory locations. It allows fast

access to elements using an index but has a fixed size, which limits flexibility. Arrays require

41
memory to be allocated at compile time or dynamically in a single block, and inserting or
deleting elements especially in the middle can be costly in terms of performance.

Example:

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

// Access: arr[2] = 30

Easy Example:

Think of an egg tray with 6 slots:

You can grab the 3rd egg instantly (like arr[2]).

But if you want to insert a new egg in the middle, you need to shift all the others.

Visual:

+------+------+------+------+------+
| 10 | 20 | 30 | 40 | 50 |
+------+------+------+------+------+
Index: 0 1 2 3 4

Insertion Example (Insert 25 at index 2):

Shift elements to the right → costly.

Before: [10, 20, 30, 40, 50]

After: [10, 20, 25, 30, 40]

Linked list – is a linear data structure where elements, called nodes, are stored in
non-contiguous memory locations. Each node contains data and a pointer (or reference) to
the next node. This structure allows dynamic memory allocation, meaning nodes can be
added or removed easily at runtime without the need to shift elements, making it more
flexible than arrays in many situations.

Example (Java-style):

class Node {
int data;
Node next;

Node(int value) {
data = value;
next = null;
}
}

42
You can then link them like:

Node head = new Node(10);

head.next = new Node(20);
head.next.next = new Node(30);

Easy Example:

Imagine a necklace made of beads:

Each bead has a string that ties to the next bead.

You can add or remove a bead anywhere without touching all of them.

Visual:

[10] → [20] → [30] → null

Each box is a Node

Arrows (→) show the next reference

null means end of the list

– By implementing arrays using linked lists (such as in dynamic array implementations or

array-like access through linked structures), programmers can combine the advantages of
both structures such as the dynamic nature of linked lists and the indexed access style of
arrays. This hybrid approach helps manage memory more effectively, especially when
dealing with unpredictable or frequently changing data sizes.

Example (Java-style):

class ArrayNode {
int data;
ArrayNode next;

ArrayNode(int value) {
data = value;
next = null;
}
}

class LinkedArray {
ArrayNode[] array = new ArrayNode[10]; // array of linked list nodes
}

43
Easy Example:

Imagine you’re building a bookshelf:

You want to access each book by position (like an array)

But you also want to easily add or remove books (like a linked list)

So you make each shelf adjustable, and use slots to hold linked books

Visual:

Index: 0 1 2 3 4
↓ ↓ ↓ ↓ ↓
[10] → [20] [null] [30] → [40]

Array index points to linked nodes

Each node can store or link more data

Combines index access with dynamic size

Definition of Terms
1. Storage allocation – It is a place for storing information

Example: In Java, when you declare int[] numbers = new int[5];, the memory is allocated for
5 integers in an array.

Easy Example: Think of a drawer with 5 sections to put papers. Each section is a storage
space for one paper.

Visual:

[ _ ][ _ ][ _ ][ _ ][ _ ] ← 5 storage slots in memory

2. Key [Next [head]] – refers to the information associated with the first item on the list

Example:

class Node {
int key;
Node next;
}
Node head = new Node();
head.key = 10;
head.next = new Node();

44
Accessing: head.key gives 10 → Key[Next[head]]

Easy Example: Imagine a train: the engine is head, and the value (number) it carries is the
key.

Visual:

[Head] → [10] → [ ]
3. Key[next[next[head] ]] – refers to the second item on the list.

Example:

Node head = new Node();

head.key = 10;
head.next = new Node();
head.next.key = 20;
head.next.next = new Node();
head.next.next.key = 30;

Accessing: head.next.next.key gives 30 → Key[next[next[head]]]

Easy Example: In the train, if the engine is head, the third coach holds the third value.

Visual:

[Head] → [10] → [20] → [30]

↑ ↑
next next[next]

4. Parallel arrays – the structure can be built "on top of the data

Example:

String[] names = {"Anna", "Ben", "Carl"};

int[] ages = {18, 20, 22};
// names[0] = "Anna" and ages[0] = 18 are related

Easy Example: Two lists, one for student names, another for their scores. The 1st student's
name is in names[0], and their score is in scores[0].

Visual:

45
Names: [ "Anna" ][ "Ben" ][ "Carl" ]
Ages : [ 18 ][ 20 ][ 22 ]
↑ ↑ ↑
index 0 index 1 index 2

5. Key – contains the data

Example:

Node node = new Node();

node.key = 5; // 5 is the key or the data

Easy Example: A note card with a number written on it. That number is the key.

Visual:

[ Key = 5 ]

6. Next – All the structure in the parallel array.

Example:

node.next = new Node(); // Link to next node

Easy Example: In a chain of paperclips, each paperclip is a node, and the part connecting to
the next clip is the next.

Visual:

[5] → [10] → [15] → null

↑ ↑ ↑
key next next

Given:

Position 0 = Head

1=Z

Since next(0) is 4, key [4] (A)

Next [4] is 3, key [3] (L)

Insert SLA after head; I after L and

46
Insert T after S.

INSTRUCTIONS:

47
INSTRUCTIONS: (7 DISTINCT LETTERS)
1. Insert PROJECT IN AN EMPTY LIST
2. Insert PROJ after Head
3. Insert E after R
4. Insert C after O
5. Insert T after J

48
Lesson3. Activities

Given ALGORITHM, Create your own instructions to design the storage allocation with array
linked list implementation.

Assignment

Think of 3 words with 5, 7 and 9 distinct letters of computer words. Create your own
instructions and storage allocation. MSWord

STORE

NETWORK

CUSTOMIZE

A. INSTRUCTIONS 1:

1. Insert ALGORITHM IN AN EMPTY LIST

2. INSERT ALGOR AFTER THE HEAD
3. INSERT I AFTER A
4. INSERT T AFTER L
5. INSERT HAFTER G
6. INSERT M AFTER O

49
https://beginnersbook.com/2013/12/how-to-loop-linkedlist-in-java/

50
Activity in Laboratory

Write a program using linked list to display the above examples like SLAIT, PROJECT and
ALGORITHM.

LESSON 4 – Stacks Data Structure

Learning Outcomes

At the end of this lesson, the student should be able to:

➤ Discuss the Stacks concept
➤ Differentiate push from pop operations of stacks
➤ Develop an application utilizing stacks data structure

INTRODUCTION
Stack – is a linear data structure which follows a particular order in which the operations are
performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out).

51
There are many real-life examples of a stack. Consider an example of plates stacked over
one another in the canteen. The plate which is at the top is the first one to be removed, i.e,
the plate which has been placed at the bottommost position remains in the stack for the
longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First
In Last Out) order.

Example:

In programming, when a function calls another function, and that function calls another, the
return happens in reverse order. This is managed using a stack.

Function C is called last → it finishes first and is removed first.

Function A is called first → it finishes last and is removed last.

Easy Example:

Think of a stack of plates in a cafeteria:

You put plates on top one by one.

You always take the topmost plate when you need one.

So:

Plate 1 → Bottom
Plate 2 → Middle
Plate 3 → Top → Removed first

Visual:

Stack (Top ↓ to Bottom):

52
[ Plate 3 ] ← Last In (removed first)
[ Plate 2 ]
[ Plate 1 ] ← First In (removed last)

Push operation → Add plate to the top

Pop operation → Remove plate from the top

Push – Adds an item in the stack. If the stack is full, then it is said to be an Overflow
condition.

Example:

Imagine a stack that can only hold 3 items.

Let’s push the values one by one:

1. Push(10) → [10]

2. Push(20) → [20, 10]

3. Push(30) → [30, 20, 10]

4. Push(40) → ❌ Overflow (Stack is full)

Easy Example:

Stack of boxes:

You keep placing boxes on top.

If the shelf can only hold 3, adding a 4th box will cause an overflow (it falls).

Visual:

Before Push(30): After Push(30):

[ ] [ 30 ] ← Top
[ 20 ] → [ 20 ]
[ 10 ] [ 10 ]

If you try Push(40) after this, it’s an Overflow 🚫

Pop – Removes an item from the stack. The items are popped in the reversed which they
are pushed. If the stack is empty, then it is said to be an Underflow condition.

Example:

53
Start with a stack:
[30, 20, 10] ← Top is 30

Pop() → Removes 30 → Stack becomes [20, 10]

Pop() → Removes 20 → Stack becomes [10]

Pop() → Removes 10 → Stack becomes []

Pop() → ❌ Underflow (Stack is already empty)

Easy Example:

Imagine a stack of books:

You remove (pop) books one by one from the top.

If there are no books left, and you try to remove one more, that’s an underflow.

Visual:

Before Pop(): After Pop():

[ 30 ] ← Top [ ]
[ 20 ] → [ 20 ]
[ 10 ] [ 10 ]

Keep popping and eventually:

[ ] ← Underflow (no more elements to pop!)

Peek or Top – Returns top element of stack.

Example:

Stack:
[30, 20, 10] ← Top is 30

Peek() → returns 30

Stack remains the same: [30, 20, 10]

Easy Example:

Think of a stack of plates:

You look at the top plate to see what it is (Peek),

But you don’t take it off.

54
Visual:

Stack:
[ 30 ] ← Top (Peek returns this)
[ 20 ]
[ 10 ]

After Peek:
[ 30 ]
[ 20 ] ← Nothing changed!
[ 10 ]

isEmpty – Returns true if stack is empty, else false.

Example:

1. Stack: []

isEmpty() → true

2. Stack: [10, 20]

isEmpty() → false

Easy Example:

Imagine a stack of books:

If there are no books → isEmpty says true

If there's even one book → isEmpty says false

Visual:

Empty Stack:

[ ] ← nothing here
↓
isEmpty() → true

Non-Empty Stack:

[ 20 ]
[ 10 ] ← has items

55
↓
isEmpty() → false

Stack lastElement() method in Java with Example.

Java.util.Stack.lastElement() – method in Java is used to retrieve or fetch the last element
of the Stack. It returns the element present at the last index of the Stack.

Example:

import java.util.Stack;

public class Main {

public static void main(String[] args) {
Stack<String> stack = new Stack<>();
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");

// Get the last (top) element

String last = stack.lastElement();
System.out.println("Last Element: " + last); // Output: Cherry
}
}

Easy Example:

Think of stacking plates:

You put Apple, then Banana, then Cherry on top.

lastElement() looks at the top plate (Cherry) without taking it off.

Visual:

Stack (Top → Bottom):

[ Cherry ] ← lastElement() returns this

[ Banana ]
[ Apple ]

Syntax – Stack.lastElement()

Parameters – The method does not take any parameter.

Example:

Stack<String> colors = new Stack<>();

56
colors.push("Red");
colors.push("Blue");

System.out.println(colors.lastElement()); // Output: Blue

⚠️ ❌
✅
> No need to write: colors.lastElement("Blue") →
Just write: colors.lastElement() →

Easy Example:

Think of saying:
“Show me the top plate”
You don’t give any plate name — you just ask to see the top one.

Visual:

Stack:
[ Blue ] ← lastElement()
[ Red ]

Call: colors.lastElement()
Output: "Blue”

Return Value – The method returns the last element present in the Stack.

Example:

Stack<Integer> numbers = new Stack<>();

numbers.push(5);
numbers.push(10);

int last = numbers.lastElement();

System.out.println(last); // Output: 10

> The last element added was 10, so that’s what it returns.

Easy Example:

Imagine a stack of books.

You say: “Tell me what the top book is.”
It tells you, but doesn't remove it.

Visual:

Stack:
[ 10 ] ← lastElement() returns this
[5 ]

57
Return Value: 10

Implementation Styles
1. Array-based (fixed size) – Use a fixed-size array plus a "top" index. Before pushing,
check for overflow: before popping, check for underflow Unstop.

Example:

Declare an array of size 5 and push elements using index tracking.

int[] stack = new int[5];

int top = -1;

stack[++top] = 10;
stack[++top] = 20;
stack[++top] = 30;

Easy Example:

Imagine stacking 5 plates in a tray. You can only put a plate on top, and remove from top.

Visual:

Stack size: 5
[30][20][10][ ][ ] ← Stack (top = 2)
↑
Top

2. Linked-list-based (dynamic) – Use a linked list, adding/removing nodes at the head.

This avoids fixed capacity limitations

Example:

Use a Node class and add/remove from the head.

class Node {
int data;
Node next;
Node(int value) {
data = value;
next = null;
}
}

Node top = null;

top = new Node(10);

top = new Node(20, top);

58
top = new Node(30, top);

Easy Example:

Imagine a chain of boxes where you always add a new box at the front.

Visual:

top → [30] → [20] → [10] → null

Stacks (Last in First Out)

1. Letters – represent information or data while

2. asterisk(") represents deletion operation

59
Example:

Given input:

60
ABC*D*E

Each letter is pushed onto the stack.

Each asterisk * means pop the top element.

Easy Example (Step-by-Step):

1. Push A → [A]

2. Push B → [A, B]

3. Push C → [A, B, C]

4. Pop (remove C) → [A, B]

5. Push D → [A, B, D]

6. Pop (remove D) → [A, B]

7. Push E → [A, B, E]

Final Stack:
A→B→E

Visual:

Operation Stack (Top at bottom)

-------------------------------
Push A A
Push B B
A
Push C C
B
A
Pop (*) B ← C removed
A
Push D D
B
A

61
Pop (*) B ← D removed
A
Push E E
B
A

ACTIVITY FOR LECTURE

1. DATA***STRUCT***URES_AND*****ALGORITHMS

2. INFORMATION TECHNOL*****OGY***

3. CUS***TOMI***ZING*** WIND****OWS**

Program 1:
// Java code to illustrate lastElement()
import java.util.*;

public class StackDemo {

public static void main(String args[]) {
// Creating an empty Stack
Stack<String> stack = new Stack<String>();

// Use add() method to add elements into the Stack

stack.add("Welcome");
stack.add("To");
stack.add("Geeks");
stack.add("4");
stack.add("Geeks");

// Displaying the Stack

System.out.println("Stack: " + stack);

// Displaying the last element

System.out.println("The last element is: " + stack.lastElement());
}
}

Program 2:
import java.util.*;

public class StackDemo {

public static void main(String args[]) {
// Creating an empty Stack
Stack<Integer> stack = new Stack<Integer>();

// Use add() method to add elements into the Stack

stack.add(10);

62
 stack.add(15);
stack.add(30);
stack.add(20);
stack.add(5);

// Displaying the Stack

System.out.println("Stack: " + stack);

// Displaying the last element

System.out.println("The last element is: " + stack.lastElement());
}
}

Hands-On Activity

1. Create a program that will input 10 different student names and display the last name that
you entered from the stack.

2. Create a program that will input 10 Even Numbers and display the first number that you
entered from the stack.

63