M2: Arrays and Dynamic Arrays

Prof. Justin David Pineda CISSP, CISM

Why Arrays Still Matter

• Used in almost all systems
• Fast access improves performance
• Improper use leads to inefficiency

Learning Objectives

• Understand memory layout
• Differentiate static vs dynamic arrays
• Analyze performance
• Apply to real-world systems

What is an Array?

• Collection of elements in contiguous memory
• Same data type
• Indexed structure

​

Example:

[10, 20, 30, 40]

Memory Layout

• Stored in contiguous memory
• Address = Base + (Index × Size)

Why Contiguous Memory Matters

• Better cache performance
• Predictable access
• Less fragmentation

Indexing Efficiency

• O(1) access time
• Direct computation

​

Example:

Access arr[3] instantly

Array Operations

• Access: O(1)
• Search: O(n)
• Insert: O(n)
• Delete: O(n)

​

For more information: Learn Big O notation in 6 minutes 📈

​

Insertion Cost

• Requires shifting elements
• Worst case: insert at beginning

Deletion Cost

• Requires shifting elements
• Maintains contiguous structure

Static Arrays

• Fixed size
• Allocated at compile time
• Not resizable

​

Example:

int arr[5];

​

Dynamic Arrays

• Resizable
• Allocated at runtime

​

Examples:

Python list

Java ArrayList

C++ vector

How Dynamic Arrays Work

• Start small
• Resize when full
• Copy elements to new array

Resizing Strategy

• Common approach: Double capacity

​

Example:

2 → 4 → 8 → 16

​

Why doubling?

• Reduces frequency of resizing
• Balances time and space

Amortized Cost

• Most inserts O(1)
• Occasional O(n)
• Average remains O(1)

Memory Trade-Off

• Extra unused memory
• Performance vs efficiency trade-off

When Arrays Fail

• Frequent insert/delete inefficient
• High resizing cost
• Memory allocation limits

Database Tables

• Rows often stored in array-like structures
• Columnar storage = optimized arrays

​

Example:

Indexing in SQL systems

Cache Storage

• Arrays used in:
• CPU cache
• LRU cache implementations

Packet Buffers

• Arrays store incoming packets
• Used in:
• Routers
• Firewalls
• IDS/IPS systems

​

Cyber Context:

• Buffer overflow vulnerabilities happen here

Security Insight

• Buffer overflow attacks
• Improper bounds checking
• Memory corruption

​

Example:

• Classic exploit vectors

Demo Example

• Array example
• Memory address
• Assigning values

Key Takeaways

• Fast access structure
• Dynamic arrays add flexibility
• Trade-offs exist

Knowledge Check (Recitation)

1. In your own words, what is an array and how is it stored in memory?
2. Give a simple real-life example (not technical) that is similar to how an array works.
3. Why can we access any element in an array quickly?
4. What is one key difference between a static array and a dynamic array?

5. What happens when a dynamic array becomes full?

6. Why is inserting an element in the middle of an array slow?

7. Give one real-world system (e.g., apps, banking, networking) where arrays are used.

8. What can go wrong if a program does not check the size or limit of an array?

Exercise 2: Arrays in Real-World Programs

Objective

• Apply your understanding of arrays by designing a simple program.

​

You will demonstrate:

• How arrays store multiple data
• How arrays are used in processing
• How results are generated from array data

What You Will Create

• Input → What data is entered
• Process → How the array is used
• Output → What the program displays

Simple pseudocode or code snippet

Exercise 2: Instructions

Choose ONE (1) scenario and design a simple program.

Your answer should include:

• Input
• What data will the user enter?
• Process / Logic
• How will you use the array?
• Output
• What will the program show?
• Code / Pseudocode
• Show a short example using arrays

Important Reminders

• Keep it simple and clear
• Focus on how arrays are used
• No need for perfect syntax

Exercise 2: Scenarios

1. Class Record (Grading Sheet)
2. Daily Sales Tracker
3. Attendance Checker
4. Quiz Scores Analyzer
5. Inventory of Supplies
6. Monthly Expense List
7. Packet Size Monitor
8. Temperature Monitoring Log

Exercise 2: Sample Answer Scenario 1

​

START

Input n

​

Create array names[n]

Create array grades[n]

Set total = 0

Set highest = 0

​

For i = 0 to n - 1

Input names[i]

Input grades[i]

total = total + grades[i]

​

If grades[i] > highest

highest = grades[i]

End If

End For

​

​

average = total / n

​

Display "Class Record"

For i = 0 to n - 1

Display names[i], grades[i]

End For

​

Display "Average Grade: ", average

Display "Highest Grade: ", highest

END

Exercise 2: Demo next session

Be ready to explain your answer in class:

• What your program does
• What the array stores
• How the array is used