Introduction to Array
An array is a collection of items of the same type stored contiguously in memory. It is the simplest and most widely used Data Structure. Most of the other data structures for example stack and queues can be implemented using the array structure. This makes the array one of the central building blocks of all data structures.
Look at the figure below; we have made a simple array with four elements. Each item in the collection is called a Data Element and the number of data elements stored in an array is known as its size.
Declaring arrays
In C++, arrays can be declared as either static or dynamic.
Declaring static arrays
In C++, memory allocation for static arrays takes place at compile time. Furthermore, this allocation is on stack memory.
A generic definition of a static array is given below:
datatype arrayName [size];
Static arrays can be assigned values when they are declared. This is called array initialization. An example of array initialization is:
int dots[3] = { 1, 4, -2 };
When initializing arrays, the size can be skipped. In such cases, the compiler determines the size of the array from the list of values. The following is just as correct as the last example:
int dots[] = { 1, 4, -2 };
If we do not initialize an array, there is no saying what its element values will be. If, we initialize an array with fewer values than the array size, the remaining array elements will be zeros. For example, the following statement will initialize an array containing the element 1, 2, 3, 0, 0.
int dashes[5] = {1, 2, 3};Declaring dynamic arrays
Static arrays are fixed in size. The memory allocated to them can’t grow or shrink. Dynamic arrays are allocated at run time on the heap memory. This is done with the help of pointers.
A generic dynamic array declaration is given below:
datatype * arrayName = new datatype[size];
Data types could be int, float, double, char, or any user-defined type.
Accessing array elements#
Array elements can be accessed by specifying an integer index using the square brackets. In C++, array indices start at and go all the way up to , where is the size of the array.
Array indexing
Each data element in an array is associated with a numerical value called the Index which corresponds to the position of that item in the array. It is important to note that the value of the index is non-negative and always starts from 0. So the first element of an array will be stored at Index 0 and the last one at Index n-1, where n is the size of the array.
An index makes it possible to access any element of the array directly. This is why an array is called a random access data structure. That is the key feature that differentiates arrays from other data structures like linkedLists.
So, to refer to the third element in an array named hills, we would write:
hills[2]
The C++ runtime does not perform bounds checking on array indices, so if an array named hills is declared of size and you try to access hills[5], there is no telling what will happen. The program might crash due to a segmentation fault, or it might keep running while giving potentially incorrect results.
Consider the example below:
int main(){
int size = 10;
//Dynamic array initialization
int * dynamicArray = new int[size];
for(int i = 0 ; i< size; i++){
dynamicArray[i] = i;
}
//Static array initialization
int staticArray[size] = {1,2,3,4,5,6,7,8,9,10};
float staticArray2[] = {2.3, 7.9, 5.6, 4.2, 9.1};
//Printing an static Array
cout << "Static Array: ";
for(int i = 0 ; i< size; i++){
cout << staticArray[i] << " ";
}
cout << endl;
//Printing an static Array
cout << "Static Array 2: ";
for(int i = 0 ; i< 5; i++){
cout << staticArray2[i] << " ";
}
cout << endl;
//Printing an Dynamic Array
cout << "Dynamic Array: ";
for(int i = 0 ; i< size; i++){
cout << dynamicArray[i] << " ";
}
// deleting allocated memory
delete[] dynamicArray;
}How are arrays stored in memory?
Static arrays in memory are stored using contiguous memory space while dynamic arrays in memory are stored using a reference pointer which points to the first element of the array. For example, if we create a dynamic integer array of size 3 and name it arr, then the variable will point to the start of the array. Memory assigned to arr will be on the stack. The memory created by new keyword will be on heap. See the figure below:
Changing or Adding elements in an array
To change a static array element, we can simply access its index and change the value. For Example:
int arr[3] = {1,2,3};
arr[2] = 4;
Now, the array becomes {1,2,4}.
To add a new element in an array, we need to resize the array first and that is only possible if it’s a dynamic array. Given below is the code that’ll do the job. Have a look!
class ArrayList{
int * arr; // array growing dynamically
int num_elements; // number of elements in an array
int capacity; // current capacity of an array
}; void resize(){
// capacity(size) is doubled
int * tempArr = new int[capacity*2];
capacity*=2;
//copying old array values to new array
for(int i=0; i<num_elements; i++){
tempArr[i]=arr[i];
}
// deleting the allocated space
delete [] arr;
// pointing to new allocated memory
arr=tempArr;
}At the end of the lesson, you’ll see the implementation of the ArrayList class.
We can add one or more items to an array using the insert(int val) member function of the class ArrayList.
void insert(int val){
// if arr size is less than capacity of list
if(num_elements < capacity){
arr[num_elements]=val;
num_elements++;
}else{
resize();
arr[num_elements]=val;
num_elements++;
}
}To return the current length of the array, we can call the length() function of class ArrayList.
int length(){
return num_elements; // return
}Here is the implementation of the class Arraylist with print() function, which will print the elements of an array.
#include <iostream>
using namespace std;
class ArrayList {
int *arr;
int num_elements;
int capacity;
public:
ArrayList(int size) {
arr = new int[size];
num_elements = 0;
capacity = size;
}
void insert(int val) {
if(num_elements < capacity) {
arr[num_elements]=val;
num_elements++;
} else {
resize();
arr[num_elements]=val;
num_elements++;
}
}
int getAt(int index){
return arr[index];
}
void resize() {
int* tempArr=new int[capacity*2];
capacity*=2;
for(int i=0; i<num_elements; i++) {
tempArr[i]=arr[i];
}
delete [] arr;
arr=tempArr;
}
int length() {
return num_elements;
}
void print() {
for(int i=0; i<num_elements; i++)
cout << arr[i] << " ";
cout << endl;
}
};
int main() {
ArrayList arr(1);
cout << "Arr length : " << arr.length() << endl;
arr.insert(1);
arr.insert(2);
arr.insert(3);
arr.insert(4);
arr.insert(5);
arr.insert(6);
arr.insert(7);
arr.insert(8);
cout << "Arr length : " << arr.length() << endl;
cout << "Array : ";
arr.print();
cout << "Element at index 5 is " << arr.getAt(4) << endl;
}