Data Structures And Algorithms in Python - Python Data Structures Full Tutorial (2020)

[00:13] hi I'm Joe James I have master's degree

[00:16] in computer science and I'm a software

[00:17] engineer in Silicon Valley and in this

[00:20] course we're gonna learn about data

[00:21] structures in Python you might be

[00:24] wondering well why should I care about

[00:25] data structures in Python let's imagine

[00:28] for a second that your carpenter you

[00:30] wouldn't try to pound in a nail with the

[00:33] screwdriver that just doesn't make sense

[00:35] carpenters no you can't do that you also

[00:37] wouldn't try to drive into screw with

[00:40] the pair of pliers so carpenters know

[00:43] that for every task there's a best tool

[00:46] for the job

[00:47] and that's why carpenters carry around a

[00:49] tool belt full of tools and those tools

[00:51] are specialized for different tasks and

[00:53] that's exactly what you're going to do

[00:56] when you master data structures in

[00:57] Python data structures are your tool

[01:01] belt for each task you face as a

[01:03] programmer you're going to know exactly

[01:04] which data structure to use and how to

[01:06] use it you're going to save time write

[01:09] better code and do it more efficiently

[01:11] so in this course we're gonna learn

[01:13] about pythons built-in data structures

[01:15] strings lists tuples sets and

[01:18] dictionaries then we're going to

[01:21] continue to learn about queues stacks

[01:23] and heaps we're also going to learn

[01:24] about linked lists then we're going to

[01:27] cover binary search trees and graphs

[01:29] you're gonna learn how to use these data

[01:31] structures how to implement them in

[01:33] Python and you're going to learn the

[01:35] strengths and weaknesses of each of

[01:36] these data structures so let's look at

[01:39] some of the code first we'll look at

[01:41] sequence types string list and tupple so

[01:45] I put a link here to the documentation

[01:47] this is the official Python

[01:48] documentation encourage you to check

[01:50] that out if you have any questions or

[01:52] you want more detail on you needing

[01:53] these items just look at the

[01:54] documentation link here so first is

[01:57] indexing we can access any item in a

[02:01] sequence by using its index we put that

[02:04] index inside square brackets an indexing

[02:08] starts with zero the first element is

[02:11] always zero

[02:13] so the fourth element is going to be

[02:15] index three so here we have a string

[02:18] frog as four letters in it if we want

[02:21] the fourth element which is G we print

[02:24] out X of 3 that gives us the G as you

[02:27] can see in the output here if we have a

[02:30] list of pig cow and horse these are

[02:31] strings we can print out X of 1 and

[02:34] that's going to give us cow and again

[02:37] it's just square brackets and a tuple

[02:39] with four names in it and if we want the

[02:41] very first name we print out X of zero

[02:44] with the zero in square brackets and

[02:46] that gives us Kevon so that's indexing

[02:50] now let's look at slicing we can slice

[02:53] out sub strings sub lists or sub temples

[02:55] using indexes so the way indexing works

[02:59] is you put inside the square brackets

[03:01] separated by colons three possible

[03:04] parameters so we can put a start and end

[03:07] plus one and a step and I'll show you

[03:09] what each of these means so let's just

[03:12] use a string for this example computer

[03:14] the word computer again the sea is index

[03:17] 0 so here we're going to print out X of

[03:21] 1 to 4 so since we didn't put a third

[03:25] parameter that means the step is assumed

[03:27] to be 1 that's the default step so when

[03:32] we put 1 that means the O and that is

[03:35] inclusive the from is or the start is

[03:38] always inclusive the end is non

[03:40] inclusive so if we look at item number 4

[03:43] that's the U that's the fifth item it's

[03:45] not inclusive so it's really just going

[03:47] to get OMP for us and when we look at

[03:49] the result it prints out OMP now here's

[03:53] an example using a step so we print out

[03:57] X of 1 to 6 again we're going to start

[04:00] at the O because the 1 is inclusive and

[04:03] we're going to go up to 6 which is the e

[04:05] but it's non inclusive and we're going

[04:10] to do it in a step of 2 so in other

[04:13] words we're going to get to O the P and

[04:15] the T and that's what we print out opt

[04:18] so it takes every other item when we

[04:20] have a step of 2

[04:24] next we're going to not put a end

[04:27] plus-one we're just gonna leave an open

[04:29] colon there and what happens is when we

[04:31] put the open colon 3 : nothing basically

[04:36] the default is end of string so

[04:38] everything from the third item on so

[04:41] here the third item is P because we

[04:44] start counting at zero the third item is

[04:46] P and we get everything from P onward P

[04:49] UT ER so if you don't know how long a

[04:52] string is or you just want to get all of

[04:54] the remaining elements skip the first

[04:56] three three items or something you use

[04:59] an open : next we're not going to

[05:02] declare a start so we can skip the start

[05:05] by just putting : five so in other words

[05:09] our default is we're going to start from

[05:11] the beginning of the string we're going

[05:12] to get up to the sixth item because the

[05:16] v is not inclusive so c om p u and you

[05:22] can see our result here are Co MP u so

[05:26] you can see if you don't declare a start

[05:28] the start defaults to the beginning and

[05:30] if you don't declare an end the end

[05:33] defaults to the end and if you don't

[05:36] declare a step the step defaults to one

[05:38] so that's basically what's happening

[05:39] here let's look at a negative index so

[05:44] if we print out just a negative index

[05:45] negative one that counts from the right

[05:48] side of the string so here we want the

[05:51] very last item in the string we put

[05:53] negative 1 we get the are the last

[05:55] element and then here we get the last

[05:59] three items so we put a negative three

[06:02] as the from and to the end of the string

[06:06] so that gives us ter that gives us the

[06:08] last 3 elements and then if we want to

[06:11] get everything except the last two

[06:13] elements of the string we leave this

[06:15] start blank so we get everything from

[06:17] the beginning up until the last two

[06:20] items so that is how slicing works and

[06:25] it works exactly the same as we just

[06:27] covered for this string example works

[06:29] exactly the same on lists and tuples

[06:32] now let's look at adding and

[06:34] concatenating so we can combine two

[06:37] sequences of the same type using the

[06:40] plus sign let's look at a string example

[06:43] first we want to combine horse and shoe

[06:45] and we just print X so we see the result

[06:49] is horseshoe if we have two separate

[06:52] lists and we want to merge those two

[06:54] lists together we can use a plus sign

[06:56] and when we print that we get a single

[06:58] list with three elements in it and in

[07:02] the case of tuples if we have two

[07:04] separate tuples and we print the result

[07:08] we get a single tuple with four elements

[07:10] in it now it's important to note here

[07:12] for the second one to be considered a

[07:14] tupple we have to include a comma here

[07:16] if we don't have that comma it's just a

[07:18] string in parentheses if we include this

[07:21] comma that tells python that this is

[07:24] actually a tuple we can use the

[07:28] multiplying function to multiply a

[07:30] sequence using the asterisk in a string

[07:33] example if we want to print bug three

[07:35] times we just do bug times three and

[07:38] then print and you can see the result

[07:40] here is bug bug bug and the same with a

[07:42] list we have a list eight comma five and

[07:45] we want to multiply that by three what

[07:47] we get is eight five eight five eight

[07:49] five so we're not actually multiplying

[07:51] the elements by three we're multiplying

[07:53] the list by three and then the same with

[07:56] tuple we can multiply at up all by three

[07:59] and then we get basically a triplicate

[08:01] of that tupple now let's look at testing

[08:06] membership we can test whether an item

[08:08] is in or not in a sequence these are

[08:12] really easy

[08:12] it's almost English key words in Python

[08:15] they made it so simple so with a string

[08:18] let's say we have a string called bug

[08:20] and we want to check if the letter U is

[08:22] in our string we just say u in X and

[08:26] that's going to give us a boolean result

[08:28] true or false in this case u is in X so

[08:32] it returns true and now we have a list

[08:35] pig cow and horse if we print cow not in

[08:41] Y it's going to print false because cow

[08:43] is in Y

[08:45] and for a couple example we have a

[08:47] couple here with four names and if we

[08:49] print one of those names in Z we get

[08:51] true because it is in Z so it's really

[08:54] easy to check membership using in or not

[08:56] in if we want to iterate through the

[08:59] items in a sequence we can say for item

[09:03] in X an item can be any variable name

[09:06] you want it can be for number in X or

[09:08] whatever you like here I just use the

[09:10] variable name item print item if you

[09:14] want both the index and the item here we

[09:18] have a list with 7 8 and 3 in it we say

[09:22] index comma item in enumerate X the

[09:26] numerator is going to return both an

[09:29] index and an item so actually again

[09:32] these variable names are arbitrary the

[09:34] first one is going to be the index the

[09:36] second one is going to be the item

[09:37] itself so you can name them whatever

[09:39] variable name you like but you can get

[09:42] both the index and the item using the

[09:45] enumerate function and then we have

[09:47] access to both the index in the item as

[09:49] you can see the results if you want to

[09:54] get the count or the number of items in

[09:57] a sequence you can just use the Len

[09:59] function so in a string example we have

[10:03] bug we get Len of X 3 this list we have

[10:07] three items in the list so we print lin

[10:09] of y we get three and our tuple the Len

[10:12] of Z is four to find the minimum item

[10:19] Python checks is lexicographically which

[10:22] means the smallest on the ASCII scale so

[10:25] you can use the minimum function on

[10:27] either alpha or numeric types but you

[10:29] cannot mix alpha and numeric types into

[10:32] a list or a temple you'll get an error

[10:34] so here on our string example we print

[10:37] the min of X we get the smallest letter

[10:39] which is B and in the list we print the

[10:43] minimum of Y which is cow because it

[10:47] basically is going to compare the first

[10:49] letter first and see it comes first

[10:50] alphabetically and the same with the

[10:53] tupple we print the one that comes first

[10:55] alphabetically in that's Craig so that's

[10:57] the min

[10:59] the maximum item in a sequence again

[11:02] lexicographically and it can be done

[11:05] alpha or numerically but not both

[11:09] so it's bug the maximum is you and with

[11:12] pig cow and horse we see that pig

[11:14] actually comes last alphabetically and

[11:16] in our couple example in is the last

[11:21] letter alphabetically we can find the

[11:27] sum of items in a sequence they have to

[11:30] be numeric so if you mix in other items

[11:32] that are non numeric let's say strings

[11:34] or something it's going to give you an

[11:36] error so in the case of a string we

[11:40] throw a string in here and we find that

[11:42] we print sum you're just going to get an

[11:44] error but if we have a list of numbers

[11:47] and we print the sum of that list you

[11:50] can see we get 27 you can also do

[11:53] slicing you can combine slicing to get a

[11:56] sum of part of the list so if here we

[11:59] want to just get the last two numbers 8

[12:02] and 12 we can do negative 2 onward and

[12:05] that gives us 20 because we adding 8 and

[12:08] 12 only and for the tupple we have

[12:12] another tuples e with 4 items in it and

[12:14] we add those together we get 80 sorting

[12:21] returns a new list of items in sorted

[12:23] order but it returns it as a list so

[12:28] here we have a string bug we print the

[12:31] the sorted version of X and what we get

[12:34] back is the letters basically separated

[12:37] and sorted as a list elements of a list

[12:42] our list example it's Caesar these are

[12:45] strings it puts them in sorted order and

[12:48] it returns to the list in sorted order

[12:51] and it's important to understand this

[12:53] does not change the original list the

[12:55] sorted function is not an in-place sort

[12:58] it returns a new list with a sort result

[13:01] in our example we have four names here

[13:04] and we put those in sorted order and get

[13:07] Craig Jenny Kevin and Nicholas

[13:12] so let's say you don't want to sort by

[13:14] the first letter that you want to sort

[13:16] instead by the second letter well you

[13:17] can use a lambda function to do that I'm

[13:20] not going to cover lambda functions in

[13:21] detail in this video but I want to make

[13:24] you aware that you can sort stuff either

[13:25] by reverse order or using some other

[13:29] parameter and we do that using key

[13:32] equals some lambda function and here we

[13:35] for each item K you can again you can

[13:37] use as an arbitrary variable name k

