An array is the simplest and most used data structure we’ll cover in this guide. It’s a collection of items stored at contiguous memory locations. There are a few types of implementation based on what language you’re using, some are static, some are dynamic, some an store multiple types of data, some only one.
The basic idea is that they store large number of items and continuous memory location makes accessing those items fast ( O(1) time ). Items are accessed by index usually starting from 0 (there are also 1-indexed and n-indexed arrays) and each index represents a memory offset from the first item.
To make things clear let’s use an array of integers as an example. Below code makes an integer array and prints each items memory address.
#include
using namespace std;
int main()
{
// an array of 5 integers.
// If arr[0] is stored at address x,
// then arr[1] is stored at x + sizeof(int)
// arr[2] is stored at x + sizeof(int) + sizeof(int)
// and so on. int arr[5], i;
cout << "Size of integer in this compiler is " << sizeof(int) << "n";
for (i = 0; i < 5; i++)
// The use of '&' before a variable name, yields
// address of variable.
cout << "Address arr[" << i << "] is " << &arr[i] << "n";
return 0;
}Output:
Size of integer in this compiler is 4
Address arr[0] is 0x7ffe75c32210
Address arr[1] is 0x7ffe75c32214
Address arr[2] is 0x7ffe75c32218
Address arr[3] is 0x7ffe75c3221c
Address arr[4] is 0x7ffe75c32220Now I skipped over the point and that’s how we declare an array, above is one way to declare an array in C++, let’s look at some more:
int main()
{
//int array of size 5, ___ ways
int a[5]; //this is just to reserve memory, if you try to access
//any of the values in this array they would be random
int a[5] = {0, 1, 2, 3, 4};
int a[] = {0, 1, 2}; //Compiler will automatically alocate
//memory for three values
int a[5] = {}; //All zeroes
int a[5] = {1}; //one and all zeroes
//Same is for all other data types
return 0;
}There is a version of dynamic arrays in C++ called vectors, not to be confused with mathematical vectors these are just arrays with dynamic size, so they support removing and adding elements. Here is how to use them:
#include <vector>
using namespace std;
int main
{
vector<int> a; //This is just a nullptr right now
vector<int> a = {0, 2, 4};
//Adding values
a.push_back(3) //a = {0, 2, 4, 3}
//Removing values
a.pop_back() //a = {0, 2, 4}
return 0
}Traversing arrays can be done with a simple for loop:
#include <iostream>
using namespace std;
int main()
{
int arr[5] = {1, 2, 3, 4, 5};
//Using indexing
for (int i = 0; i < 5; i++)
cout << "Element arr[" << i << "] is " << arr[i]
<< "\n";
//Or just accessing the value itself
for(auto i: arr)
cout << "Element is " << i
<< "\n";
return 0;
}Traversing vector can be done using vector::begin and vector::end. Those return something called vector iterator which is a pointer to the item in the vector. That why we have to dereference it in the cout.
#include <vector>
using namespace std;
int main
{
vector<int> vector;
for (int i = 1; i <= 5; i++)
vector.push_back(i);
for (auto i = vector.begin(); i != vector.end(); ++i)
cout << *i << " ";
};For all the functions of a vector in C++ see the docs https://en.cppreference.com/w/cpp/container/vector
Now let’s see how do we declare vectors in some other languages.
Java
class Krile
{
public static void main (String[] args)
{
// declares an Array of integers.
int[] arr;
//This is the same
int arr[];
// allocating memory for 5 integers.
arr = new int[5];
//Or it can be done like this
int arr[] = new int[5];
// initialize the elements of the array
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
arr[3] = 40;
arr[4] = 50;
//Or write the elements at the start
int arr[] = {10, 20, 30, 40, 50}
// accessing the elements of the specified array
for (int i = 0; i < arr.length; i++)
System.out.println("Element at index " + i +" : "+ arr[i]);
}
}Python
In Python there are two types: lists and arrays. List are dynamically allocated and can store multiple value types, whereas arrays store a specific data type, but are still dynamically allocated.
Most commonly used are lists, for arrays you need to import array module.
import array
lst = [0, 'Mateo', 3.14]
lst= list()
#this is python specific, it's called list comperhension
#it's a nice one line list creation
lst = [i for i in range(90)]
#when making an array you need to pass the type and values to be stored
arr = array.array('i', [2, 5, 7, 8])
#Printing the array
print ("Array elements are : ",end=" ")
for i in range (0, 3):
print (arr[i], end=" ")
#Functions, the same for the array and the list
lst.append(x)#Adds the value x at the end
lst.insert(i, x)#Adds the value x at index i
lst.remove(x)#removes the first occurrance value x
lst.pop()#removes the last element and returns it
lst.index(x)#Returns the index of the first occurrance of value x
lst.reverse()#Reverses the list/array...Official docs –
arrays – https://docs.python.org/3/library/array.html
lists – https://docs.python.org/3/tutorial/datastructures.html
C#:
//Declaration
int[] arr;
//Initialization
arr = new int[5];
//You can also do this in one line
int[] arr = new int[5];
//Or you can set the values right away
int[] arr = new int[]{0, 1, 2, 3, 4};
/*
This is NOT legal, this gives a compile error
int[] arr;
arr = {2, 3, 4, 5};
This as well
int[] arr = new int[];
*/
//Getting the size
arr.Length;
//Traversing using a for loop
for (int i = 0; i < intArray.Length; i++)
Console.Write(" " + intArray[i]);
//Or a foreach loop
foreach(int i in intArray)
Console.Write(" " + i);Multidimensional Arrays
What we looked at so far were just usual one-dimensional arrays. We can also use multidimensional arrays. These are basically arrays of arrays. Most common are 2D arrays (also called matrices or grids). You can think of the nested arrays as rows, and elements in them as columns. Rows can also have different number of element, these are called Jagged arrays. Let’s look at example in C++.
using namespace std
int main
{
int matrix[6][8] = {}; //data-type name[rows][columns]
//Accessing values
/*
Matrix looks like this:
[
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
]
Upper left value in the matrix is accessed by matrix[0][0]
and bottom right is
matrix[(number of rows) - 1][(number of columns) - 1]
in this case matrix[5][7]
*/
//Traversing arrays with nested for loops
for(int i = 0; i < matrix.size(); i++)
{
for(int j = 0; j < matrix[i].size(); j++)
{
//Do somthing
matrix[i][j]
}
}
}Here is in some other languages
Java
//Declaration
int[][] matrix = new int[2][4];
//Initialization of values
matrix[row][column] = value;
//Or like this
int[][] matrix = {{1, 2}, {3, 4})
//jagged array
int[][] jaggedArr = new int[2][];
jaggedArr[0] = new int[4]; //First row has 4 values
jaggedArr[1] = new int[3]; //Second has 3
//Or like this
int[][] jaggedArr = { {0, 1, 5},
{52, 70, 8, 9, 13},
{10, 12} };
for (int i=0; i< 3 ; i++)
{
for (int j=0; j < 3 ; j++)
arr[i][j];
}Python
#This would create a grid with 4 rows and 5 columns
matrix = [[_ for _ in range(5)] for _ in range(4)]
#Accessing arrays
for x in range(len(matrix)):
for y in range(len(matrix[x])):
matrix[x][y] #Do somethingC#:
int[,] matrix = new int[2][4];
//Jagged array
int[,] jagged = new int[2][];
jagged[0] = new int[3];
jagged[1] = new int[5];
for(int x = 0; x < matrix.Length; x++)
{
for(int y = 0; y < matrix[x].Length; y++)
{
matrix[x][y]; //Do something
}
}Creating 3D arrays would be the same thing, you need one more bracket and one more nested for loop to traverse it that’s it.
In coming posts I’ll be covering some array coding exercises and problems. I’ll explain my thought process when going over those problems and provide source code in the languages I covered here.