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
In this video we're going to look at how the remaining data structure operations work on arrays
This video doesn't have any notes.
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
In the last video, we learned what happens
under the hood when we create an array and
0:00
read a value using an index.
0:04
In this video we're going to look at how
the remaining data structure operations
0:06
work on arrays.
0:10
If you took the Introduction to Algorithms
course, we spent time learning about two
0:11
search algorithms,
linear search and binary search.
0:16
While arrays are really fast at accessing
values, they're pretty bad at searching.
0:19
Taking an array, as is, the best
we can do is use linear search for
0:25
a worst case linear run time.
0:29
Linear search works by accessing and
0:31
reading each value in the list until
the element in concern is found.
0:33
If the element we're looking for
is at the end of the list,
0:38
then every single element in the list
will have been accessed and compared.
0:41
Even though accessing and
comparing are constant time operations,
0:45
having to do this for every element
results in overall linear time.
0:49
But let's look at how
search works in code.
0:52
In Python, we can search for
an item in an array in one of two ways.
0:56
We can use the in operator to check
whether a list contains an item.
1:01
So I can say if 1 in
new_list: print(True).
1:06
The in operator actually
calls a contains method,
1:12
that is defined on the list type
which runs a linear search operation.
1:17
In addition to this, we can also use a for
1:24
loop to iterate over the list manually and
perform a comparison operation.
1:27
So I can say for
1:32
n in new_list: if n ==
1:35
1: then print(True).
1:40
And then after that,
break out of the loop.
1:46
This is more or
less the implementation of linear search.
1:49
If the array were sorted, however,
we could use binary search.
1:52
But because sort operations
incur a cost of their own,
1:56
languages usually stay away from sorting
a list and running binary search since for
1:59
smaller arrays,
linear search on it's own may be faster.
2:04
Now, again remember that since this is
an editor, this is just a text file,
2:08
none of these lines of code are evaluated.
2:13
So you can try that out in here,
so we'll copy that, and
2:15
you come down here and
say python and hit Enter.
2:19
And the when it starts up,
we can paste in our lists.
2:22
And now we can try what we just did.
2:25
So if 1 in new_list: print(True) and
2:27
there you go, it prints true.
2:32
Now because we've already
learned about linear and
2:35
binary search in a previous course,
there's nothing new going on here.
2:38
What's more interesting to look
at in my opinion is inserting and
2:43
deleting values in an array.
2:46
Let's start with inserting, in general,
2:48
most array implementations support
three types of insert operations.
2:51
The first is a true insert
2:56
using an index value where we can
insert an element anywhere in the list.
2:59
This operation has a linear runtime.
3:03
Imagine you wanted to insert
an item at the start of the list.
3:06
When we insert into the first position,
3:10
what happens to the item that
is currently in that spot?
3:12
Well, it has to move to the next spot,
at index value 1.
3:16
What happens to the second
item at index position 1?
3:18
That one moves to the next
spot at index position 2.
3:22
This keeps happening until all
elements have been shifted forward one
3:26
index position.
3:31
So in the worst case scenario, inserted
at the zeroth position of an array,
3:32
every single item in the array
has to be shifted forward.
3:37
And we know that any operation that
involves iterating through every single
3:41
value means a linear runtime.
3:46
Now the second way we can insert
an item into an array is by appending.
3:48
Appending, although technically
an insert operation in that it inserts
3:52
an item into an existing array,
doesn't incur the same run time
3:57
cost because appends simply add
the item to the end of the list.
4:02
We can simplify and
say that this is constant time.
4:06
This is a constant time operation, but
4:09
it depends on the language
implementation of array.
4:12
To highlight why that matters,
let's consider how lists in Python work.
4:15
In Python, when we create a list,
the list doesn't know anything about
4:21
the size of the list and
how many elements we're going to store.
4:25
Creating a new empty list like so,
so numbers = [ ].
4:28
So this creates a list and
allocates a space of size n plus 1.
4:35
Since n here is 0, there are no
elements in this array in this list,
4:40
space is allocated for
a one element list to start off.
4:46
Because the space allocated for the list
and the space used by the list are not
4:50
the same, what do you think happens when
we ask Python for the length of this list?
4:55
So I can say len(numbers).
5:01
We correctly get 0 back.
5:03
This means that the list doesn't use
the memory allocation as an indicator of
5:06
its size.
5:11
Because as I mentioned, it has allocated
space for a one element list, but
5:11
it returns 0, so
it determines it in other ways.
5:16
Okay, so, numbers, this list,
currently has space for one element.
5:19
Let's use the append method
defined on the type to
5:23
insert a number at the end of the list.
5:27
So you could say numbers.append and
I'll pass in 2.
5:30
Now the memory allocation and
5:34
the size of the list are the same
since the list contains one element.
5:36
Now what if I were to
do something like this?
5:42
Numbers.append, that needs to be a dot and
5:44
write another value, 200.
5:48
Now since the list only has an allocation
for one item at this point,
5:52
before I can add the new
element to the list,
5:56
it needs to increase the memory allocation
and thereby the size of the list.
5:59
It does this by calling
a list resize operation.
6:04
List resizing is quite interesting
because it shows the ingenuity
6:07
in solving problems like this.
6:12
Python doesn't resize the list to
accommodate just the element we
6:15
want to add.
6:20
Instead in this case, it would allocate
four blocks of memory to increase
6:21
the size to a total of four
contiguous blocks of memory.
6:25
It does this so that it doesn't
have to resize a list every single
6:28
time we add an element, but
at very specific points.
6:33
The growth pattern of
the list type in python is 0,
6:37
4, 8,16, 25, 35, 46 and so on.
6:42
This means that as the list size
approaches these specific values,
6:47
resize is called again.
6:52
If you look at when
the size of the list is 4,
6:55
this means that when appending four
more values, until the size of 8,
6:57
each of those append operations do not
increase the amount of space taken.
7:02
At specific points, however,
when resizing is triggered,
7:07
space required increases as
memory allocation increases.
7:11
This might signify that the append method
has a non-constant space complexity.
7:15
But it turns out that because some
operations don't increase space, and
7:21
others do, when you average all of them
out append operations take constant space.
7:26
We say that it has an amortized
constant space complexity.
7:32
This also happens with insert operations.
7:36
If we had a four element array,
we would have four elements and
7:40
a memory allocation of four.
7:42
An insert operation at that point doesn't
matter where it happens on the list, but
7:45
at that point, it would trigger a resize.
7:49
Inserting is still more expensive
though because after the resize
7:52
every element needs to
be shifted over one.
7:56
The last insert operation that
is supported in most languages
7:59
is the ability to add one list to another.
8:02
In Python, this is called an extend,
and looks like this.
8:06
I'll say numbers,
let me actually clear out the console.
8:10
Actually, we will.
8:15
Let's exit Python.
8:16
We'll clear this out, so we're back
at the top, and we'll start again.
8:18
So I'll say numbers, and
we'll set it to an empty list, and
8:21
now we can say numbers.extend.
8:26
And as an argument, we're going
to pass in a new list entirely,
8:30
so here we'll say (4, 5, 6).
8:35
And then once I hit Enter,
if I were to print out numbers,
8:38
you'll see that it now contains
the values 4, 5, and 6.
8:42
So extend takes another list to add.
8:45
Extend effectively makes a series of
append calls on each of the elements in
8:48
the new list until all of them have
been appended to the original list.
8:53
This operation has a run time of big O(k),
where k represents
8:58
the number of elements in the list that
we're adding to our existing list.
9:03
The last type of operation we need
to consider are delete operations.
9:07
Deletes are similar to inserts in
that when a delete operation occurs,
9:11
the list needs to maintain
correct index values.
9:17
So when inside shift every
element to the right,
9:20
a delete operations shift
every element to the left.
9:23
Just like the inside as well, if we
delete the first element in the list,
9:26
every single element in the list
needs to be shifted to the left.
9:31
The delete operations have an upper
bound of big O(n) also known as
9:35
a linear runtime.
9:40
Now that we have seen how common
operations work on a data structure that
9:41
we're quite familiar with, let's switch
tracks and build our own data structure.
9:45
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