Array

Before anything, let me ask you something

Before we learn about arrays, you can try using the visualizer to see how arrays work.

Let's learn arrays in a very simple way possible.

Think about going to school. Just you. You'd hop on your cycle and go.

Now imagine you and 40 friends are going together. You could each take your own cycle — 40 separate cycles, 40 separate trips. Or you could just take one bus.

Same idea in programming. If you have one value to store, you use a variable:

int var = 10;

But if you have 10 different numbers to store? You could store them in 10 different variables. However you could also save them all in one variable — like taking a bus for 40 students instead of 40 separate cycles.

That one variable that holds everything together is called an array.

What is an array?

If you open your music app, what do you see? A playlist — songs stored in a row, one after another.

That is an array. An array is a collection of items of the same type. Now let's see how to create one.

How to create an array in C++?

We create one like this:

datatype  arrayName[how many items]

Let's create a playlist array:

string playlist[5] = {"Blinding Lights", "Levitating", "Stay", "Heat Waves", "Peaches"};

This creates an array named playlist that stores strings and holds 5 of them. Let me break it down:

string

The data type. We are storing song names — text — so we write string. Storing numbers? Write int.

playlist

The name of the array.

[5]

The size — total number of slots the computer reserves. This is fixed forever and cannot change.

{}

The songs we are adding. Each one goes into a slot, in order, left to right.

Next, let's see how arrays are stored.

How are arrays stored in the computer?

Think of your computer having this memory:

[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]

Now, our array has a size of 5. So the computer searches for a place where 5 empty slots are available together. It finds one and stores all 5 songs there, like this:

[ ][ ][ ][Blinding Lights][Levitating][Stay][Heat Waves][Peaches][ ][ ][ ][ ]

Now each slot has a number. That number is called an index. Five slots numbered 0 to 4. The first song is at index 0 — not 1.

Access a specific element in an array

Sometimes you don't want to play the whole playlist. You want one specific song. You just tap it and it plays directly.

Same in arrays. You can access any element directly using its index number. Index starts at 0, not 1. To access any element you just do:

arrayName[index]

So to access our playlist at index 0:

playlist[0]

And to print it:

cout << playlist[0];  // Blinding Lights

Similarly, this is how you access all 5:

cout << playlist[0];  // Blinding Lights
cout << playlist[1];  // Levitating
cout << playlist[2];  // Stay
cout << playlist[3];  // Heat Waves
cout << playlist[4];  // Peaches

So to access Stay it is one step. To access Peaches it is one step. Even if there were 1000 songs it would still be one step — because we know exactly where the song is. We just give the index and the computer goes directly there.

Update an element

Say you want to update a song. Your playlist currently looks like this:

You just go to its index and overwrite it:

playlist[2] = "Shape of You";

Now your playlist looks like this — Stay is now replaced with Shape of You. One step. We go directly to the index and change it.

Traversal — going through every element

Sometimes you don't choose a song. You just hit play and every song plays one by one on auto mode. Going through each element one by one is called traversal. To traverse we just loop through each element:

for(int i = 0; i < n; i++){
    cout << playlist[i] << "\n";
}

int i = 0

Start at index 0. The first slot.

i < n

Keep going while i is less than n. Here n is the length — how many slots are filled. We visit 0, 1, 2 ... n-1 and stop. The empty slots after that are not our songs.

i++

After each element, move to the next index.

#include <iostream>
#include <string>
using namespace std;
int main(){
    string playlist[5] = {"Blinding Lights", "Levitating", "Stay", "Heat Waves", "Peaches"};
    int n = 5;
    for(int i = 0; i < n; i++){
        cout << playlist[i] << "\n";
    }
    return 0;
}
// Blinding Lights
// Levitating
// Stay
// Heat Waves
// Peaches

Remove last element

Say you want to remove a song. You delete it right? However in programming it does not work like that. We cannot delete a slot. The size is fixed — the slots are always there. So what we do is just overwrite the last filled slot with an empty value and reduce our length.

playlist[4] = "";
n--;

That is it. Peaches is gone. We do n-- to reduce the length — now our array has 4 songs instead of 5. The size is still 5. The slot is still there, but we treat it as empty.

playlist[4] = ""

We overwrite the last slot with an empty value. Peaches is gone.

n--

We reduce the length by 1. The size stays the same — we just tell our code there are now 4 songs, not 5.

