A Deep Dive into Arrays – Part 1: What, Why & How

🔹 What's an Array?

An array is a data structure that holds multiple values of the same data type in contiguous memory locations.
Let’s break this down:

• What’s a Data Structure? A data structure is a specific way of storing and accessing data in a computer so it can be used efficiently. Common operations: Read, Write, Update, Delete.
• We choose different data structures based on our needs. Some examples:
  • Arrays (specifically 2D arrays or matrices) are used to represent pixels in an image. Since array elements are stored in contiguous memory, accessing them is very fast — something that's critical in graphics rendering.
  • Trees are a natural choice for implementing file systems. Folders nested within folders can be best modeled as trees, with the root folder at the top.

---

🔹 Why Arrays?

Arrays are optimized for locality of reference — a key concept in making memory access fast.

Locality of Reference:

This refers to the tendency of programs to access:

• Recently used memory locations → called Temporal Locality
• Nearby memory locations → called Spatial Locality

These patterns are utilized by:

1. The CPU: When the CPU fetches data from memory, it also fetches nearby memory locations, anticipating future access.

2. Programmers: Take an image processing task where pixels are stored in a matrix (2D array). In most programming languages, matrices are stored in row-major order, meaning all columns of row 1 are stored first, then row 2, and so on.
   So consider this code:
   

           for col in range(N):
               for row in range(N):
                   sum += matrix[row][col]
   

   This accesses data column-first, skipping memory in the way it’s laid out, leading to cache misses. A better approach would be to access data row-first.

🚀 Why arrays are fast:

• Array elements are stored contiguously (spatial locality).
• When you access array[0], the CPU preloads array[1], array[2], etc., into the CPU cache.
• This makes index-based access blazing fast. Hence, arrays are ideal when:
• You need to store large amounts of data of the same type
• You need to perform common operations across all elements, like scaling pixels in an image.

---

🔹 Here's a mind map of everything I just learned — what’s yours?

---

Next Up:

Dynamic arrays — what happens when we want to grow or shrink arrays on the fly?

---

Hope you enjoyed reading!

Let me know if something wasn’t clear or if you’ve got a better mental model!