What is an Array?

Think of an array as a generic container for storing a collection of elements.

To illustrate, you are moving house. Rather than take one object at a time to the new property you would store each item in a box. To keep things organized you would store kitchen items in a one, bedroom items in another and so on. This box is an array.  Moving day arrives, you would take all of these boxes into a purpose-built lorry. Think of this lorry as a multi-dimensional array as it contains an array of collections or boxes.

Yes, you can store arrays in arrays, how awesome is that!

In swift, you can create an array by using an array literal, this is a comma-separated list of values surrounded by square brackets.

An array is a sequence of items ranging from 0 – n. This means you can iterate through it at least once. It is also a collection which means it can be traversed multiple times and can be accessed using an operator. An array is also a random access collection. Which is great for efficiency!

A given example is the count property. This is “cheap” constant-time operation and is written as O(1). In lamens terms, this means no matter how big your array becomes, the time it takes to compute count will be equal.

Order

Items in an array are explicitly ordered.  Using the above Beatles array as an example John comes before Paul.

All arrays start at index zero. You can retrieve items from an array like so:

You can also access the first and last item using the following:

Order is defined by the array collection and should not be taken for granted. For instance, the Dictionary collection has a weaker concept when it comes to ordering.

Random-access

Random-access is a quality that data structures can claim if they can retrieve in time-constant O(1). Getting  “George” from the Beatles array takes a constant-time. For example,

retrieving “John” would take the same amount of time as retrieving “George”. Later in the series, we will dive into linked lists and binary trees. These two collections do not have a constant-time.

Performance

Besides the aforementioned random-access collection. As a developer, there are other areas of performance that may become of interest. In particular, how well does the collection perform when the contents of that collection need to grow? For arrays, we have two factors to consider.

Location of insertion

The first of the two factors is where you choose to insert the new item or object into the array. The most efficient way to add an item would be to add it at the end of the array. This can be done like so

However, there may be a time when you need to insert an item at a specific index of the array. Such as the very middle. This such scenario is not as efficient as adding at the end and is referred to as an O(n) operation.

To illustrate, imagine you’ve and a few friends queued, camped outside your favorite Apple store to be the first to buy the next greatest iPhone. Then just before the store opens an Apple employee puts his best mate at the front of the queue. Not only would you be extremely annoyed but your no longer in the front of the queue and respectively your friends are no longer in 2nd or 3rd. Everybody has had to move down a position.

This is exactly how arrays work and it’s relatively expensive to force shuffle every item one index which takes n steps to make room for the new item. This is known as O(n)  or linear-time.

If adding items at the front of the queue is a common occurrence in your project then you should consider a different data structure.

The second factor that determines the speed of insertions is the capacity of the array. If adding an extra element exceeds the capacity of the array, then the array has to copy itself and reallocate the storage. This results in the O(n) time. However, the standard library has a trick up its sleeve. If ever the array has reached its capacity it doubles in size. By doing this it will have a constant-time O(1)  this is known as amortized cost.