Introduction to data structures: Arrays
Learn about the array data structure in an intuitive way
The first data structure that most programmers are introduced to is
the array.
It's considered so fundamental that it's left out of
"data structure" courses and covered in earlier "introduction to
programming" courses.
Every popular programming language supports
the array data structure.
Arrays are used to construct other data structures (we will learn
about them in future articles).
We could go as far as giving it the title "godmother of data
structures".
What is an array?
An array is a finite sequence of elements.
"Sequence" tells us that the elements are placed one after another.
"Finite" tells us that the sequence has to end. It can be 10, 100,
1000, 10000 or more elements long, but it has to end.
Technically,
it should be at least one element long and the upper limit depends on
the available memory resources.
Can we think of examples of arrays in our daily lives?
Let's take
my son's toy cars as an example. He loves to arrange them one after
another, making a sequence of toy cars: 🚗🚕🚙🛻🏎️🚓
Luckily for
us those sequences are finite 😄
Another example are the dish dryers that we have in our kitchens. They have gaps for a finite number of plates to dry.
Another example are seats in a cinema (or stadium, theatre, etc.).
There is a finite number of seats. Even though they are not physically
placed one after another in the real world, we could represent them
with an array in a computer program.
A very important aspect of arrays is related to how individual
elements are accessed.
They are accessed using indices starting at 0. That means that the
first element in the array is accessed with the index 0, the second
element with the index 1 and so on. The last element is accessed with
the index: length of array - 1. In a ten element array
the last element would be accessed with index 9.
Finally, regardless of the position in the array, using indices it takes the same amount of time to access any element in the array. It does not matter if the element is somewhere at the start, middle or end of the array.
When should arrays be used?
- When the length of the array is know upfront.
- When we don't need to modify the order of the elements in the array or its length.
If the length of the array is not known upfront or we need to modify
the order of its elements or its length, the array data structure
might not be a good choice for us.
Every time we would need to append an element (i.e. insert at
the last position), we would need to create a new array with a larger
length, copy the elements from the old array to the new array and
finally insert the new element at the last position.
Every time
we would need to insert an element (anywhere except the end of the
array), we would need to create a new array with a larger length, copy
and shift the elements from the old array to the new array and insert
the new element.
Every time we would need to remove an element,
we would need to create a new array with a smaller length and copy the
other elements from the old array to the new array.
These kind
of operations would cause performance issues for our computer program.
In these kind of cases there are other data strcutures that we can
use.
We will learn about them in the next articles.
If you enjoy my articles, please consider supporting me.