[13:39] we're gonna take the one item which is

[13:42] the second letter so here it's going to

[13:44] be e i e and r and we're going to put

[13:49] those in sorted order based on the

[13:51] second letter and we can see those with

[13:54] the second letter in sorted order if we

[13:57] want to get the count of items in a

[13:59] sequence we can use the count function

[14:01] and here we're going to we have the word

[14:03] hippo in a string we're going to count

[14:06] the number of times the letter P appears

[14:08] in hippo and we can see that the result

[14:09] is two here I added a word cow to the

[14:12] list twice so if we get the count of the

[14:15] word cow we see that that also is two

[14:17] and here we just get the word count of

[14:20] Kevin in this list and we can see that

[14:22] is one and we can get the index of an

[14:28] item by passing in that item and asking

[14:31] for the index of it and what it's going

[14:33] to give us is the index of the first

[14:34] occurrence of the item so in the case of

[14:37] hippo if we're looking for P it's going

[14:39] to give us let's see H is zero I is one

[14:42] the first P is two so we can see the

[14:45] result we get is two it stops looking

[14:48] after it finds the first item that

[14:50] matches in the sequence and our list

[14:53] example we have cow we have two cows in

[14:56] here and we're going to get the index of

[14:58] cow and we're going to get one as a

[14:59] return value and then for the tuple we

[15:03] get the index of Jenny and we can see

[15:04] that's 0 1 2 so unpacking of items in a

[15:09] sequence and we can unpack those into a

[15:12] number of variables it's important that

[15:14] our number of variables exactly matches

[15:17] the length of that list or string

[15:18] because we're if not we're going to get

[15:20] an error so here we have a list x equals

[15:25] cow and horse and if we won't unpack

[15:27] those and assign each of these values to

[15:30] its own variable we can say a comma B

[15:33] comma C equals x and then that's

[15:36] basically going to put these in order

[15:38] assigning them to a b and c so when we

[15:40] print out a b and c now these are each

[15:43] separate variables pig cow and horse so

[15:47] that's called unpacking in the next

[15:51] lecture we'll learn more detailed

[15:52] features of lists tuples sets and

[15:55] dictionaries so now let's dig into some

[15:57] of the specifics of lists tuples sets

[16:00] and dictionaries again as a recap lists

[16:03] are the most general-purpose data

[16:06] structure in python you're going to use

[16:07] these for almost everything in Python I

[16:10] should say a lot of stuff and this can

[16:12] grow and shrink in size as needed so you

[16:15] can continue adding items to them or

[16:16] deleting items from them and the size of

[16:18] the list will shrink accordingly

[16:19] automatically python does that for you

[16:22] and this is our a sequence type so all

[16:25] of the sequence functions that we

[16:27] covered above are all useful for lists

[16:29] and they're also sortable a lot of data

[16:32] structures are not sortable lists are

[16:35] that makes them useful for sorting data

[16:38] so let's look at some of the

[16:39] Constructors for lists how do we create

[16:42] a new list so there are few different

[16:44] ways of doing this one we can create an

[16:46] empty list by just saying x equals list

[16:49] and in parentheses that calls the list

[16:50] constructor with no no parameters and it

[16:54] gives us a new empty list and another

[16:57] way to do it is this is probably the

[16:59] most common way is to pass in the items

[17:01] we want in that list inside square

[17:03] brackets these square brackets we can

[17:06] separate each item with a comma we can

[17:08] pass in here we have multiple different

[17:10] data types we have strings we have

[17:12] integers and in floating point values

[17:14] all in the same list and that's one nice

[17:16] thing about the versatility of lists you

[17:18] can see here we can also create a tuple

[17:22] which will cover tupple constructors in

[17:24] a minute but as we create a new tuple

[17:26] and we can pass that tupple in to the

[17:28] list constructor just by putting it

[17:30] inside the parentheses in the list

[17:33] constructor and that will create a new

[17:35] list and Pat and assign it to Z

[17:38] and lastly we can use list

[17:39] comprehensions I'm going to have another

[17:41] section on list comprehensions in a few

[17:43] minutes so I just wanted to give you a

[17:46] little teaser of what you can do with

[17:48] list comprehensions to create new lists

[17:50] with sets of values so here we're going

[17:53] to create a new list called a and we put

[17:55] square brackets and basically inside of

[17:58] that is a for loop in the range function

[18:01] so we can say m4m in range 8 that's

[18:06] going to count from 0 to 7 and for each

[18:09] value M it's going to assign M to the

[18:12] list so we here we get a new list with

[18:14] value 0 through 7 in it and then if we

[18:18] want to do something more fancy here's

[18:19] just a taste of it I in range 10 so

[18:24] we're going to count 0 through 9 and

[18:26] we're only going to take the ones that

[18:28] are greater than 4 if I is greater than

[18:31] 4 then it'll pass I squared into the

[18:34] list so here we get 5 through 9 squared

[18:38] into this new list so that's a taste of

[18:41] what you can do with list comprehensions

[18:42] to create a new list using a for loop

[18:45] and the range function you can also add

[18:47] if to filter items and you can do

[18:50] whatever you want to the items that

[18:52] you're iterating now let's take a look

[18:56] at the delete function if we want to

[18:58] delete a single item from a list or

[18:59] we're going to delete the entire list we

[19:01] can do that using del here we have a

[19:04] list called X and we have 5 3 8 6 in it

[19:08] and if we want to delete the one thigh

[19:10] tum' which is the 3 and we can just pass

[19:13] in the one in the square brackets the

[19:16] index of the item del x of 1 that

[19:19] deletes the one time 2 3 and we can see

[19:22] the new list there and if we want to

[19:24] delete the entire list we just say del X

[19:29] next the append function if we want to

[19:31] add an item on to the list this is going

[19:34] to add it to the tail end of the list we

[19:37] create a new list 5 3 8 6 when we do X

[19:39] dot append and then we pass in that 7 is

[19:42] an argument then we can append 7 to the

[19:44] tail of the list extend basically is

[19:49] similar to the plus function that we

[19:51] used up

[19:52] we're basically combining two separate

[19:55] lists into one list so here we have x

[19:58] equals 5 3 8 6 y equals 12 13 and we can

[20:02] extend x with y and then we print out

[20:06] the new x and you can see we have all 6

[20:07] items in it we could also have used the

[20:11] plus for that so insert we can insert an

[20:16] item at a given index in the list here

[20:19] we have the same list we used above and

[20:21] we insert at the one position the item 7

[20:25] so here we can see the result is 5 7 3 8

[20:29] 6 this is the position or the index we

[20:32] want to insert it at and this is the

[20:34] item we want to insert and then we can

[20:36] see here that you can not only insert an

[20:39] integer or a floating point value you

[20:41] can Sir tale' issed

[20:42] into a list as an item we have a list

[20:45] here with a and M min as two items and

[20:47] then we print out the revised list and

[20:49] we see that the second item are the 1

[20:52] thight 'm in the list is another list

[20:55] with a and M in it so that's the insert

[20:59] function let's take a look at pop pop

[21:01] basically pops off the last item from

[21:04] the list and it returns that item so you

[21:07] can use that item if you want to you

[21:10] don't have to but you are basically

[21:13] shrinking your list by one item so here

[21:15] we have 5 3 8 6 as we pop off one item

[21:17] we're using X dot pop that pops off the

[21:20] last item is 6 we didn't assign it to

[21:23] anything or do anything with it but we

[21:24] can see the new list is just 5 3 8 here

[21:27] we print X dot pop and it pops off the 8

[21:30] the last item on the list now and we

[21:33] print that so we can see the the return

[21:35] value is 8 when we do X dot Pop remove

[21:41] we can remove the first instance of an

[21:43] item so if there are multiple instances

[21:45] of an item Python is going to start

[21:48] searching at the beginning of the list

[21:49] until it finds that item that matches

[21:51] it's going to stop searching is going to

[21:53] remove that item so here we have

[21:55] multiple threes in this list we're just

[21:57] going to remove the very first one so if

[22:00] we do X don't remove 3 we can see the

[22:02] revised list is without the first 3

[22:06] reverse function can reverse the order

[22:08] of a list

[22:09] it's an in-place reverse which means

[22:12] that it changes the original list the

[22:15] original list is no longer the same as

[22:17] it was so here we have an original list

[22:19] of x equals 5 3 8 6 and then we apply

[22:22] reverse to it it's not putting these in

[22:24] sorted order

[22:25] it's simply reversing the order of the

[22:28] items so we get 6 8 3 5 as the reversed

[22:32] list and then we can apply the sort

[22:36] function to it which is also an in-place

[22:38] sort you should note that we can use

[22:41] sorted of AX

[22:43] these are Python functions sort there

[22:46] are two different ones and you're a

[22:47] little bit confusing here sort is an

[22:49] in-place sort sorted returns a new list

[22:53] so it's not an in-place sort so here

[22:57] using the X dot sort function we don't

[23:02] pass anything in as a parameter to the

[23:04] sort function we're applying the sort

[23:06] function to the X which is what's

[23:09] calling the sort function and we can see

[23:13] that we put these items in sorted order

[23:15] and then if you want to do a reverse

[23:17] sort we can pass into the sort function

[23:20] a parameter called reverse equals true

[23:23] and that will give you a descending sort

[23:25] so we get 8 6 5 3 if we try and use

[23:28] reverse equals true and again this is

[23:32] the same parameter that you would use in

[23:35] the sorted function if you wanted to

[23:37] reverse sort using sorted function but

[23:39] this one is an in-place sort as you can

[23:44] see Python lists are really powerful

[23:46] data structure and they have a lot of

[23:47] built-in functions and features but

[23:50] unless you want to become the Carpenter

[23:51] who tries to turn every problem into a

[23:53] nail by pounding on it with a hammer

[23:54] let's continue on in the course and

[23:57] learn other data structures and see what

[23:59] they can be used for so let's take a

[24:03] closer look at tuples just to recap we

[24:06] said that tuples are immutable that

[24:09] means they can't be changed and you

[24:11] can't add items to the tupple once it's

[24:14] created they are useful for fixed data

[24:18] if you're gonna have a lot of changes to

[24:20] your data then you should use lists they

[24:23] are useful for fixed data they're much

[24:25] faster for finding items than a list is

[24:27] and these are sequence types which means

[24:30] that all of the above functions are

[24:32] still going to work so you can use all

[24:34] those sequence functions that we've used

[24:36] above on tuples so let's take a look at

[24:41] some of the Constructors for tuples how

[24:43] do we create a new tuple there are a few

[24:45] different ways of doing this

[24:47] the tupple uses the parentheses as its

[24:51] constructor so here we can create an

[24:53] empty new tuple using x equals

[24:56] parentheses empty parentheses or if we

[24:58] want to pass in items 1 2 3 the

[25:02] parentheses are actually optional so

[25:04] even when you take the parentheses away

[25:06] 1 2 3 separated by commas Python notices

[25:10] this is a tupple now if you want a

[25:13] couple of just one item you still have

[25:15] to put the comma that comma tells python

[25:18] that this is a one item tuple and not

[25:21] just an integer and then you can see

[25:25] that we print here X and the type of X

[25:27] and we get a couple with just the two in

[25:30] it and the class is a tupple now let's

[25:35] create list one equals two four six this

[25:39] is a list with three items in it we pass

[25:41] that list into the tupple constructor

[25:43] and it creates a tuple called X so here

[25:48] we print out X which is that tupple two

[25:51] four six you can now see that it doesn't

[25:53] have square brackets it has the

[25:54] parentheses around it because it's at up

[25:56] all and we print out the type of X and

[25:58] it's a class couple so there are several

[26:01] different ways there to create tuples

[26:04] tuples again are immutable however this

[26:08] may be a little confusing so pay

[26:09] attention member objects may be mutable

[26:12] if you have a list as one of the items

[26:16] inside a couple you can't make changes

[26:19] to that list you can add or delete items

[26:21] from that list you can change the items

[26:25] in the list so let's take a look at what

[26:28] we mean here if we have a couple with

[26:31] one two three in it

[26:32] and then we try to delete the one theit

