Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
Regardless of the kind of data structure you work with, all data structures are expected to carry out four kinds of operations at minimum. In this video we look at the concepts behind array access
Regardless of the kind of
data structure you work with,
0:00
all data structures are expected to carry
out four kinds of operations at minimum.
0:03
We need to be able to access and
read values stored in the structure.
0:08
We need to be able to search for
an arbitrary value.
0:12
We also need to be able to inset a value
at any point into the structure.
0:15
And finally,
we need to be able to delete structures.
0:18
Let's look at how these operations are
implemented on the array structure in some
0:22
detail starting with Access.
0:27
Elements in an array are identified
using a value known as an Index.
0:29
And we use this Index to access and
read the value.
0:33
Most programming languages follow
a zero-based numbering system
0:37
when it comes to arrays.
0:41
And all this means is that the first
index value is equal to zero, not 1.
0:42
Generally speaking,
when an array is declared,
0:47
a base amount of contiguous memory
is allocated as the array storage.
0:50
Computers refer to memory
through the use of an address.
0:55
But instead of keeping a reference
to all the memory allocated for
0:58
an array, the array only has to store
the address of the first location.
1:01
Because the memory is contiguous, using
the base address, the array can calculate
1:06
the address of any value by using the
index position of that value as an offset.
1:11
If you want to be more specific,
think of it this way.
1:16
Let's say we want to create an array of
integers, and then each integer takes up
1:18
a certain amount of space in
memory that we'll call M.
1:23
Let's also assume that we know how
many elements we're going to create.
1:26
So the size of the array is some
number of elements we'll call n.
1:30
The total amount of space that we need to
allocate is n times the space per item M.
1:34
If the array keeps track of the location
in memory where the first value is held,
1:40
so let's label that M0,
1:45
then it has all the information it needs
to find any other element in the list.
1:46
When accessing a value in an array,
we use the index.
1:51
So to get the first element in the list,
we use the zero index.
1:55
To get the second we use
the index value 1, and so on.
1:58
Given that the array knows how much
storage is needed for each element,
2:01
it can get the address of any element
by starting off with the address for
2:06
the first element.
2:11
And adding to that,the index value times
the amount of storage per element.
2:12
For example, to access the second value,
we can start with M0.
2:17
And to that,
add times M times the index value 1,
2:21
giving us M1 as the location in memory for
the second address.
2:24
This is a very simplified model, but
that's more or less how it works.
2:28
This is only possible because we know that
array memory is contiguous with no gaps.
2:33
Let's switch over to some code.
2:39
As I mentioned earlier, we're going
to be using Python in this course.
2:41
If you don't know how to code, or
you're interested in this content but
2:45
know a language other than Python,
check the note section of this video for
2:49
more information.
2:53
While the code will be in Python,
the concepts are universal.
2:54
And more importantly, simple enough that
you should have no issue following along
2:58
in your favorite programming language.
3:02
Now, to get started,
click on the Launch Workspace button
3:05
on the video page that you
are watching right now.
3:08
This should spin up an instance
of a treehouse workspace,
3:11
an in-browser coding environment.
3:15
Right now, your workspace should be empty,
and that's to be expected.
3:17
So let's add a new file in here.
3:21
Going to go to File > New File.
3:22
And we'll call this arrays.py, py.
3:25
Creating a list in Python is quite simple.
3:30
So we'll call this new_list.
3:33
We use a set of square brackets around
a set of values to create a list.
3:36
So 1.
3:40
And we comma separate them.
3:41
So space 2, and space 3.
3:42
This allocates a base amount of memory for
the array to use.
3:46
Or when I say array in Python,
know that I mean a list.
3:50
Since this is Python,
the values aren't stored in memory.
3:53
Instead, the values 1, 2, and
3 are stored elsewhere in memory.
3:57
And the array stores references
to each of those objects.
4:02
To access a value, we use a subscript
along with an index value.
4:07
So to get the first value,
we use the index 0.
4:13
And if we were to assign
this to another variable,
4:16
it would say result equal new_list.
4:18
We write out new_list since this is the
array that we're accessing the value from.
4:23
And then, a subscript notation,
which is a square bracket.
4:27
And then the index value.
4:30
As we saw, since the array has a reference
to the base location in memory,
4:32
the position of any element can
be determined pretty easily.
4:37
We don't have to iterate
over the entire list.
4:42
All we need to do is a simple calculation
of an offset from the base memory
4:45
since we're guaranteed that
the memory is contiguous.
4:50
For this reason, access is a constant time
operation on an array or a Python list.
4:54
This is also why an array crashes
if you try to access a value
5:00
using an index that is out of
bounds of what the array stores.
5:05
If you've used an array before,
you've undoubtedly run into an error or
5:09
a crash where you tried to access a value
using an index that was larger than
5:13
the number of elements in the array.
5:17
Since the array calculates
the memory address on the fly,
5:20
when you access a value with an out
of bounds index, as it's called,
5:23
the memory address returned is not one
that's part of the array structure.
5:27
And therefore cannot be read by the array.
5:32
In Python,
this is represented by an index error.
5:34
And we can make this happen by using
an index we know our array won't contain.
5:37
Now, I'm writing out my code
here inside of a text editor,
5:43
which obviously doesn't run the code.
5:46
So let's drag up this console area here.
5:48
And I'm going to write python to
bring up the Python interpreter.
5:51
And in here, we can do the same thing.
5:55
So I can say new_list = (1, 2, 3).
5:58
And now, this is an interpreter, so
it's actually going to evaluate our code.
6:00
All right, so now, we have a new list.
6:07
If I type out new_list,
it gets printed out into the console.
6:09
Okay, I can also do new_list [0], and
you'll see that I get the value 1,
6:13
which is the value stored
at the zeroth index.
6:18
Now, to highlight that index error,
we can do new_list.
6:21
And inside the square brackets,
6:25
we can provide an index that we
know our array doesn't contain.
6:27
So here I'll say index 10.
6:31
And if I hit Enter, you'll see it say
index error, list index out of range.
6:33
And those are the basics of how we
create and read values from an array.
6:39
In the next video,
let's take a look at searching.
6:42
You need to sign up for Treehouse in order to download course files.
Sign up