Variable Declaration and Memory Allocation
Variable Declaration:
Defining a variable in a program, specifying its data type and name.
Example: int age;
Memory Allocation:
Assigning memory space to a variable during its declaration.
Example: int *ptr = malloc(sizeof(int));
Array Declaration and Initialization:
Defining an array variable and assigning initial values to its elements.
Example: int numbers[5] = {1, 2, 3, 4, 5};
Representation of Arrays in Memory:
Arrays are stored in contiguous memory locations.
Example: int arr[3] = {10, 20, 30};
Variable Declaration and Memory Allocation
Variable Declaration:
Defining a variable in a program, specifying its data type and name.
Example: int age;
Memory Allocation:
Assigning memory space to a variable during its declaration.
Example: int *ptr = malloc(sizeof(int));
Array Declaration and Initialization:
Defining an array variable and assigning initial values to its elements.
Example: int numbers[5] = {1, 2, 3, 4, 5};
Representation of Arrays in Memory:
Arrays are stored in contiguous memory locations.
Example: int arr[3] = {10, 20, 30};
Representation of Arrays in Memory
Arrays are stored in consecutive memory locations
Each element in the array is stored next to each other in memory
The memory address of the first element is used as the base address for the array
Accessing elements in an array is done by calculating the offset from the base
address
Arrays can be multi-dimensional, where each dimension is stored in consecutive
memory locations
Arrays are stored in row-major order in memory for easier access
Arrays
What is an array?
An array is a contiguous area of memory. It consists of equal-sized items (or
elements) indexed by a contiguous integer starting from 0 (or 1). Figure 1 shows
the visual representation of an array consisting of 7 items.
Fig 1: Visual representation of an array
Fig 1: Visual representation of an array
Once we know the address of the starting position of the array, we can calculate
the position of ith
(index) item in constant time as
Ai=A0+i∗s
Where A0
is the address of the starting position of the array (also called address of an
, array or array address) and s
is the size of each item. Suppose an array starts at memory 4000
and has 30 items with size 4
, the location (or address or position) of 22nd item can be calculated as
4000+22∗4=4088
. If we want to get the item in ith
position, we simply calculate its address and read the content of that address.
Even if the array has millions of items, the read (and write) operation takes a
constant time. All we need to do is calculate the position in memory and we are
done.
Operations on array
We can perform read, write, insert and delete operations on an array. If we give a
position i
in the array, read operation gives the item located at position i
, write overwrites the content in the memory located at position i
, insert inserts the new item at position i
and delete removes the item located at position i
. The complexities of all operations are described below.
Read
As described above we can perform the read operation on an array to get the content
of any position from first to the last position. This operation takes constant time
O(1)
.
Write
The write operation also takes constant time O(1)
. Once we know what to write and on what position to write, we can calculate the
memory address of that position and write the content.
Insert
Inserting an item to the end of the array takes only a constant time. We calculate
the position of the last block of the array and write the item. But if we want to
insert the item in the first position, we need to shift all the items one step to
the right and then write the item in the first position. If there are n
items in the array, inserting an item in the first position requires to move all
the items in the one step to the right. If moving one item takes O(1)
time then moving n
items take O(n)
time. In a similar way, if we want to insert an item to the middle of the array,
we need O(n/2)=O(n)
time. Therefore the worst case complexity of insertion is O(n)
.
Delete
The delete operation is similar to insert operation in terms of complexity. To
remove the item in the last position requires constant time. To remove the item in
the first position requires O(n)
time. This is because after we remove the item in the first position, we need to
move all the items one step to the left to fill the gap. The worst case complexity
is, therefore, O(n)
.
Multi-dimensional array
An array can be more than one dimensional. Even though we can have more than 2
dimensions, we only talk about 2-dimensional array here. The 2-dimensional array
has row and column as shown in Figure 2.
Variable Declaration:
Defining a variable in a program, specifying its data type and name.
Example: int age;
Memory Allocation:
Assigning memory space to a variable during its declaration.
Example: int *ptr = malloc(sizeof(int));
Array Declaration and Initialization:
Defining an array variable and assigning initial values to its elements.
Example: int numbers[5] = {1, 2, 3, 4, 5};
Representation of Arrays in Memory:
Arrays are stored in contiguous memory locations.
Example: int arr[3] = {10, 20, 30};
Variable Declaration and Memory Allocation
Variable Declaration:
Defining a variable in a program, specifying its data type and name.
Example: int age;
Memory Allocation:
Assigning memory space to a variable during its declaration.
Example: int *ptr = malloc(sizeof(int));
Array Declaration and Initialization:
Defining an array variable and assigning initial values to its elements.
Example: int numbers[5] = {1, 2, 3, 4, 5};
Representation of Arrays in Memory:
Arrays are stored in contiguous memory locations.
Example: int arr[3] = {10, 20, 30};
Representation of Arrays in Memory
Arrays are stored in consecutive memory locations
Each element in the array is stored next to each other in memory
The memory address of the first element is used as the base address for the array
Accessing elements in an array is done by calculating the offset from the base
address
Arrays can be multi-dimensional, where each dimension is stored in consecutive
memory locations
Arrays are stored in row-major order in memory for easier access
Arrays
What is an array?
An array is a contiguous area of memory. It consists of equal-sized items (or
elements) indexed by a contiguous integer starting from 0 (or 1). Figure 1 shows
the visual representation of an array consisting of 7 items.
Fig 1: Visual representation of an array
Fig 1: Visual representation of an array
Once we know the address of the starting position of the array, we can calculate
the position of ith
(index) item in constant time as
Ai=A0+i∗s
Where A0
is the address of the starting position of the array (also called address of an
, array or array address) and s
is the size of each item. Suppose an array starts at memory 4000
and has 30 items with size 4
, the location (or address or position) of 22nd item can be calculated as
4000+22∗4=4088
. If we want to get the item in ith
position, we simply calculate its address and read the content of that address.
Even if the array has millions of items, the read (and write) operation takes a
constant time. All we need to do is calculate the position in memory and we are
done.
Operations on array
We can perform read, write, insert and delete operations on an array. If we give a
position i
in the array, read operation gives the item located at position i
, write overwrites the content in the memory located at position i
, insert inserts the new item at position i
and delete removes the item located at position i
. The complexities of all operations are described below.
Read
As described above we can perform the read operation on an array to get the content
of any position from first to the last position. This operation takes constant time
O(1)
.
Write
The write operation also takes constant time O(1)
. Once we know what to write and on what position to write, we can calculate the
memory address of that position and write the content.
Insert
Inserting an item to the end of the array takes only a constant time. We calculate
the position of the last block of the array and write the item. But if we want to
insert the item in the first position, we need to shift all the items one step to
the right and then write the item in the first position. If there are n
items in the array, inserting an item in the first position requires to move all
the items in the one step to the right. If moving one item takes O(1)
time then moving n
items take O(n)
time. In a similar way, if we want to insert an item to the middle of the array,
we need O(n/2)=O(n)
time. Therefore the worst case complexity of insertion is O(n)
.
Delete
The delete operation is similar to insert operation in terms of complexity. To
remove the item in the last position requires constant time. To remove the item in
the first position requires O(n)
time. This is because after we remove the item in the first position, we need to
move all the items one step to the left to fill the gap. The worst case complexity
is, therefore, O(n)
.
Multi-dimensional array
An array can be more than one dimensional. Even though we can have more than 2
dimensions, we only talk about 2-dimensional array here. The 2-dimensional array
has row and column as shown in Figure 2.
