Array Representation
1. Memory Representation of Arrays
Arrays are stored in contiguous blocks of memory, which means that all elements
of an array are placed next to each other in memory.
Contiguous Memory Allocation:
o Arrays allocate a block of memory large enough to hold all of its
elements.
o The memory addresses of array elements are contiguous (i.e., they
are next to each other in memory).
o In many programming languages (like C, C++, and Python), arrays can
be accessed via an index, where each element's position is
determined by its index relative to the base address of the array.
Example (in C):
int arr[5] = {10, 20, 30, 40, 50};
In this case, the memory layout would look like this:
| 10 | 20 | 30 | 40 | 50 |
Each number is stored in a consecutive memory location, and the array's base
address (the address of arr[0]) points to the first element.
2. Accessing Array Elements
Because arrays are stored contiguously, accessing an element is done by
calculating its position in memory based on the index. The address of an element
at index i can be calculated as:
Address of arr[i] = base address of arr + i * size_of_element
, This formula allows for constant time O(1) access to any element in the array,
making arrays very efficient for random access.
For example, if an integer array has elements stored in a contiguous block of
memory and each integer takes 4 bytes, then the element at index i can be
accessed as:
Address of arr[i] = Address of arr[0] + i * 4
3. Array vs Linked List
Array: Fixed-size block of memory, elements are contiguous, and access is
O(1).
Linked List: Each node contains a reference (pointer) to the next node, and
the nodes are scattered throughout memory, which means accessing an
element is slower (O(n)) because you have to traverse the list.
4. Row-Major and Column-Major Order
For multi-dimensional arrays (like 2D arrays), there are two common ways to
store them in memory:
Row-Major Order (used by C, C++):
o In row-major order, the rows of the array are stored contiguously in
memory.
o For example, for a 2x3 matrix:
|1 2 3|
|4 5 6|
The elements will be stored in memory as: 1, 2, 3, 4, 5, 6.
Column-Major Order (used by languages like Fortran and MATLAB):
o In column-major order, the columns of the array are stored
contiguously in memory.
1. Memory Representation of Arrays
Arrays are stored in contiguous blocks of memory, which means that all elements
of an array are placed next to each other in memory.
Contiguous Memory Allocation:
o Arrays allocate a block of memory large enough to hold all of its
elements.
o The memory addresses of array elements are contiguous (i.e., they
are next to each other in memory).
o In many programming languages (like C, C++, and Python), arrays can
be accessed via an index, where each element's position is
determined by its index relative to the base address of the array.
Example (in C):
int arr[5] = {10, 20, 30, 40, 50};
In this case, the memory layout would look like this:
| 10 | 20 | 30 | 40 | 50 |
Each number is stored in a consecutive memory location, and the array's base
address (the address of arr[0]) points to the first element.
2. Accessing Array Elements
Because arrays are stored contiguously, accessing an element is done by
calculating its position in memory based on the index. The address of an element
at index i can be calculated as:
Address of arr[i] = base address of arr + i * size_of_element
, This formula allows for constant time O(1) access to any element in the array,
making arrays very efficient for random access.
For example, if an integer array has elements stored in a contiguous block of
memory and each integer takes 4 bytes, then the element at index i can be
accessed as:
Address of arr[i] = Address of arr[0] + i * 4
3. Array vs Linked List
Array: Fixed-size block of memory, elements are contiguous, and access is
O(1).
Linked List: Each node contains a reference (pointer) to the next node, and
the nodes are scattered throughout memory, which means accessing an
element is slower (O(n)) because you have to traverse the list.
4. Row-Major and Column-Major Order
For multi-dimensional arrays (like 2D arrays), there are two common ways to
store them in memory:
Row-Major Order (used by C, C++):
o In row-major order, the rows of the array are stored contiguously in
memory.
o For example, for a 2x3 matrix:
|1 2 3|
|4 5 6|
The elements will be stored in memory as: 1, 2, 3, 4, 5, 6.
Column-Major Order (used by languages like Fortran and MATLAB):
o In column-major order, the columns of the array are stored
contiguously in memory.
