Data Structures

Array

Lesson

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:

You write to the Array like this:

And you read from it like this:

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)O(1) time. This just means that the time grows with the number 1, which means that it doesn't grow at all. As the size of the Array grows, the read and write time stays the same.

Read/Write Time O(1)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.

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

Insert/Delete Time O(n)O(n)

The only time inserting and deleting isn't slow is when you do it on the last element. This has a much faster complexity than doing it on an arbitrary element, since the computer doesn't ever have to push anything over. It just has to do 1 operation, which is O(1)O(1).

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

Mark as Completed:
Submits:
test
Test your code to get an output here!