[26:34] 'im which is the two that's going to

[26:36] fail that's going to give us an error in

[26:37] Python if we try to change the value of

[26:41] the two to eight that also fails we

[26:44] cannot change the value of the two so it

[26:48] looks like the tupple is totally

[26:49] immutable and unchangeable and we get

[26:52] one two three so even if you try those

[26:54] you're just going to get an error but

[26:56] look at this if we assign a list a two

[27:00] item list as the zeroeth item in this

[27:02] tuple well that list we can we can just

[27:06] mutable so we can change or drop items

[27:09] off of this list if we want so here

[27:11] we're going to pass in two indices the

[27:15] zero tells python that yeah we want the

[27:18] zeroeth item of tuple Y which is this

[27:20] list with one and two in it and in that

[27:23] list we want the one thight 'm which is

[27:26] the two and that's what we're going to

[27:28] delete so we're basically deleting this

[27:30] two from this list and then we're going

[27:35] to print out y and we can see that the

[27:36] result is we get a single item list with

[27:40] the 1 and a 3 so we were able to edit

[27:43] this list with the one and two we're

[27:46] able to drop items off of that list and

[27:50] then if also if we want to add items to

[27:52] the tempo we cannot just add or append

[27:55] however we can use this concatenation

[27:57] function where we do y plus equals an

[28:01] additional temple and it will it will

[28:03] merge the two tuples into one so here

[28:06] again you need the comma to tell python

[28:09] that this is a tupple and not just an

[28:11] integer it's a one item tuple so if we

[28:14] do y plus equals four we can see that

[28:17] the four is added on to our original

[28:19] type of y so concatenating will work now

[28:24] let's look at sets set store non

[28:28] duplicate items so unique items are

[28:31] really what sets are ideal for you get

[28:35] very fast access compared to lists and

[28:37] the reason why is when you iterate

[28:38] through a list looking for an item the

[28:42] only way to do it is to start at the

[28:43] beginning and look at every single item

[28:44] and do a

[28:45] comparison so if you have a billion

[28:47] items in that list you're going to do a

[28:48] bill you may have to do a billion

[28:49] comparisons to find that item but in a

[28:53] set it hashes that item so it can find

[28:56] it instantly using the hash it has much

[29:00] faster access than lists so especially

[29:02] for very large data sets it has much

[29:04] faster access to items than lists it's

[29:08] great for checking membership the set is

[29:10] also great for doing math set operations

[29:13] things like Union and intersection and

[29:16] keep in mind that sets are unordered

[29:18] which means you cannot sort a set so

[29:23] let's take a look at the Constructors

[29:24] for a set there are a few different ways

[29:26] to create a new set we can use these

[29:29] curly braces and you'll see here as we

[29:31] pass in 3535 we've got some duplicates

[29:34] there

[29:34] what python does is it filters out the

[29:37] dupes and gives us a set with just three

[29:39] and five in it and if we create a new

[29:43] empty set we can just use the set

[29:45] constructor with parentheses and then we

[29:48] print out y you can see we get an empty

[29:49] set if we want we can also pass in a

[29:52] list here we have two three four and we

[29:55] call the set constructor using the

[29:57] parentheses and our pass in our set is a

[29:58] parameter and we're getting a new set Z

[30:01] and then we print that out we get two

[30:03] three four as a set so that's a few

[30:05] different ways to create sets some of

[30:08] the set operations you can use you can

[30:12] add an item to a set by using X dot add

[30:16] so here we add a seven to this list of

[30:19] three eight five and then we remove a

[30:22] three using X dot remove so you can see

[30:24] the result here is that after you add

[30:27] the seven you get the four item list and

[30:29] when you delete the three you get back

[30:33] down to eight five and seven so add and

[30:36] remove both work for sets and then if

[30:38] you want to get the length of a set you

[30:40] just use Lin checking membership we use

[30:43] in or not in so if we want to check if

[30:46] five is in the set we just do five in X

[30:49] or five not in X and that's going to

[30:51] give us a boolean return here we can see

[30:54] we got true for five and X

[30:56] and then we can also pop a random item

[30:59] bear in mind the set is not ordered so

[31:02] we don't know which item we're gonna get

[31:04] we're gonna get a random item off the

[31:05] set and then here it actually the pop

[31:08] function returns the item itself and so

[31:11] we're printing out that item and the new

[31:13] list X so here we can see the item it

[31:17] gave us is 8 and the new set is 5 and 7

[31:21] and then if we want to delete all the

[31:24] items from the set and get our empty set

[31:26] back we can do X clear let's look at

[31:30] some of the mathematical set functions

[31:32] so we said that we can do intersection

[31:35] and union which are and and or functions

[31:38] so the intersection is done using an

[31:41] ampersand with two sets and the union is

[31:45] done using the pipe or bar so a set one

[31:48] pipe set to symmetric difference or

[31:52] exclusive or in other words and items

[31:55] that are in set one but not in set two

[31:57] or in set two but not in set one and

[32:00] they a difference we can just use a

[32:03] subtraction so set one - set - because

[32:06] it's the difference between those two

[32:07] and then we can check if one set is a

[32:10] subset or fully contained and the other

[32:12] set using the less than or equal to or

[32:14] greater than or equal to super first

[32:17] superset so we have two different sets

[32:20] here set one and set two and when we do

[32:24] the intersection we can see that the

[32:26] intersection is three they both have

[32:28] this value three when we do the Union we

[32:33] get all the items that are in either set

[32:35] so 1 2 3 4 5 so when we do exclusive or

[32:39] using the up caret we get 1 2 4 5 which

[32:44] is all the items that are in one set or

[32:46] the other but not in both and then - we

[32:50] get 1 & 2 and then since neither set is

[32:54] a subset of the other set both of these

[32:55] to return false so those are some of the

[32:58] mathematical set operations you can do

[33:01] on sets now let's take a look at

[33:04] dictionaries so first to recap on

[33:06] dictionaries dictionaries are key value

[33:09] pairs

[33:10] so most programming languages have some

[33:13] equivalent of the Python dictionary they

[33:15] don't always call it that some of them

[33:17] call it a hashmap

[33:18] Java calls it a hashmap dictionaries are

[33:21] unordered this means they cannot be

[33:24] sorted they can be converted to a list

[33:26] and then sorted as a list

[33:28] but it cannot be sorted as a dictionary

[33:30] so some of the functions that we can do

[33:32] how do we create new dictionaries let's

[33:35] take a look at our constructors so if we

[33:38] create a new dictionary using the curly

[33:40] braces then we need to pass in members

[33:42] key value pairs separated by a colon and

[33:46] then spaced out with commas okay so here

[33:49] we have three key value pairs the key is

[33:52] on the Left colon and then the value and

[33:55] these are three different ways of

[33:57] creating exactly the same dictionary so

[34:00] in the second example we pass in a list

[34:03] of tuples

[34:04] so the tuple contains two items it has

[34:08] the string and separated by a comma that

[34:11] floating point so there are three tuples

[34:14] in the list passed into the dictionary

[34:17] constructor which is in parentheses and

[34:19] then the third one passes into the

[34:22] dictionary constructor notice search

[34:24] there are no quotation marks around the

[34:26] strings here we just have pork equals 25

[34:29] point 3 in Python knows that this is a

[34:32] string so these are three different ways

[34:35] to create dictionaries in Python they

[34:40] all do exactly the same thing some of

[34:43] the operations of dictionaries now we

[34:45] notice that shrimp is not in our

[34:46] dictionary so if we want to add shrimp

[34:49] we can say X of shrimp equals 38.2 this

[34:54] in this case there is no shrimp in the

[34:56] dictionary add so it's going to add a

[34:58] new key value pair for shrimp 38.2 if

[35:02] there already was a shrimp in the

[35:04] dictionary then it would update the

[35:06] value to 38.2 for shrimp it looks up

[35:10] this key and it will update the value

[35:13] for it so this is add or update and

[35:16] python is not going to tell you if that

[35:18] was in there or not if you if you want

[35:20] to check you can check first right if

[35:22] shrimp

[35:23] dictionary but if you just do this X of

[35:26] shrimp equals 38.2 it's going to

[35:29] overwrite anything that was already in

[35:30] the dictionary for shrimp if you want to

[35:34] delete an item this is just del X of

[35:38] shrimp is going to delete shrimp for

[35:39] them a dictionary and then you can see

[35:41] that we print out the new dictionary

[35:43] there's no shrimp in it and if we want

[35:46] to get the length of the dictionary you

[35:47] can print Lin of X they'll tell you how

[35:50] many key value pairs are in the

[35:51] dictionary and if you want delete all

[35:54] the items from dictionary you can use X

[35:56] dot clear and lastly to delete the

[35:59] entire dictionary and free up the memory

[36:02] that it's using you can use del X so to

[36:07] access keys and values in the dictionary

[36:10] you can access these separately or you

[36:13] can access them together so here are a

[36:15] few different ways of doing that we have

[36:16] this dictionary Y with pork beef and

[36:19] chicken in it those are the keys the

[36:21] strings pork beef and chicken so if we

[36:24] do y dot keys we get a list of pork beef

[36:29] and chicken it dumps these out as a list

[36:31] if we do wideout values it dumps these

[36:34] out as a list the values those 14-point

[36:37] values and if we do items we can say

[36:41] print Y dot items it's going to print

[36:44] out all the key value pairs so here at

[36:47] Princeton amount is a list of tuples or

[36:49] key value pairs to check membership in

[36:53] just the keys you don't have to specify

[36:56] keys you can if you want you can say

[36:58] beef in Y dot keys or you can just

[37:00] simply say beef in Y and that's gonna

[37:03] check in wise keys only it's not going

[37:06] to check in to values if you want to

[37:07] check for membership only in the values

[37:09] you can check clams in Y dot values and

[37:13] all these membership tests are going to

[37:15] have a boolean return true or false so

[37:20] to iterate a dictionary keep in mind

[37:24] that these items are in random order and

[37:26] you're not going to be able to iterate

[37:28] them in any kind of sorted order it's

[37:30] going to python is going to give them

[37:31] back to you in whatever order at once so

[37:34] for key in Y print key

[37:37] that will give you all the keys in the

[37:40] dictionary one at a time and then you

[37:43] can get the value by saying why of key

[37:47] so here you can see we printed out each

[37:50] key and its value if we want to iterate

[37:53] with a separate variable for both the

[37:56] key and the value sometimes this is

[37:58] helpful if you're doing a lot of

[37:59] operations inside the loop you can put

[38:03] whatever variables you want

[38:04] I used K comma V as my variable names

[38:07] and what you do is you iterate Y dot

[38:11] items and then items returns at up all a

[38:14] to item couple of the key and the value

[38:16] and then it assigns them to whatever

[38:19] variable names you have here so K and V

[38:22] in my case so you can see the result

[38:25] here is the same we iterate through the

[38:27] items we print out both the key and the

[38:30] value so that wraps up this video on

[38:34] built-in Python data structures now you

[38:37] should have a pretty good understanding

[38:38] of how to use pythons built-in data

[38:41] structures strings lists tuples sets and

[38:44] dictionaries make sure you download the

[38:46] code and get some practice using it

[38:49] because it's hands-on practice is going

[38:51] to make you a good programmer in the

[38:53] next section we'll learn how to use list

[38:55] comprehensions to create new lists hi

[38:58] I'm Joe this chapter we're going to

[39:00] cover a pretty cool feature of python

[39:02] called list comprehensions that enables

[39:05] you to create new lists of values using

[39:08] a comprehension are basically sort of a

[39:10] for loop and iteration inside of a list

[39:14] creator so our basic format is transform

[39:18] sequence and filter so we can apply a

[39:21] filter to it if we want and we put that

[39:24] inside square brackets and that's going

[39:26] to the result is going to be assigned to

[39:28] a new list so we're going to use the

[39:30] random module a little bit in this don't

[39:33] need that for all this comprehension

[39:34] before it to my examples so I'm going to

[39:36] import that so we have a series of about

[39:39] 10 examples or something I'll show you

[39:41] and get increasingly more complex so

[39:45] here we're going to just get values

[39:46] within a range typically in list

