This is the most basic lesson on DeriveIt. If you're an experienced programmer, this is optional reading and you can skip ahead. Most content on DeriveIt is a lot more advanced - we're just covering the basics first!

Arrays are the simplest Data Structure, and are the building block for all other Data Structures. Arrays store data consecutively in computer memory, one element after the other. You create an Array like this:

x = [2,2,2,2]

You write to the Array like this:

x[2] = 8

And you read from it like this:

x[2] # gives 8

When you read or write to an Array, you only have to step to a single element which is fast. People say this takes $O(1)$ time. This just means that as the size of the Array grows, the read and write time stays the same. In other words, the time grows like the number 1 does - not at all.

Read/Write Time $O(1)$

You can also insert and delete elements from an Array, but when you do, the computer has to push many elements over. We indicated the elements that get pushed over in red.

x.insert(1, 4)

del x[2]

When we insert or delete an element, the worst case is that we have to push all of the $n$ elements over. So we say that adding/removing takes $O(n)$ time, which is slow.

Insert/Delete Time $O(n)$

The exception to having slow insert/delete is when you do it on the last element of the array. This is much faster than doing it on an arbitrary element, since the computer doesn't have to push anything over. It is an $O(1)$ operation.

Of course, the same is true if you insert/delete some constant amount from the end, but that usually doesn't show up.

x.append(4)

x.pop() # gives 4

Insert/Delete Time (last element) $O(1)$