An array is the most fundamental, the simplest, and the most widely used data structure. An array is a way to store a collection of elements to be accessed directly by using an index. To be more precise : it is a fixed-size collection of same type elements stored at contiguous memory locations.

The important thing to remember is an array index always starts at 0 and ends at lenght - 1 :
array[0]                  // First item
array[lenght - 1]     // Last item.

Storing items of the same type (same size in memory) contiguously allow the computer to calculate the index position in memory by just adding an offset to the base address. This is the key benefit of an array : it offers fast O(1) retrieval.

On the other hand, adding and removing an element from an array is slow because you cannot change the size of the array once it is created. It is true that most of the programming languages allow you to define dynamic arrays : those are flexible arrays allocated during program execution (std::vector for c++ for instance). The best is to use them, but, remember that changing the size of an array require the computer to create a new array and copy all elements in O(n).

Reduce the number of variables by using arrays
Use indexes to fast access an item (Random accessor)
Sequentially iterate through an array (Loop)
Compute statistics with our data.

We will have a quick overview of using an array with code samples to perform traversal, retrieval and update operations. We will also quickly see how to find the maximal value and compute the total benefits from a series of losses and gains.

What is next?

If we have not read about the linked lists then, let us have a tour to understand the main differences with the other most fundamental data structure. Arrays are also one of the favorite topics of programmers and you will hear many questions about them in any coding interview such as searching elements or sorting the array.

Here is some code using both the raw array and dynamic array (recommended). Whereas we have opted for the C++ as a programming language for the code illustration, the other languages use the same logic and most often the same syntax.

Initialization

// variable_type array_name[size];    (size must be known at compile time)
string names[5];                // names["?","?","?","?","?"]
int ages[] = {2, 3, 1, 0, 6};   //  ages[2, 3, 1, 0, 6]

// using namespace std;
// vector array_name(size);  (size is optional and may be changed at running time)
vector empty;                    // empty[]
vector names(5);                 // names["?","?","?","?","?"]
vector ages = {2, 3, 1, 0, 6};   //  ages[2, 3, 1, 0, 6]
 

Access / Update

// For both
int thirdAge = ages[2];   // Retrieve thirdAge = 1 (index starts at 0)
names[2] = "thirdName";   // Update third name : names["?","?","thirdName","?","?"]

// Using vector allows you to add values whenever you want
empty.push_back(66);  // empty[66]
empty.push_back(99);  // empty[66, 99]

Traversal / Update (Loop)

// Display ages line by line (for both)
for (int i = 0; i < 5; ++i)
  cout << ages[i] << endl;

// Update ages - Add one year to everyone (for both)
for (int i = 0; i < 5; ++i)
  ages[i]  += 1;

// Using vector allows you use its size instead of having to know it
for (int i = 0; i < ages.size(); ++i)
  cout << ages[i] << endl;

// Vector also provides you iterators for more convenient traversal
// Here we write the ages in reverse order (from the last to the first)
for (auto it = ages.cbegin(); it != ages.cend(); ++it)
  cout << *it << endl;

That’s it : you have everything to start playing with arrays and vectors to build some process. We will finish by three simple real cases often used. Let us say we are a poker player who notes the results of its benefits or losses day after day during a year.

Maximum gain

// vector gains = { ... }
auto it = gains.begin();
auto maxValue = *it;
++it;

for (; it != gains.end(); ++it)
  if (*it > maxValue)
    maxValue = *it;

Last loosing time

int lastLoosingTime = 0; // Number of days since lastt lost when != 0 (0 means never lost).

for (auto it = gains.cbegin(); it != gains.cend(); ++it, ++lastLoosingTime)
  if (*it < 0)
    break;

Total gain

auto it = gains.begin();
auto totalGain = *it;
++it;

for (; it != gains.end(); ++it)
  totalGain += *it;

• The Algorithm Design Manual Book par Steven S Skiena
• Wikipedia