[39:49] comprehensions or anything is the range

[39:50] function

[39:51] here we just use range of 10 and you

[39:54] know the range function returns a

[39:56] sequence of numbers in this case it

[39:58] starts with 0 which is a default and it

[40:01] goes up through 9 because the 10 is non

[40:03] inclusive so 0 through 9 and what we're

[40:06] going to add to this new list is X for X

[40:09] in that range so in this part the first

[40:14] X we could apply some sort of a

[40:17] transform or a function on that X if we

[40:19] wanted to x squared to X whatever we

[40:21] want and then this is where we declare

[40:25] the variable each X in this range so the

[40:31] result is a series of values under 10 so

[40:35] 0 through 9 under 10 integers okay so

[40:41] that's the simplest example of a list

[40:43] comprehension now let's look at some of

[40:45] the other more crazy stuff that you can

[40:46] do with list comprehensions we could get

[40:49] all the squares if we want I told you we

[40:50] can we could apply a transformation to

[40:52] the X if we want so here we declare our

[40:55] variable is X as we iterate through

[40:58] under 10 which is this list we just

[40:59] created okay so we don't necessarily

[41:02] have to use the range function we can

[41:04] use any sequence here which means we

[41:07] could use a list we could use a couple

[41:10] set or even a string or a range function

[41:15] so x squared for X in under 10 so it's

[41:19] going to iterate through these it's

[41:21] going to return the square of each one

[41:23] of them and it's going to assign that to

[41:25] this new list called squares and then

[41:28] we're going to print out squares so you

[41:30] can see the result is 0 through 81 the

[41:33] squares of the previous list ok let's

[41:37] see what else we can do

[41:38] get odd numbers using mod ok so odds

[41:42] equals x for X in range 10 so here we're

[41:48] going to just basically iterate through

[41:50] 0 through 9 the variable we're going to

[41:53] use is called X and we're gonna send X

[41:57] to this odds list but here look we apply

[42:01] a test a condition if X mod 2 is

[42:05] 2:1 in other words if it's odd if X is

[42:09] odd then we'll send it to this odds list

[42:12] when we print it out we see that we get

[42:14] one three five seven and nine now let's

[42:18] get them multiples of ten so we're going

[42:20] to use the arrange function again as our

[42:22] sequence zero through nine and instead

[42:26] of adding X to the list we're gonna add

[42:29] x times ten so this is not a whole lot

[42:31] different from me x squared we did we

[42:35] get two multiples of ten so zero through

[42:38] nine D now let's get all the numbers

[42:42] from a string so we start out with a

[42:44] string named s that has a combination of

[42:47] letters and numbers in it maybe

[42:49] sometimes you want to filter out and

[42:51] delete all the numbers or whatever but

[42:52] here what we're gonna do is just create

[42:54] a new list with all those numbers so

[42:57] nums

[42:57] equals x for X in s in other words we're

[43:01] going to iterate through the letters or

[43:05] characters in s and we're going to test

[43:09] if each one is numeric and if it is then

[43:12] we're gonna add it to this list and then

[43:15] when we print out the list

[43:17] we're basically we get a list so I'm

[43:19] gonna use this little join function to

[43:21] join the numbers into a single single

[43:24] string so we get 207 3 in other words we

[43:28] managed to grab all the integers in this

[43:30] string so here we're going to get the

[43:33] index of a list item and we're going to

[43:37] do that by using the enumerate function

[43:39] so we iterate using enumerate names name

[43:43] this is a list the names is a list and

[43:46] we're going to numerator

[43:47] the enumerate returns both a key and a

[43:50] value for each item in the list so we

[43:53] start out with Cosmo and 0 and then we

[43:56] get Pedro and one on you and - right so

[43:59] we're eating each name we're getting the

[44:01] key and the value our test is if the

[44:05] value is equal to Anya okay so that

[44:08] means here then the key is going to be

[44:10] equal to two and then what do we add to

[44:13] the list well we add K we add K we add

[44:16] the key we had to so at the end result

[44:19] here we get a list with just a two in it

[44:21] because that's the only one that passes

[44:23] this test and then when we print out the

[44:28] zeroeth item in the list of course it's

[44:30] a twos it's a one item list and we can

[44:36] also delete an item from a list here we

[44:39] have a list of letters actually a string

[44:41] we start by iterating through the string

[44:44] ABCDE F converting it to a list of

[44:47] letters just by adding each letter in

[44:49] the string to a list so now we have a

[44:52] list of ABCDE F as individual letters we

[44:55] shuffle those using this random function

[44:57] so now we have shuffled letters ABCDE F

[45:01] and each one of them is basically a

[45:03] string object in the letters list so

[45:08] we're going to create a new list that

[45:10] passes this test a for a in letters if a

[45:15] is not C right in other words every

[45:18] letter in this list except for uppercase

[45:21] C so we're gonna get a B D EF and you

[45:25] see when we print them out we get DF e a

[45:28] B but we do not get C so we get yeah

[45:30] that works pretty cool huh

[45:34] we basically filtered out the C wherever

[45:37] it is in the list we don't know but we

[45:39] filtered it out that wraps up this

[45:41] lecture on list comprehensions you can

[45:44] download this code from my github site

[45:46] and use tests to code and run these

[45:48] examples and I encourage you to use list

[45:51] comprehensions these are really a useful

[45:52] tool in Python for creating lists in

[45:57] this section we're going to learn how to

[45:58] use stacks queues and heaps first we'll

[46:02] cover the fundamentals of each of these

[46:03] data structures what key operations each

[46:06] of them has and then how you can

[46:07] implement them in Python these are three

[46:10] very useful data structures let's start

[46:13] by learning about stacks a stack is a

[46:16] last in first out data structure that's

[46:20] called LIFO so what that means is that

[46:23] all the push and pop operations are to

[46:26] the top of the stack the only effect the

[46:29] top item on the stack the only way to

[46:32] access

[46:32] the bottom items on the stack like in

[46:34] this diagram item one is to first remove

[46:37] all of the items above it we have a

[46:40] couple of different key operations here

[46:42] push allows us to push an item on to the

[46:45] top of the stack and we use the pop

[46:48] command to pop an item off of the top of

[46:51] a stack some other stack operations are

[46:54] peak sometimes you might want to get an

[46:56] item off of the top of the stack without

[46:58] actually removing it let's say we need

[47:00] access to the top item we want to know

[47:02] what it is and we can use the peak

[47:04] command to see a copy of the top item

[47:07] without actually removing it from the

[47:09] stack or clear to remove all the items

[47:14] from the stack and empty the stack out

[47:16] there are a lot of different use cases

[47:18] for stacks one very common use case is

[47:21] the command stack all computer programs

[47:25] track each command that you execute and

[47:28] most programs you use have the option of

[47:31] undoing the previous command in order to

[47:34] do that the program has to keep track of

[47:36] which commands you've executed in which

[47:39] order so it does that using a stack each

[47:42] time you execute a command it pushes

[47:45] that command on to the stack so that has

[47:48] a record of it and if you click the undo

[47:50] button it's going to pop the last

[47:52] command off of the stack and it's going

[47:55] to reverse that command so the command

[47:59] stack is used to execute the undo

[48:02] function in programming now let's take a

[48:05] look at how stacks can be implemented in

[48:07] code we have the Python list which makes

[48:10] a great foundational data structure to

[48:13] store the stack in and actually Python

[48:15] gives us most of the functionality that

[48:17] we need to create a stack with the list

[48:20] so the underlying data structure beyond

[48:24] our stack is going to be a Python list

[48:26] Python gives us the append function

[48:29] which we can use to push an item onto

[48:32] the stack and it gives us a pop function

[48:34] which we can use to remove an item from

[48:37] the stack we're actually pushing items

[48:39] onto a list and opting them from a list

[48:41] so here's one implementation using the

[48:45] Python

[48:46] list we can create a new stack my stack

[48:49] equals an empty list and then we can

[48:51] push items onto the stack using a pin is

[48:54] here we pushed for 7 12 and 19 onto the

[48:58] stack and then when we print out the

[48:59] stack we can see four items now a little

[49:04] more test coat here when we pop an item

[49:07] off of the stack we can see that we get

[49:08] to 19 first and we pop the second item

[49:11] off we get to 12 so it's popping off the

[49:14] last item first which is exactly what we

[49:16] want

[49:17] so that's typical stack operation

[49:19] however it's using a Python list now if

[49:24] we wanted to write a wrapper class so

[49:26] that we can add some additional

[49:27] functionality to our stack that's

[49:29] actually not that hard so let's take a

[49:31] look at how that can be done here's a

[49:34] stack using a list as the underlying

[49:36] data structure but using a wrapper class

[49:39] so that we can rename our functions as

[49:41] we like and we can also add additional

[49:43] functions and features to our stack so

[49:47] we'll start with a constructor an init

[49:50] function and this basically just has a

[49:53] new list it creates an empty list just

[49:55] as we did before the push is going to

[49:59] add an item so we receive an item and we

[50:02] just use the append function to add that

[50:04] item on to the list what the user is

[50:07] going to see is he's pushing an item on

[50:09] the stack but what we're doing behind

[50:11] the scenes is appending that item to a

[50:14] list next the pop function first we want

[50:19] to check if the list actually has items

[50:21] on the list if the list is empty we

[50:24] don't want to try a pop operation if

[50:26] there's at least one item on the list

[50:28] then we'll pop that item off and return

[50:30] it

[50:31] the peek function allows us to just look

[50:34] at the top item on the list and return

[50:36] that item but without taking it off so

[50:40] here we return the top item on the list

[50:43] but without removing it and lastly if

[50:47] someone wants to print out the stack or

[50:49] show all the items that are on the stack

[50:51] what we're going to do is just show the

[50:53] string representation of the list now

[50:57] let's look at some tests

[50:59] see how our stack works my stack equals

[51:02] stack and then we can push an item will

[51:05] push a1 will push a3 and then when we

[51:08] print out the stack we can see that yeah

[51:09] we have a1 and a3 on our stack and when

[51:13] we pop on an item off of the stack we

[51:15] get the three which was the last item

[51:17] that we put on the stack when we peak we

[51:20] get the one which is the only item

[51:21] actually left on the stack but as

[51:23] peeking is going to give us the top item

[51:25] on the stack if we pop another item we

[51:28] get one and now the stack is empty so if

[51:32] we try to pop another item we get none

[51:36] so basically all those key features of

[51:38] our staff are all working just fine so

[51:41] this is how we can use a wrapper class

[51:43] to implement a stack in Python with an

[51:47] underlying data structure of the Python

[51:49] list so the Python list is a very

[51:52] versatile data structure and here we've

[51:54] used it to create a stack now let's take

[51:58] a look at queues queue is a FIFO or

[52:01] first in first out data structure this

[52:05] is really intuitive because we see

[52:07] queues in every walk of life almost in

[52:10] everything you do on a daily basis you

[52:12] encounter queues queues have two key

[52:15] functions you in queue an item by adding

[52:18] it to the end of the line udq an item

[52:21] means removing it from the front of the

[52:23] line

[52:24] so some use cases for queues just about

[52:27] everything you wait in line for so bank

[52:29] tellers placing an order at McDonald's

[52:32] or your favorite restaurant

[52:34] DMV customer service supermarket

[52:37] checkout pretty much anything that has a

[52:40] line is what a queue is and it's

[52:43] important to be able to model that in a

[52:45] computer program so the queue data

[52:48] structure allows us to do that now let's

[52:52] take a look at how we can implement a

[52:53] queue in Python it's actually pretty

[52:56] simple because python already provides

[52:58] us a built-in library called the deck or

[53:01] de quue that's a double-ended queue that

[53:06] allows you to add and remove items from

[53:08] both ends of the queue for our simple

[53:10] queue we don't really need that function

[53:12] now

[53:12] we just want to be able to add items to

[53:14] one end of the queue and pop them off of

[53:16] the other so we can use the append

[53:19] function to add items or push items on

[53:22] to our queue and we can use pop left to

[53:25] remove items or pop items off of the

[53:28] cube you can see the full documentation

[53:31] in Python here if you want to learn more