#include <iostream>
#include <string>
using namespace std;
int main(){
    string playlist[10] = {"Blinding Lights", "Levitating", "Stay", "Heat Waves", "Peaches"};
    int n = 5;
    playlist[n - 1] = "";
    n--;
    for(int i = 0; i < n; i++){
        cout << playlist[i] << "\n";
    }
    return 0;
}
// Blinding Lights
// Levitating
// Stay
// Heat Waves

Remove from any index

Say you want to remove Stay — which is at index 2. You cannot just overwrite it with empty and call it done — because now you have a gap in the middle:

[Blinding Lights][Levitating][  ][Heat Waves][Peaches]
        0              1       2       3           4

So what we do is shift everything after it one step to the left:

for(int i = 2; i < n-1; i++){
    playlist[i] = playlist[i+1];
}
playlist[n-1] = "";
n--;

playlist[i] = playlist[i+1]

Each element moves one step to the left.

playlist[n-1] = ""

The last slot is now empty so we overwrite it.

n--

We reduce the length by 1. The size stays the same.

#include <iostream>
#include <string>
using namespace std;
int main(){
    string playlist[10] = {"Blinding Lights", "Levitating", "Stay", "Heat Waves", "Peaches"};
    int n = 5;
    for(int i = 2; i < n - 1; i++){
        playlist[i] = playlist[i + 1];
    }
    playlist[n - 1] = "";
    n--;
    for(int i = 0; i < n; i++){
        cout << playlist[i] << "\n";
    }
    return 0;
}
// Blinding Lights
// Levitating
// Heat Waves
// Peaches

Adding an element at the end · O(1)

Before we write the code — one important thing to understand first.

In C++, an array has a fixed size. string playlist[5] means size 5 forever. So if you want to add songs later you need to plan ahead. Declare the array bigger than you currently need. In practice — just double it. Have 5 songs today? Declare size 10. This gives you room to grow.

We keep a variable n that tracks the length — how many slots are actually filled. The size is 10 but the length starts at 5. The other 5 slots are just sitting there empty and waiting.

[Blinding Lights][Levitating][Stay][Heat Waves][Peaches][  ][  ][  ][  ][  ]
        0              1        2       3           4      5    6    7    8    9

Now to add a song we just place it at index n — which is always the next empty slot:

playlist[n] = "Montero";
n++;

playlist[n]

n is the length — how many slots are filled. Since index starts at 0, index n is always the next empty one. Length 5 means next empty is at index 5.

n++

Increase the length by 1. Without this n stays wrong and your next song overwrites this one.

#include <iostream>
#include <string>
using namespace std;
int main(){
    string playlist[10] = {"Blinding Lights", "Levitating", "Stay", "Heat Waves", "Peaches"};
    int n = 5;
    playlist[n] = "Montero";
    n++;
    for(int i = 0; i < n; i++){
        cout << playlist[i] << "\n";
    }
    return 0;
}
// Blinding Lights
// Levitating
// Stay
// Heat Waves
// Peaches
// Montero

Adding an element at a specific index · O(n)

Say you want to add Montero at index 2 — right between Levitating and Stay.

But remember — the size is fixed. You cannot just magically create a new slot in the middle. So always plan ahead and declare a bigger size than you currently need:

string playlist[10] = {"Blinding Lights", "Levitating", "Stay", "Heat Waves", "Peaches"};
int n = 5;

Size is 10. Length is 5 — 5 songs filled, 5 empty slots waiting at the end. Now we have room.

Now — you cannot just place Montero at index 2 directly. Stay is already sitting there. If you do that Stay is gone forever. So what do we do? We make room first. We pick up everything from index 2 onwards and shift it one step to the right:

[Blinding Lights][Levitating][Stay][Heat Waves][Peaches][  ]
                                ↓        ↓          ↓
[Blinding Lights][Levitating][  ][Stay][Heat Waves][Peaches]

Now index 2 is empty and waiting. We place Montero right there. Nobody got overwritten. Nobody got lost. Everything is clean. In code:

for(int i = n; i > 2; i--){
    playlist[i] = playlist[i - 1];
}
playlist[2] = "Montero";
n++;
for(int i = 0; i < n; i++){
    cout << playlist[i] << "\n";
}
// Blinding Lights
// Levitating
// Montero
// Stay
// Heat Waves
// Peaches