🧠 Array as a Data Structure

🔹 Definition

An array is a collection of elements of the same data type, stored in contiguous memory locations.
It is one of the most fundamental and simplest data structures in computer science.

---

🔹 Key Characteristics

Feature	Description
Homogeneous	All elements are of the same data type (e.g., all integers).
Contiguous Memory	Elements are stored one after another in adjacent memory cells.
Fixed Size	The size of the array is fixed at the time of creation.
Random Access	Any element can be accessed directly using its index (constant time).

---

🔹 Representation

For a 1D array:

A[0]   A[1]   A[2]   A[3]   A[4]
 |      |      |      |      |
1000   1004   1008   1012   1016

(If each integer takes 4 bytes.)

---

🧮 Address Calculation in 1D Array

If:

• Base Address (BA) = address of A[0]

• w = size of each element (in bytes)

• i = index position

Then:

$$\text{Address of A[i]} = BA + i \times w$$

---

🧩 Multidimensional Arrays

A 2D array is like a matrix (rows and columns):

A[3][4] =
[ [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12] ]

---

🧮 Address Calculation in 2D Arrays

For 2D arrays, elements are stored in memory as a sequence of 1D elements — either row by row or column by column.

Let:

• BA = base address (address of A[0][0])

• w = size of each element

• n = number of columns

• i, j = row and column indices

---

🔹 1. Row-Major Order

In Row-Major Order, elements of a row are stored contiguously.

Memory Layout:

Row	Elements	Stored Sequence
Row 0	A[0][0] A[0][1] A[0][2]	—
Row 1	A[1][0] A[1][1] A[1][2]	—
Row 2	A[2][0] A[2][1] A[2][2]	—

So the memory looks like:

A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2], A[2][0], A[2][1], A[2][2]

Address Formula:

$$\text{LOC(A[i][j])} = BA + \big((i \times n) + j\big) \times w$$

🔹 2. Column-Major Order

In Column-Major Order, elements of a column are stored contiguously.

Memory Layout:

A[0][0], A[1][0], A[2][0], A[0][1], A[1][1], A[2][1], A[0][2], A[1][2], A[2][2]

Address Formula:

$$\text{LOC(A[i][j])} = BA + \big((j \times m) + i\big) \times w$$

where m = number of rows.

---

🧮 Example

Consider the array:

A[3][4] =
[ [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12] ]

• BA = 1000

• w = 4 bytes

• n = 4, m = 3

Find the address of A[2][1].

➤ Row-major:

$$LOC = 1000 + ((2×4) + 1)×4 = 1000 + 9×4 = 1036$$

➤ Column-major:

$$LOC = 1000 + ((1×3) + 2)×4 = 1000 + 5×4 = 1020$$

---

🧠 Summary Table

Representation	Formula	Order of Storage
Row-major	BA + ((i × n) + j) × w	Row by row
Column-major	BA + ((j × m) + i) × w	Column by column

---

💡 Practical Notes for Students

• C and C++ use Row-Major Order.

• FORTRAN and MATLAB use Column-Major Order.

• Understanding address computation helps in writing efficient matrix algorithms.