[53:33] about how double into queues work so for

[53:37] basically just using double ended queue

[53:40] in python as a single ended queue we can

[53:42] use from collections import deck that's

[53:46] going to import our double ended queue

[53:48] library and then we'll create a new

[53:50] queue my queue and that's going to be a

[53:53] double ended queue object and then we

[53:57] can append items or push items using the

[54:00] append function so we can push a 5 and

[54:03] we can push a tin on to the queue and

[54:05] then when we print out the queue we see

[54:07] that we have a double ended queue with a

[54:08] 5 and a 10 on it and then if we want to

[54:12] pop items off of the queue we use pop

[54:15] left and here we get to 5 that pops an

[54:17] item off the tail end of the queue or

[54:20] the left end of the queue so it's pretty

[54:23] easy to implement a queue in Python this

[54:26] is obviously a common enough data

[54:29] structure that Python built in a library

[54:32] for it now as a fun exercise for you you

[54:36] may try writing a wrapper class for the

[54:39] double-ended queue to make a

[54:40] single-ended queue using push and pop as

[54:43] we did similar for the stack in this

[54:47] lecture we're going to learn how to use

[54:48] max heaps now implementation wise the

[54:52] underlying data structure is going to be

[54:54] a list and it's the functions of a max

[54:58] heap are not a whole lot different from

[55:00] stack and queue so I think you're going

[55:02] to be able to pick this up fairly easily

[55:04] now when you look at this graphical

[55:07] representation of a max heap though it

[55:08] looks a lot like a tree and I know we

[55:10] haven't covered trees yet that's going

[55:11] to be covered in section 5 but bear with

[55:14] me I think you're going to figure this

[55:15] out pretty easily so the one condition

[55:19] of a max heap is that every node is less

[55:22] than or equal to

[55:23] it's parent that's the key so you'll see

[55:26] that 25 is the parent of 16 and 24 right

[55:30] 25 has a left child and a right child

[55:33] and it's greater than or equal to both

[55:36] of those and then 16 is greater than or

[55:39] equal to both of its left and right

[55:41] children and so on so every node in the

[55:44] tree has to be less than or equal to its

[55:47] parent and every parent node has to be

[55:49] greater than or equal to be the nodes

[55:51] below it so that is the core condition

[55:54] of a max-heap and the reason it's like

[55:57] this is so that we can instantly remove

[55:59] this max number anytime we want anytime

[56:03] we want to pop the top number off of the

[56:05] heap we know that it's the highest

[56:06] number in that heap so the highest

[56:09] number always rises to the top of the

[56:10] heap and it can be instantly removed and

[56:13] used so max heaps are fast if you're

[56:19] familiar with Big O notation you can

[56:22] insert or add an item to a max heap in

[56:24] Big O of log n time which is extremely

[56:27] fast and you can get an item you can get

[56:31] the max item off the top of the heap and

[56:33] Big O of one time which is pretty much

[56:35] instantaneous you can remove the max or

[56:38] pop in Big O of log in time so the

[56:41] response time for a max heap is

[56:43] extremely fast and that's why we use max

[56:46] heaps for some things if you need to pop

[56:48] this the maximum number off a heap you

[56:50] can get very quickly

[56:52] max heaps are easy to implement in

[56:55] Python using a list not as easy as the

[56:58] other two data structures we just

[57:00] covered but not too hard so I think

[57:03] you'll be able to follow this but I'll

[57:05] warn you the code is a little bit longer

[57:06] and hairier than the previous two

[57:08] examples that we just covered but I've

[57:10] already written all the code all you

[57:12] have to do is just follow along with the

[57:13] explanation so you can see that using a

[57:15] list we open index the correspond to

[57:18] list index it corresponds to each node

[57:20] starting with one at the top and then

[57:23] 2/3 across 4 5 6 7 across on the next

[57:26] tier and then on the next tier 8 9 10 so

[57:29] it's a pretty easy indexing system that

[57:33] corresponds to these nodes under the

[57:35] tree

[57:36] [Music]

[57:37] and then when you look at our our list

[57:39] how we put the items into the list well

[57:42] look 25 is an index 1 and then 16 and 24

[57:47] so look we know that 16 is not greater

[57:50] than 24 but it looks like wow it's lower

[57:53] than note 3 here or index 3 why is that

[57:58] well because our rule is that 16 has to

[58:01] be greater than everything below it on

[58:03] the tree which it is so our condition is

[58:06] met this is a max-heap

[58:07] 16 does not have to be greater than 24

[58:10] we didn't say greater than everything

[58:12] behind it on the list no no on the tree

[58:15] so that this is a valid max-heap okay

[58:20] and that is how it is implemented in the

[58:22] list using these list indices so we can

[58:26] instantly access any node in the tree or

[58:30] any node in the max heap now let's say

[58:34] we wanted to access the 5 we know that

[58:37] the index is 4 this is it index number 4

[58:40] for this this 5 node now we can also

[58:44] access 5s parent which is the 16 we

[58:48] simply divide the index by 2 so this 4

[58:52] divided by 2 gives us the index of 5s

[58:55] parent node which is 16 and if we want

[58:58] to access 5 children it's the same thing

[59:00] 5s left child is times 2 to get the

[59:05] index of 5 left child 8 and then times 2

[59:09] plus 1 gives us the index of 5s right

[59:12] child 8 9 so if we're taking take a

[59:16] given node at index 4 we can access his

[59:20] right and left child by x 2 and x 2 plus

[59:25] 1 and we can access force parent by just

[59:29] divided by 2 so it's pretty quick easy

[59:31] operations to access the parent and

[59:34] children node in this tree

[59:37] no max heap operations like I said these

[59:40] are exactly the same operations that we

[59:42] just covered for stacks and queues so we

[59:44] want to be able to insert or push an

[59:46] item onto the heap we want to be able to

[59:49] peek find out what is the

[59:51] item on the heap without popping it off

[59:53] and then we want to be able to remove an

[59:55] item from the heap and return it which

[59:58] is a pop operation so the same three

[1:00:00] operations for heaps as we had for the

[1:00:03] previous two data structures let's look

[1:00:06] at how those work so push we can add a

[1:00:10] value to the end of the array and then

[1:00:13] we float it up to its proper position so

[1:00:17] let's look at an example we want to push

[1:00:20] a 12 onto this heap what we're going to

[1:00:23] do is put it at the very last spot in

[1:00:25] the array which is here right and we

[1:00:27] have a spot for it so in other words

[1:00:30] it's gonna be 11 right child it's the

[1:00:32] last index in the array and then we need

[1:00:35] to float it up to its proper position

[1:00:37] well how do we do that we need to

[1:00:39] compare 12 to 11 if 12 is greater than

[1:00:41] these two we'll swap places yeah it is

[1:00:44] greater so we want the 12 and 11 to swap

[1:00:47] places now we need to compare 12 to its

[1:00:51] its new parent 16 is 12 greater than 16

[1:00:56] no it's not so there's no more swapping

[1:00:58] 12 is already floated up to its proper

[1:01:01] position in the heap so this is one of

[1:01:05] the key behind-the-scenes functions that

[1:01:07] we have to code which is called float up

[1:01:10] or bubble up when we add an item to the

[1:01:13] bottom of the tree we need to be able to

[1:01:15] bubble it up to its correct position in

[1:01:18] the heap by comparing it to its parent

[1:01:20] nodes and in swapping so we use that

[1:01:22] every time we do a push operation peek

[1:01:26] just returns the value at the top of the

[1:01:28] heap okay which is going to be heap of

[1:01:31] number one index number one and that's

[1:01:34] pretty straightforward we don't really

[1:01:35] need to pop it off or anything's we just

[1:01:37] get that item and return it and then pop

[1:01:40] first we're going to move this topmost

[1:01:42] item we want to pop off the max which we

[1:01:45] know is in index position one first

[1:01:47] we're going to swap it with the item in

[1:01:49] the last position then we're going to

[1:01:52] delete it from the heap and then we're

[1:01:54] going to bubble down the item here to

[1:01:56] its proper position so let's take a look

[1:01:59] at the example so 11 is in the last

[1:02:03] position

[1:02:04] 25 is the item we want to pop so we're

[1:02:07] going to swap those two 25 and 11 swap

[1:02:10] places now we can remove 25 from the

[1:02:13] heap without affecting the rest of the

[1:02:15] heap it's in the last place it doesn't

[1:02:17] affect anything else in the heap our

[1:02:20] next step is to bubble that 11 down to

[1:02:23] its correct position so we compare 11 to

[1:02:26] 24 11 is less than 24 so it needs to

[1:02:29] move down next we're going to compare 11

[1:02:32] to 19 and 11 is less than 19 so that's

[1:02:35] gonna swap places so we do some

[1:02:38] comparisons with the child nodes to move

[1:02:41] 11 down until there's either no further

[1:02:43] room to go down or it's not greater than

[1:02:46] any of its children nodes so that's the

[1:02:49] operation for pop and now we can just

[1:02:51] return to 25 that we pulled off that's

[1:02:54] it so those are the three key operations

[1:02:57] and that's basically how they work in a

[1:02:59] nutshell now let's take a look at the

[1:03:01] code again the underlying data structure

[1:03:03] we're using is a list so you're gonna

[1:03:06] see us using list indices throughout

[1:03:07] this program now the public functions we

[1:03:10] have here are push peek and pop for

[1:03:14] pretty familiar with those by this point

[1:03:16] but we also have supporting private

[1:03:18] functions that we need for this heap and

[1:03:20] we have a basically swap a float up in a

[1:03:23] bubble down and we use those about

[1:03:25] internal utility functions these are not

[1:03:27] part of the user interface and then the

[1:03:30] string function is so that we can print

[1:03:32] a heap so our constructor when we create

[1:03:38] a new heap we have the option of passing

[1:03:41] in a list of items that we want to add

[1:03:44] to the heap if we don't pass in a list

[1:03:46] of items and we'll get back an empty

[1:03:48] heap with just a 0 in it so we put a 0

[1:03:52] in the very first element because we

[1:03:54] don't use that we start our elements at

[1:03:56] index number 1 for the max heap if we

[1:04:00] pass in this list of items we're

[1:04:02] basically going to iterate through those

[1:04:03] add them one at a time to the end of the

[1:04:06] list and then float it up to its proper

[1:04:08] position that's the push operation so

[1:04:12] essentially we're pushing them all one

[1:04:13] at a time and when you look at the push

[1:04:15] method it does exactly the same thing

[1:04:17] it appends the data that you passed in

[1:04:19] to the end of the heap and then it

[1:04:22] floats it up to its proper position in

[1:04:23] the heap so that is the push operation

[1:04:25] which is almost identical to the

[1:04:27] constructor if you pass in items now the

[1:04:31] peak operation doesn't do much it only

[1:04:33] returns the top item on the heap that's

[1:04:36] all

[1:04:36] it doesn't take it off there's no pop

[1:04:38] operation going on it's just a peak now

[1:04:42] let's look at the pop operation there

[1:04:46] are a few different cases here depending

[1:04:48] on how many items we have in the list if

[1:04:51] the list has exactly two items one of

[1:04:54] those is the zero that we're not

[1:04:55] counting we're not using that as part of

[1:04:57] our or max heap so if there are exactly

[1:05:00] two items that means there's really just

[1:05:01] one item in our max heap we'll pop off

[1:05:04] that number one item with index number

[1:05:06] one and we'll return it we set past that

[1:05:09] into a variable Max and then here at the

[1:05:11] end here we return max if there are more

[1:05:14] than two items then we're going to swap

[1:05:16] the maximum item which is in position

[1:05:18] index 1 with the last item so we get the

[1:05:22] last item in the list we swap those two

[1:05:26] we pop off the last item and assign it

[1:05:29] to this variable Max and then we bubble

[1:05:32] down the first item that we moved into

[1:05:34] the top position so it's exactly what we

[1:05:37] just walked through in this slides and

[1:05:40] then at the end we return to max so

[1:05:43] that's how the pop operation works then

[1:05:47] in our utility functions here swap

[1:05:49] really just swaps two different items we

[1:05:51] pass in two indices we swap those two

