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
A common data structure built in to nearly every programming language is the array. In this video we explore some of the basics of arrays
Glossary
Data Structure - A data structure is a collection of values and the format they are stored. Data structures model the relationships between the values in the collection as well as the operations applied on the data stored in the structure.
Contiguous Memory - Blocks of memory situated right beside each other with no gaps
Resources
For code and explanations in other programming languages, check the Instruction step following this video
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
A common data structure built into nearly
every programming language is the array.
0:00
Arrays are a fundamental data structure,
and
0:05
can be used to represent
a collection of values.
0:07
But it is much more than that.
0:10
Arrays are also used as building blocks
to create even more custom data types and
0:12
structures.
0:16
In fact in most programming languages,
text is represented using the string type.
0:17
And under the hood,
0:22
strings are just a bunch of characters
stored in a particular order in an array.
0:23
Before we go further and dig into arrays,
what exactly is a data structure?
0:29
A data structure is a way of
storing data when programming.
0:34
It's not just a collection of values and
the format they are stored in, but
0:37
the relationship between
the values in the collection,
0:42
as well as the operations applied on
the data stored in the structure.
0:44
An array is one of very
many data structures.
0:49
In general, an array is a data structure
that stores a collection of values
0:52
where each value is referenced
using an index or a key.
0:57
A common analogy for thinking about
arrays is as a set of train cars.
1:01
Each car has a number, and
these cars are ordered sequentially.
1:06
Inside each car, the array, or the train
in this analogy stores some data.
1:10
While this is the general
representation of an array,
1:14
it can differ slightly from
one language to another.
1:18
But for the most part,
all these fundamentals remain the same.
1:22
In a language like Swift or Java,
arrays are homogeneous containers,
1:25
which means they can only
contain values of the same type.
1:30
If you use an array to store integers
in Java, it can only store integers.
1:34
In other languages,
1:39
arrays are heterogeneous structures
that can store any kind of value.
1:40
In Python, for example, you can mix
numbers and text with no issues.
1:45
Now regardless of this nuance,
1:49
the fundamental concept
of an array is the index.
1:51
This index value is used for
every operation on
1:55
the array from accessing values,
to inserting, updating, and deleting.
1:58
In Python,
the language we're going to be using for
2:03
this course is a tiny bit confusing.
2:05
The type that we generally refer to
as an array in most languages is
2:09
best represented by
the least type in Python.
2:13
Python does have a type called array
as well, but it's something different.
2:17
So, we're not going to use it.
2:21
While Python calls it a list,
when we use a list in this course,
2:22
we'll be talking about concepts that apply
to arrays as well in other languages.
2:26
So definitely don't skip any of this.
2:31
There's one more thing.
2:33
In computer science, a list is actually a
different data structure than an array and
2:34
in fact we're going to build
a list later on in this course.
2:40
Generally though this structure is called
a linked list as opposed to just list.
2:43
So hopefully the terminology
isn't too confusing.
2:48
To properly understand how arrays work,
2:51
let's take a peek at how arrays
are stored under the hood.
2:54
An array is a contiguous data structure.
2:58
This means that the array is stored in
blocks of memory that are right beside
3:01
each other with no gaps.
3:05
The advantage of doing this is that
retrieving values is very easy.
3:08
In a non-contiguous data structure,
we're going to build one soon.
3:12
The structure stores a value, as well as
a reference to where the next value is.
3:16
To retrieve that next value,
the language has to follow that reference,
3:21
also called a pointer,
to the next block of memory.
3:24
This adds some overhead,
which as you will see,
3:28
increases the run time
of common operations.
3:31
A second ago, I mentioned that
depending on the language,
3:33
a race can either be homogeneous,
containing the same type of value, or
3:37
heterogeneous, where any
kind of value can be mixed.
3:41
This choice also affects
the memory layout of the array.
3:44
For example, in a language like C, Swift,
or Java, where arrays are homogeneous.
3:48
When an array is created,
3:53
since the kind of value is known
to the language compiler, and
3:55
you can think of the compiler as the
brains behind the language, it can choose
3:59
a contiguous block of memory that fits
the arrays size and values created.
4:03
If the values were integers,
assuming an integer took up space,
4:08
represented by one of these blocks,
then for a five-item array,
4:12
the compiler can allocate five
blocks of equally sized memory.
4:16
In Python, however, this not the case.
4:20
We can put any value in a Python list.
4:24
There's no restriction.
4:26
The way this works is a combination of
contiguous memory, and the pointers or
4:28
references I mentioned earlier.
4:32
When we create a list in Python,
4:34
there is no information about
what will go into that array,
4:36
which makes it hard to allocate
contiguous memory of the same size.
4:40
There are several advantages
to having contiguous memory.
4:45
Since the values are stored
beside each other,
4:48
accessing the values happens
in almost constant time.
4:51
So this is a characteristic
we want to preserve.
4:54
The way Python gets around this is
by allocating contiguous memory and
4:58
storing in it, not the value we
want to store, but a reference or
5:02
a pointer to the value that's
stored somewhere else in memory.
5:06
By doing this, it can allocate equally
sized contiguous memory since regardless
5:10
of the value size, the size of the pointer
to that value is always going to be equal.
5:15
This incurs an additional cost in that
when a value is accessed, we need
5:20
to follow the pointer to the block of
memory where the value is actually stored.
5:25
But Python has ways of dealing with these
costs that are outside the scope of this
5:29
course.
5:33
Now that we know how
an array stores its values,
5:34
let's look at common operations
that we execute on an array.
5:37
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up