[1:05:53] items in the in the list now the float

[1:05:58] up function is going to receive an index

[1:06:01] of the item that we want to float up

[1:06:03] probably the very bottom item in the

[1:06:05] list initially first we'll get the index

[1:06:08] of its parent if it's already in the top

[1:06:11] position then there's no floating up to

[1:06:14] do it's already risen to the top

[1:06:15] otherwise we're going to compare it to

[1:06:18] its parent and if it's greater than its

[1:06:21] parent then those two need to swap

[1:06:22] places

[1:06:23] so I'll swap the positions of the item

[1:06:26] at index passed in with its parent then

[1:06:29] we'll call the float up function

[1:06:31] forcibly on the parent so this will

[1:06:33] continue to float up function until the

[1:06:36] element reaches its proper position

[1:06:40] bubble down kind of does the opposite it

[1:06:43] takes an element that's at the top of

[1:06:45] the list and it bubbles it down to its

[1:06:47] proper position so you can pass in an

[1:06:49] index we get the left child and the

[1:06:54] right child by multiplying the index by

[1:06:57] 2 and times 2 plus 1 and then we'll set

[1:07:01] the largest equal to index we do a

[1:07:05] little comparison if the item were

[1:07:08] bubbling down is less than its left

[1:07:11] child then we're going to swap positions

[1:07:13] with the left one if the item we're

[1:07:15] bubbling down is less than the right

[1:07:17] child then we're going to swap positions

[1:07:19] with the right child so if there's any

[1:07:24] swapping to be done at the very end here

[1:07:26] we check do we need to swap if so we'll

[1:07:29] call this swap function on the item

[1:07:33] we're bubbling the target item with the

[1:07:35] larger of those two and then we'll

[1:07:39] recursively call the bubble down

[1:07:41] function again on the same item that we

[1:07:43] just bubbled until it reaches its proper

[1:07:45] position and our test code here we don't

[1:07:52] have a whole lot of test code we create

[1:07:55] a new max-heap with three items in it

[1:07:57] obviously the 95 is the highest one and

[1:08:00] 2221 is the second highest we push a 10

[1:08:03] on and then we can see that our list now

[1:08:05] has ignore the zero really has four

[1:08:08] items in it and when we pop one off we

[1:08:11] get it of course the 95 and when we peek

[1:08:13] at the next item none - 95 is gone we

[1:08:17] can see that the 21 is the next item in

[1:08:19] the max heap that is how a max-heap

[1:08:22] works and that's how you can implement

[1:08:24] it in Python and by simply changing a

[1:08:26] few greater than or less than signs you

[1:08:29] could change this to a min heap let's

[1:08:32] say you have a collection of items that

[1:08:34] you want to store and you want to be

[1:08:35] able to iterate through them so you

[1:08:37] wouldn't be able to find an item in the

[1:08:39] list you wouldn't be able to insert an

[1:08:40] item but you need very fast and

[1:08:42] searching speed especially at the front

[1:08:44] of the list you want

[1:08:44] to insert new items at the front you

[1:08:47] need to be able to remove items from the

[1:08:48] list you also may want to iterate

[1:08:50] forward and backward through the list or

[1:08:53] possibly even in a continuous circle

[1:08:55] through the list so one possible storage

[1:08:57] solution for these requirements is a

[1:08:59] linked list we're going to learn how to

[1:09:02] use linked lists and what they are and

[1:09:03] we're going to learn a few different

[1:09:04] types of linked lists a standard linked

[1:09:06] list a bi-directional or doubly linked

[1:09:08] list and also a circular linked list

[1:09:10] we'll learn how those work the major

[1:09:12] operations used for with linked lists

[1:09:14] and we're also going to go through of

[1:09:17] course how to code a linked list in

[1:09:19] Python so let's take a look at how

[1:09:22] linked lists work every linked list is

[1:09:25] going to be composed of what we'll call

[1:09:27] nodes you can call it whatever you want

[1:09:29] in this video we're just going to call

[1:09:31] each item in a linked list a node you

[1:09:34] could store whatever data you want in

[1:09:37] the linked list it could be a student

[1:09:38] node it could be an employee node

[1:09:41] whatever it doesn't matter but we're

[1:09:43] gonna call our node and that's kind of a

[1:09:45] common nomenclature for the items in the

[1:09:47] linked list just call them nodes and

[1:09:49] each node is connected to the next node

[1:09:51] so it has a pointer to the next node so

[1:09:54] those two things it has a piece of data

[1:09:56] which for us is just going to be an

[1:09:57] integer in this video and it has a

[1:09:59] pointer to the next node so those are

[1:10:02] the two key components of every node in

[1:10:04] the linked list now a linked list looks

[1:10:07] something like this each node has its

[1:10:09] own piece of data and it also has a

[1:10:11] pointer to the next node there can be

[1:10:13] any number of nodes it's basically

[1:10:14] unlimited only by the amount of memory

[1:10:16] you have in your system and the very

[1:10:18] last node here you'll see there's no

[1:10:20] next pointer so we're going to store

[1:10:22] like a nun there to indicate that

[1:10:24] there's no next node that's the last

[1:10:26] node in the list at the very front we

[1:10:30] call that the root node that's the first

[1:10:33] node in the list so we need a pointer to

[1:10:35] point to the starting point for the list

[1:10:38] and this is what we call the root so we

[1:10:41] have a pointer to the root and the

[1:10:44] operations that we need for each linked

[1:10:46] list we need to be able to find data we

[1:10:49] need to be able to add a piece of data

[1:10:51] we need to be able to remove a piece of

[1:10:53] data from the linked list and we need to

[1:10:56] be able to print the list

[1:10:57] so we're gonna see how each of these

[1:10:59] operations works and then we're gonna

[1:11:01] see how it held a code it in Python

[1:11:03] now the attributes for a linked list you

[1:11:06] have a pointer to that root node and

[1:11:08] then we're also going to track the size

[1:11:09] of the linked list so it in you given

[1:11:11] time you could find out how many nodes

[1:11:12] are in the list

[1:11:15] let's look at the add operation so

[1:11:18] here's our linked list we have a pointer

[1:11:20] to the root we want to add tend that's

[1:11:22] our command let's add 10 so we're first

[1:11:25] are gonna create a new node with that

[1:11:28] data 10 in it we don't have anything in

[1:11:30] the next pointer yet but what we're

[1:11:33] gonna do is we're going to point the

[1:11:35] next pointer to where the root is

[1:11:38] currently pointing so the root currently

[1:11:40] points at this five node we're going to

[1:11:43] put our next pointer for this new node

[1:11:45] pointing at the root node and then we

[1:11:49] change our route to the ten

[1:11:51] so we effectively inserted this new 10

[1:11:54] node at the very beginning of the linked

[1:11:57] list that's how we're going to do the

[1:11:59] insert operation next we want to try and

[1:12:02] remove a number so let's try and remove

[1:12:04] five obviously if we try to remove a

[1:12:06] number like 200 and it's not in this

[1:12:08] this linked list and we'll get back your

[1:12:10] a false or a nun or sorry dude or an

[1:12:12] error or something but if we have if we

[1:12:15] have a number that's in the list and we

[1:12:17] want to try and remove that so we're

[1:12:18] going to remove five first we need to

[1:12:19] find that five so we start at the root

[1:12:21] we check if this is the number no it's

[1:12:24] not oh is this the number yes it is geez

[1:12:26] so there's the node that we want to

[1:12:28] remove pretty easy to remove it we we

[1:12:32] take the previous node to this five we

[1:12:36] change the previous nodes next pointer

[1:12:39] to 5's next pointer in other words see

[1:12:42] five the next node is 17 so we just

[1:12:46] changed five s previous node which in

[1:12:48] this case is the root the ten we change

[1:12:51] that next pointer to where five next

[1:12:53] pointer goes and so now effectively the

[1:12:56] five node is just completely cut out of

[1:12:58] the linked list when we iterate through

[1:13:00] the linked list starting from the root

[1:13:01] we're going to follow this path and

[1:13:03] we're never even going to know that the

[1:13:04] five is there the five note still exists

[1:13:06] but we don't have access to it anymore

[1:13:09] it's effectively deleted from the

[1:13:11] list so that's the remove operation now

[1:13:14] let's take a look at how to code a

[1:13:16] linked list in Python we're going to

[1:13:18] start with a node class we're going to

[1:13:20] use the same node class for three

[1:13:23] different types of linked lists that we

[1:13:24] cover in this section so W linked lists

[1:13:27] and circular linked lists are going to

[1:13:28] use the same node class you'll see in

[1:13:31] the node class here that we have three

[1:13:33] attributes we have a piece of data we

[1:13:36] have a next node and we have a previous

[1:13:38] node now in our standard linked list we

[1:13:41] do not need the previous node so we're

[1:13:43] just not going to use that attribute in

[1:13:45] the standard linked list but it'll be

[1:13:47] there for us so that we can reuse the

[1:13:49] node class for the other two linked

[1:13:51] lists and then we also have this string

[1:13:54] representation that gives us back

[1:13:56] essentially the data in parentheses so

[1:14:00] that's what the string representation of

[1:14:02] a node is so in the linked list we have

[1:14:05] four methods we have an add find remove

[1:14:09] and a print list let's see how all those

[1:14:12] work first our constructor has two

[1:14:15] attributes we keep track of the root

[1:14:18] node and we also keep track of size so

[1:14:20] each time we're add or remove node we're

[1:14:23] going to increment or decrement the size

[1:14:25] accordingly to add a new node we pass in

[1:14:29] the data that we want to create that new

[1:14:31] node with we create a new node with

[1:14:34] passing in the data and the next note as

[1:14:37] the root node keep in mind we're

[1:14:39] inserting this node at the very

[1:14:41] beginning of the list so the current

[1:14:45] root node is going to be the second node

[1:14:48] so we pass that in as the next node for

[1:14:51] this new node and then we change the

[1:14:53] root node to the new node we increment

[1:14:57] our size by one and we're done with the

[1:14:59] add operation to find a piece of data we

[1:15:03] passing that piece of data we are going

[1:15:05] to iterate through the list one note at

[1:15:08] a time we're going to start at the root

[1:15:10] node which will call this node and as

[1:15:13] long as this node is not none as long as

[1:15:16] there it's a valid node we're going to

[1:15:18] continue to iterate through this list

[1:15:20] each time through this while loop this

[1:15:22] else statement is

[1:15:24] going to bump us forward to the next

[1:15:26] node if we haven't found what we're

[1:15:28] looking for yet

[1:15:29] so what we're looking for is this nodes

[1:15:33] data is equal to D and when we find that

[1:15:36] we return D if we get through all the

[1:15:39] way through the while loop we haven't

[1:15:41] found it will return none because that

[1:15:42] data is not in the list the remove

[1:15:46] function we pass in a piece of data we

[1:15:49] need pointers to this node and this

[1:15:51] notes previous node so we're going to

[1:15:54] start iterating through the lists to do

[1:15:56] defined operation at the root which will

[1:15:59] call this node and then we're going to

[1:16:01] keep track of the previous node because

[1:16:03] we need that to be able to remove the

[1:16:05] node when we find the one we want to

[1:16:07] remove each time through this while loop

[1:16:10] we have two pointers now to increment we

[1:16:13] have to increment the previous node to

[1:16:15] this node and we have to increment this

[1:16:18] node to this node next node so if we

[1:16:21] haven't found what we're looking for yet

[1:16:22] at the end of this while loop we'll bump

[1:16:24] forward both of those two pointers and

[1:16:26] that's how we iterate through the list

[1:16:30] now our check we check if this nodes

[1:16:33] data is equal to D that we're a past end

[1:16:36] that we're looking for if we find it we

[1:16:39] found that data there's two

[1:16:41] possibilities for removing that node one

[1:16:45] that node is in the root that's this

[1:16:48] else here in which case we just changed

[1:16:51] the pointer for the root node for our

[1:16:53] linked list to this nodes next node in

[1:16:57] other words the second node in the list

[1:16:59] we bypass the current root and we point

[1:17:02] our root pointer to the second node in

[1:17:05] the list that effectively deletes the

[1:17:07] first node in the list now if it's not

[1:17:11] in the root in other words it's in some

[1:17:12] other node in the list then we need to

[1:17:15] delete that by changing the previous

[1:17:17] nodes next node pointer to this nodes

[1:17:21] next node so that is the remove

[1:17:25] operation if we get all the way through

[1:17:27] and we haven't found it we return false

[1:17:29] if we do successfully remove it return

[1:17:32] true and the print operation we print

[1:17:37] the list

[1:17:38] we're going to iterate through the list

[1:17:40] one note at a time starting from the

[1:17:42] root this while loop is going to check

[1:17:45] when we reach the end of the list and

[1:17:47] then we're going to exit and just print

[1:17:48] a none and for each node we're going to

[1:17:51] print the string representation of that

[1:17:53] node followed by a little arrow so

[1:17:56] you'll see what that looks like when we

[1:17:57] run the test code in a second so here's

[1:18:02] our test code we test a variety of

[1:18:04] different operations yeah here's what a

[1:18:06] list printed looks like so our string

[1:18:09] representation of a node is just the

[1:18:11] value in parenthesis and then we put an

[1:18:13] arrow between it in our print function

[1:18:16] so we'll create a new list called my

[1:18:19] list we'll add a few items to it and

[1:18:22] then we'll print the list and you can

[1:18:23] see what we get here and then we can

[1:18:25] print the size of the list we can see

[1:18:27] the size is equal to 3 we remove one

[1:18:30] item the 8 then you can see the size is

[1:18:33] equal to 2 and we can also find the 5

[1:18:37] when we find the 5 it actually returns a

[1:18:39] 5 when we can print that out and we can

[1:18:42] also print out the root which is 12

[1:18:43] that's the last item we added so that's

[1:18:46] at the front of the list so that's how

[1:18:49] the linked list works so a circular

[1:18:52] linked list is almost identical to a

[1:18:55] standard linked list except that from

[1:18:56] the very end node instead of having no a

[1:19:00] none pointer to the next node it's going

[1:19:04] to have a loop back to the very

[1:19:05] beginning to the root node the add

[1:19:08] operation in circular linked lists works

[1:19:11] slightly differently because we have

[1:19:13] this loop back to the first node from

[1:19:16] the end node we'd rather not have to go

[1:19:18] back and update that every time we

[1:19:20] insert a new node so we don't insert the

[1:19:22] new node as the root node anymore now

[1:19:25] instead we're going to insert it as the

[1:19:26] second node we leave the root pointer

[1:19:29] and the last pointer the loop back to

[1:19:32] the root the same and instead we insert

[1:19:35] our new node as the roots next node and

[1:19:38] then the next node for our new node is

[1:19:41] going to be what was the previously the

[1:19:43] second node so that's the add operation

[1:19:45] for circular linked list so that's

[1:19:48] basically yeah that's the only

[1:19:50] difference with a circular linked list

[1:19:52] so what are the advantages of a circular

[1:19:55] link list well it's great for modeling

[1:19:57] continuously looping data or objects so

[1:20:00] something like a Monopoly board or

[1:20:02] in-game board or a racetrack or

[1:20:04] something that continuously loops and

[1:20:07] there are a lot of different looping

[1:20:08] objects in the real world so if you want

[1:20:10] to model some continuously looping set

[1:20:13] of objects in a computer program a

[1:20:15] circular linked list is one way to do

[1:20:17] that

[1:20:17] the circular link list is very similar

[1:20:19] to the linked list with a few

[1:20:21] modifications in the add method we have

[1:20:25] to check whether a the list is empty and

[1:20:27] if it is then we add the first node then

[1:20:30] we make its next node point to itself it

[1:20:34] sounds crazy but we need to loop back to

[1:20:36] something so we loop back to the first

[1:20:38] node the root node else if there's

[1:20:41] already at least one node in the list we

[1:20:44] can create a new node and insert it into

[1:20:47] the number two position right after the

[1:20:49] root and change the roots next node to

[1:20:53] point to this new node so that's how the

[1:20:55] add operation works we can see the code

[1:20:58] here it's only a few lines of code the

[1:21:02] fine method works exactly the same as in

[1:21:04] the regular linked list except that in

[1:21:07] this Elif statement we have to do a

[1:21:09] check if we've circled all the way back

[1:21:11] to the root node again because if we

[1:21:13] have we have to stop our find and return

[1:21:15] false we didn't find it we search the

[1:21:17] entire list we didn't find the value

[1:21:19] we're looking for we turn false for the

[1:21:26] remove method let's scroll down here for

[1:21:31] the remove method we need to track both

[1:21:33] this node and the previous node so we're

[1:21:37] going to set pointers for both of those

[1:21:38] to start out so we'll start out at the

[1:21:40] root node and we'll set previous node to

[1:21:42] none and you can see towards the end of

[1:21:45] our while loop here we advance both of

[1:21:47] these pointers one node so they move

[1:21:50] both move forward to the next node now

[1:21:53] we test if we found the data that's this

[1:21:55] first if statement

[1:21:56] bingo found if we pass this test and if

[1:22:01] so there are two possibilities for the

[1:22:03] remove function

[1:22:04] number one if the previous node is not

[1:22:07] none tests whether the data was found in

[1:22:11] the root node and if not the remove is

[1:22:14] an easy bypass operation for changing

[1:22:17] the previous nodes next pointer which is

[1:22:19] what we do here and taste number two

[1:22:23] else if we need to delete the root we

[1:22:27] use this while loop to find the very

[1:22:29] last node in the list so that we can

[1:22:31] update its next node to point to the new

[1:22:35] root because the root has changed so we

[1:22:39] find that we find the new we find the

[1:22:41] last node we update the last nodes new

[1:22:44] next pointer which is the new root and

[1:22:47] then we update the root pointer itself

[1:22:51] lastly we decrement the size by one and

[1:22:54] we return true if we successfully remove

[1:22:56] the data and in our print list method we

[1:23:00] iterate through the list we print each

[1:23:01] node file Bob followed by an arrow you

[1:23:04] can see and our while loop has to check

[1:23:07] if you've made it back to the root so we

[1:23:09] know when to stop so this is the test we

[1:23:11] have here while this node next node is

[1:23:14] not the root we continue to iterate

[1:23:16] through the list now let's take a look

[1:23:21] at the circular linked list test code

[1:23:23] here we create a certain new circular

[1:23:25] linked list we'll just call it CLL we're

[1:23:28] going to add a bunch of items to it

[1:23:29] using a for loop adding one item at a

[1:23:32] time and then we can print the size of

[1:23:34] the list we can see down here the result

[1:23:36] the size is five we try to find an

[1:23:38] eighth if the value is actually in there

[1:23:41] it will return eight if we try to find

[1:23:44] an item that's not a no list is going to

[1:23:46] return false

[1:23:47] so we can see when we try to find the 12

[1:23:49] we get back a false and instead of using

[1:23:53] our print list function here we're going

[1:23:55] to iterate through continuously so that

[1:23:57] you can see when we pass by we're gonna

[1:23:59] print eight items even though they're

[1:24:01] only five in the list so we're gonna see

[1:24:04] if it actually does circle back to the

[1:24:05] next node we're just going to

[1:24:06] continuously get the next node up until

[1:24:08] we reach eight of them so we can see

[1:24:10] five nine eight three seven and then it

[1:24:12] starts from the beginning again five

[1:24:14] nine eight three it'll continue on we

[1:24:17] print up

[1:24:17] eight items so that shows you that it's

[1:24:20] a continuous loop and we can continue to

[1:24:22] loop through that if we want to write a

[1:24:25] little more test code we can print the

[1:24:27] list and here's the current contents of

[1:24:28] the list and then we are removing eight

[1:24:31] and when we print out remove fifteen

[1:24:33] result we see that it's false because

[1:24:36] there's no 15 in the list we can see

[1:24:37] that and we print the size of the list

[1:24:40] now we have four items because we

[1:24:42] removed one we try to remove the five

[1:24:44] node that completes successfully and

[1:24:48] then we print the list again and we only

[1:24:49] have three items left so that wraps up

[1:24:52] this lecture on a circular length list

[1:24:55] now let's look at doubly linked lists

[1:24:58] these are also sometimes called

[1:24:59] bi-directional linked lists because they

[1:25:01] have arrows pointing both directions to

[1:25:04] the next node and to the previous node

[1:25:06] so a regular linked list looks like this

[1:25:09] a doubly linked list each node has three

[1:25:14] pieces of data it has a pointer to the

[1:25:16] previous node a pointer to the next node

[1:25:18] and the data itself is storing so ask

[1:25:22] those three things three components to

[1:25:25] the node of a doubly linked list so this

[1:25:29] is what a doubly linked list would look

[1:25:30] like a simple one with three nodes we

[1:25:33] have here four or twenty three and a

[1:25:34] seven so let's say we want to delete an

[1:25:38] item this is a little more complicated

[1:25:41] because we have two pointers to fix not

[1:25:43] just one so we found this item that we

[1:25:46] want to delete we're going to call that

[1:25:48] this node and then the previous node to

[1:25:50] this node is the four and the next note

[1:25:53] is the seven so how do we delete it well

[1:25:56] we look at this pointer from the

[1:25:58] previous node that's pointing to this

[1:26:00] node and we look at the pointer from the

[1:26:02] next node that's pointing to its

[1:26:03] previous node right these ones that are

[1:26:06] pointing to this node they have to be

[1:26:09] fixed they basically just have to bypass

[1:26:11] it so what we do is we change fours next

[1:26:16] pointer instead of pointing to this it

[1:26:19] has to point to this nodes next node and

[1:26:22] then for sevens

[1:26:25] previous pointer instead of pointing to

[1:26:28] sevens previous node it has to point to

[1:26:30] this

[1:26:31] nodes previous node so we we basically

[1:26:36] do two adjustments here pre done next

[1:26:39] equals this dot next and next up pre

[1:26:43] evils this dot preview changes that we

[1:26:46] do to cut this node out of the list and

[1:26:49] you see once we get these red arrows in

[1:26:50] place once we fix these two pointers

[1:26:52] we've effectively cut no.23 out of our

[1:26:55] linked list we've deleted it so that's

[1:26:58] how the delete operation works in a

[1:27:00] doubly linked list some advantages of

[1:27:03] the doubly linked list over a standard

[1:27:05] linked list you can iterate through the

[1:27:07] list in either direction that's pretty

[1:27:09] obvious but when you have a really large

[1:27:12] linked list and you don't want to

[1:27:14] iterate through all of the items because

[1:27:16] you happen to know that your item is

[1:27:17] towards the end of the list you can

[1:27:20] actually save quite a lot of time by

[1:27:21] starting your iteration at the tail end

[1:27:23] of the list and working right back so

[1:27:25] you could save a pointer to the very end

[1:27:28] of the list as well and you can delete a

[1:27:31] node without iterating through the

[1:27:34] entire list that is if you have a

[1:27:35] pointer to that node right if you know

[1:27:38] where that node is that you want to

[1:27:39] delete and you don't have to iterate

[1:27:40] through the whole list to find it each

[1:27:43] node already stores its previous in next

[1:27:45] pointer so you can get the nodes on

[1:27:47] either side of this node that we want to

[1:27:48] delete without having to iterate through

[1:27:51] the entire list if you have a pointer to

[1:27:53] the node you want to delete doubly

[1:27:55] linked list uses an extra node attribute

[1:27:57] called priva as I showed you before when

[1:28:00] we looked at the node class and it also

[1:28:03] has an extra list attribute called last

[1:28:05] you can see here last so that we can

[1:28:09] always access the tail end of the list

[1:28:11] or the last item in the list now the add

[1:28:15] method has to check if the list is empty

[1:28:17] and if so then the root node is also the

[1:28:21] last node so otherwise it adds a new

[1:28:25] node to the beginning and it changes the

[1:28:27] roots previa fails two different

[1:28:31] conditions here for the add a new node

[1:28:34] the find method works exactly the same

[1:28:37] as the find method for the standard

[1:28:40] linked list so there's really no changes

[1:28:41] on that the remove function

[1:28:44] it is a little different there are three

[1:28:46] possible cases in the remove function so

[1:28:49] let's review each one of those case

[1:28:51] number one we're trying to delete a

[1:28:52] middle node that's this if statement

[1:28:54] here so the node is not in either the

[1:28:58] root or in the last node that's the

[1:29:02] standard case that we showed in two

[1:29:03] slides so for this we just do a simple

[1:29:05] bypass we bypass the target node and by

[1:29:09] changing the previous nodes next pointer

[1:29:10] and the next nodes previous pointer

[1:29:13] which is exactly what we're doing here

[1:29:15] then we've basically bypassed the target

[1:29:18] node that we're trying to delete now the

[1:29:20] second case is that we're trying to

[1:29:22] delete the last node this is just like

[1:29:25] case one except that the previous nodes

[1:29:28] next pointer will be changed to none

[1:29:30] because the second-to-last node is now

[1:29:33] the last node so that's the only

[1:29:35] difference here so we we're changing the

[1:29:38] basically the second-to-last nodes next

[1:29:40] pointer to none and the third case is

[1:29:44] we're trying to delete the root node and

[1:29:47] this is again similar to case one except

[1:29:50] that we change the root pointer to point

[1:29:53] to the second node in other words we

[1:29:56] change root to point two roots next node

[1:29:58] and that's it those are the three cases

[1:30:01] for remove the rest of the remove

[1:30:04] function is really straightforward the

[1:30:07] print list method is pretty much the

[1:30:08] same there's not no changes there so

[1:30:10] let's look at the test code for the

[1:30:12] doubly linked list here will create a

[1:30:16] doubly linked list dll we'll call it we

[1:30:19] add a bunch of items using a for loop to

[1:30:21] add each one of those items in we can

[1:30:22] see we print the size is 5 and we can

[1:30:25] print the entire list if we want using

[1:30:27] our print list method and then we can

[1:30:30] remove an 8 will print out the size

[1:30:32] again we can see the sizes for so these

[1:30:34] things all work and then if we try to

[1:30:36] remove items that are not in the list

[1:30:38] you'll l dot remove 15 that doesn't work

[1:30:41] if we try to find an item that's not in

[1:30:43] the list we also get false back and if

[1:30:46] we add some numbers 21 and 22 and then

[1:30:50] we remove a 5 and then we print the list

[1:30:52] again we can see that 21 and 22 were

[1:30:54] added to the front of the list and the 5

[1:30:57] was removed

[1:30:58] was a tail node the last node in the

[1:31:00] list and we successfully removed that

[1:31:01] and then just for fun we see that we can

[1:31:04] print out the last nodes previous node

[1:31:06] which should be the node right before

[1:31:08] the three of the nine which is this

[1:31:10] three which is exactly what it does so

[1:31:12] we can access nodes from the tail end of

[1:31:15] the list also that wraps up this section

[1:31:18] on linked lists so in this section we

[1:31:22] covered a standard linked list a

[1:31:23] circular linked list and a doubly linked

[1:31:26] list or a bi-directional linked list we

[1:31:29] showed you how those work and then we

[1:31:32] implemented them in code and again I

[1:31:34] encourage you to download this code and

[1:31:36] run it and try it out make some edits to

[1:31:39] it change it use your own tests on it

[1:31:42] and see how it works by using a code

[1:31:45] you're gonna better understand how the

[1:31:46] code works how linked lists work and how

[1:31:49] to eventually write your a linked list

[1:31:50] code hopefully in this lecture we're

[1:31:53] going to talk about trees after section

[1:31:56] one where we covered pythons built-in

[1:31:58] data structures trees is definitely the

[1:32:00] next most important section of this

[1:32:02] course trees are critically important

[1:32:04] data structure in all programming

[1:32:06] languages and let me explain why to make

[1:32:07] a point I'm thinking of a number between

[1:32:10] 1 and 8 million can you guess my number

[1:32:12] well you guessed 4 million I just say

[1:32:14] wrong and you're thinking uh-oh aren't

[1:32:18] you gonna tell me higher or lower no you

[1:32:20] have to guess until you get my number

[1:32:22] well you might have to guess every

[1:32:24] number between 1 and 8 million to figure

[1:32:26] out which number it is so if you're

[1:32:28] using a list an unsorted list as your

[1:32:31] data structure that's what it's like you

[1:32:33] would have to iterate through the entire

[1:32:36] list to find the number so you may have

[1:32:38] to do up to 8 million comparisons to

[1:32:41] locate that number that I'm thinking of

[1:32:43] that is the issue with lists when you

[1:32:45] have a lot of data it's really slow to

[1:32:48] find data now with a tree it's a little

[1:32:51] different you guess 4 million and I say

[1:32:54] lower you guessed 2 million I say higher

[1:32:58] you've got 3 million lower ok Wow with 3

[1:33:01] guesses

[1:33:02] you've shaved off 7 million

[1:33:03] possibilities and now you've narrowed

[1:33:05] down the possibilities to between 2 and

[1:33:07] 3 million

[1:33:08] you're only 1 million possibilities left

[1:33:10] with just 3 guesses so with as few as 30

[1:33:13] guesses you would be able to find any

[1:33:16] piece of data in a tree with up to 10

[1:33:18] million nodes so that is how fast binary

[1:33:22] search trees are a balanced binary

[1:33:24] search tree will let you locate data in

[1:33:26] a very large tree with as little as 30

[1:33:30] comparisons so now let's take a look at

[1:33:32] some of the major operations of trees

[1:33:34] and how they work so first let's learn

[1:33:36] some basic terminology about trees this

[1:33:39] is a node each part of a tree is called

[1:33:42] a node and each connection between nodes

[1:33:46] is called an edge and at the very top of

[1:33:51] the tree we have a root node you can see

[1:33:54] that trees are actually upside down

[1:33:56] compared to real-world trees this is

[1:33:58] more like a root system of a tree or a

[1:33:59] flipped upside down tree or like a

[1:34:02] management hierarchy in a company or

[1:34:04] something right we only have one

[1:34:05] president and then you have multiple

[1:34:07] vice presidents and so on down trees are

[1:34:09] great for modeling organizations but

[1:34:12] that's not the real benefit of tree the

[1:34:14] real benefit is the speed now we have

[1:34:16] parent nodes and child nodes in a binary

[1:34:19] tree a parent can have up to two

[1:34:22] children one or two children nodes that

[1:34:25] have the same parent are called sibling

[1:34:27] nodes and bottom nodes at the very

[1:34:30] bottom of the tree that don't have any

[1:34:33] children are called leaf nodes not all

[1:34:36] trees are binary trees but in a binary

[1:34:38] tree each node can have up to two child

[1:34:40] nodes a left and right child node now

[1:34:44] some trees may have 5/10 of up to a

[1:34:47] thousand child nodes for each node we

[1:34:50] can see the off of five here we have a

[1:34:52] sub tree a sub tree connects to a root

[1:34:55] node here and a sub tree is basically

[1:35:00] any part of a tree that in itself is a

[1:35:03] tree so it can be a sub tree of five

[1:35:07] compared to node 4 3 & 5 rows ancestors

[1:35:10] which is a parent node and every node

[1:35:12] above it's not the parent in the tree

[1:35:16] descendants are every node below that

[1:35:18] node in a tree so node 5's descendant

[1:35:21] includes everything in its left subtree

[1:35:23] and everything

[1:35:24] right sub-tree in a binary search tree

[1:35:27] each node is greater than every node in

[1:35:31] its left subtree so here we can see that

[1:35:33] 15 is greater than every single node in

[1:35:36] its left subtree and 8 is greater than

[1:35:40] every node in its left subtree and the 5

[1:35:44] is greater than every node in this sub

[1:35:46] tree the 24 is look greater than every

[1:35:50] node in its left subtree so this is a

[1:35:52] standard requirement for binary search

[1:35:54] trees each node is greater than every

[1:35:57] node in its left subtree and it's also

[1:36:00] less than each node in its right subtree

[1:36:03] here we can see that all the nodes in

[1:36:05] 15's right subtree are greater than 15

[1:36:08] and all the nodes in 24 right subtree

[1:36:12] are greater than 20 for all the nodes in

[1:36:15] 8 right subtree are greater than 8 so

[1:36:18] those are 2 standard requirements for a

[1:36:20] binary search tree some of the standard

[1:36:22] operations that L binary search trees

[1:36:25] are going to use insert I'm going to be

[1:36:27] able to add new data to the tree fine we

[1:36:30] want to be able to locate data in the

[1:36:31] tree delete is to remove a node get size

[1:36:35] counts all the nodes in a tree to tell

[1:36:38] us how many pieces of data we have in a

[1:36:39] tree in traversals which enable us to

[1:36:42] walk through the tree node by node and

[1:36:45] I'll show you how some of those work

[1:36:47] first let's look at the insert method

[1:36:49] we're going to always start at the root

[1:36:52] when we're doing an insert so at the top

[1:36:54] in this tree it's 215 we're always going

[1:36:58] to insert a new node as a leaf in other

[1:37:01] words at the very bottom of the tree but

[1:37:03] we start at the top to locate the right

[1:37:06] position the correct position in the

[1:37:08] tree to insert that new leaf so let's

[1:37:11] say we want to insert 12 in this tree

[1:37:13] we're going to start out with

[1:37:15] comparisons starting at the root is 12

[1:37:17] less than 15 yes it is so we're going to

[1:37:20] descend down 15 left subtree next we're

[1:37:24] going to compare 12 to 8 is 12 less than

[1:37:27] 8 no it's not so we're going to descend

[1:37:29] down 8 right subtree towards the 11

[1:37:33] there's 12 less than 11 no it's not

[1:37:37] and then we compare 12 to 13 and we say

[1:37:40] well yeah 12 is less than 13 so we're

[1:37:43] again we're going to add the 12 as a

[1:37:46] leaf node so we can add it as 13s left

[1:37:49] child that's how the insert function

[1:37:55] works now let's look at the fine method

[1:37:57] again with fine we'll always start at

[1:37:59] the root here it's 15 and we're going to

[1:38:03] do comparisons so if we want to find 19

[1:38:06] in this tree we're going to start by

[1:38:07] comparing 19 to 15 is 19 less than 15 no

[1:38:11] it's greater so we descend down the

[1:38:13] right subtree and then we compare 19 to

[1:38:17] 24 19 is less than 24 so we go down 24

[1:38:21] left subtree you can see how with each

[1:38:24] comparison and decision we descend down

[1:38:27] one subtree that cuts in half the number

[1:38:29] of remaining possibilities to locate an

[1:38:32] item so now we've already in two

[1:38:35] comparisons found the 19 in this tree so

[1:38:38] when we find a piece of data with define

[1:38:40] function we're always going to return

[1:38:42] that piece of data and if we didn't find

[1:38:44] it we want to return false to let the

[1:38:47] user know that data is not existing in a

[1:38:49] tree so with delete there are three

[1:38:52] different possibilities one is that the

[1:38:55] nobody.one delete is a leaf node another

[1:38:59] possibility is that it has one child

[1:39:00] node then there's another possibility

[1:39:02] that has two child nodes so each one of

[1:39:05] these we have to handle differently

[1:39:07] delete is a fairly complicated operation

[1:39:10] so let's first look at the possibility

[1:39:12] that the number we want to delete is a

[1:39:14] leaf node so look at these are all these

[1:39:17] gray nodes are all leaf nodes so in a

[1:39:21] case of a leaf node it's easy for us to

[1:39:23] just delete the leaf node without

[1:39:25] affecting anything else in the tree

[1:39:27] these are bottom most nodes so it

[1:39:30] doesn't affect the organization of

[1:39:31] anything else in the tree we can just

[1:39:33] delete that node if it's in the leaf

[1:39:35] that's the easiest case right there now

[1:39:39] if we have one child

[1:39:41] these are cases where we have one child

[1:39:44] note 11 13 and 28 if we want to delete

[1:39:48] one of those nodes we have to promote

[1:39:51] that child node to the targets notes

[1:39:54] position so for instance if we wanted to

[1:39:57] delete the 28 we would promote 25 to 28