[0:13] hi I'm Joe James I have master's degree
[0:16] in computer science and I'm a software
[0:17] engineer in Silicon Valley and in this
[0:20] course we're gonna learn about data
[0:21] structures in Python you might be
[0:24] wondering well why should I care about
[0:25] data structures in Python let's imagine
[0:28] for a second that your carpenter you
[0:30] wouldn't try to pound in a nail with the
[0:33] screwdriver that just doesn't make sense
[0:35] carpenters no you can't do that you also
[0:37] wouldn't try to drive into screw with
[0:40] the pair of pliers so carpenters know
[0:43] that for every task there's a best tool
[0:46] for the job
[0:47] and that's why carpenters carry around a
[0:49] tool belt full of tools and those tools
[0:51] are specialized for different tasks and
[0:53] that's exactly what you're going to do
[0:56] when you master data structures in
[0:57] Python data structures are your tool
[1:01] belt for each task you face as a
[1:03] programmer you're going to know exactly
[1:04] which data structure to use and how to
[1:06] use it you're going to save time write
[1:09] better code and do it more efficiently
[1:11] so in this course we're gonna learn
[1:13] about pythons built-in data structures
[1:15] strings lists tuples sets and
[1:18] dictionaries then we're going to
[1:21] continue to learn about queues stacks
[1:23] and heaps we're also going to learn
[1:24] about linked lists then we're going to
[1:27] cover binary search trees and graphs
[1:29] you're gonna learn how to use these data
[1:31] structures how to implement them in
[1:33] Python and you're going to learn the
[1:35] strengths and weaknesses of each of
[1:36] these data structures so let's look at
[1:39] some of the code first we'll look at
[1:41] sequence types string list and tupple so
[1:45] I put a link here to the documentation
[1:47] this is the official Python
[1:48] documentation encourage you to check
[1:50] that out if you have any questions or
[1:52] you want more detail on you needing
[1:53] these items just look at the
[1:54] documentation link here so first is
[1:57] indexing we can access any item in a
[2:01] sequence by using its index we put that
[2:04] index inside square brackets an indexing
[2:08] starts with zero the first element is
[2:11] always zero
[2:13] so the fourth element is going to be
[2:15] index three so here we have a string
[2:18] frog as four letters in it if we want
[2:21] the fourth element which is G we print
[2:24] out X of 3 that gives us the G as you
[2:27] can see in the output here if we have a
[2:30] list of pig cow and horse these are
[2:31] strings we can print out X of 1 and
[2:34] that's going to give us cow and again
[2:37] it's just square brackets and a tuple
[2:39] with four names in it and if we want the
[2:41] very first name we print out X of zero
[2:44] with the zero in square brackets and
[2:46] that gives us Kevon so that's indexing
[2:50] now let's look at slicing we can slice
[2:53] out sub strings sub lists or sub temples
[2:55] using indexes so the way indexing works
[2:59] is you put inside the square brackets
[3:01] separated by colons three possible
[3:04] parameters so we can put a start and end
[3:07] plus one and a step and I'll show you
[3:09] what each of these means so let's just
[3:12] use a string for this example computer
[3:14] the word computer again the sea is index
[3:17] 0 so here we're going to print out X of
[3:21] 1 to 4 so since we didn't put a third
[3:25] parameter that means the step is assumed
[3:27] to be 1 that's the default step so when
[3:32] we put 1 that means the O and that is
[3:35] inclusive the from is or the start is
[3:38] always inclusive the end is non
[3:40] inclusive so if we look at item number 4
[3:43] that's the U that's the fifth item it's
[3:45] not inclusive so it's really just going
[3:47] to get OMP for us and when we look at
[3:49] the result it prints out OMP now here's
[3:53] an example using a step so we print out
[3:57] X of 1 to 6 again we're going to start
[4:00] at the O because the 1 is inclusive and
[4:03] we're going to go up to 6 which is the e
[4:05] but it's non inclusive and we're going
[4:10] to do it in a step of 2 so in other
[4:13] words we're going to get to O the P and
[4:15] the T and that's what we print out opt
[4:18] so it takes every other item when we
[4:20] have a step of 2
[4:24] next we're going to not put a end
[4:27] plus-one we're just gonna leave an open
[4:29] colon there and what happens is when we
[4:31] put the open colon 3 : nothing basically
[4:36] the default is end of string so
[4:38] everything from the third item on so
[4:41] here the third item is P because we
[4:44] start counting at zero the third item is
[4:46] P and we get everything from P onward P
[4:49] UT ER so if you don't know how long a
[4:52] string is or you just want to get all of
[4:54] the remaining elements skip the first
[4:56] three three items or something you use
[4:59] an open : next we're not going to
[5:02] declare a start so we can skip the start
[5:05] by just putting : five so in other words
[5:09] our default is we're going to start from
[5:11] the beginning of the string we're going
[5:12] to get up to the sixth item because the
[5:16] v is not inclusive so c om p u and you
[5:22] can see our result here are Co MP u so
[5:26] you can see if you don't declare a start
[5:28] the start defaults to the beginning and
[5:30] if you don't declare an end the end
[5:33] defaults to the end and if you don't
[5:36] declare a step the step defaults to one
[5:38] so that's basically what's happening
[5:39] here let's look at a negative index so
[5:44] if we print out just a negative index
[5:45] negative one that counts from the right
[5:48] side of the string so here we want the
[5:51] very last item in the string we put
[5:53] negative 1 we get the are the last
[5:55] element and then here we get the last
[5:59] three items so we put a negative three
[6:02] as the from and to the end of the string
[6:06] so that gives us ter that gives us the
[6:08] last 3 elements and then if we want to
[6:11] get everything except the last two
[6:13] elements of the string we leave this
[6:15] start blank so we get everything from
[6:17] the beginning up until the last two
[6:20] items so that is how slicing works and
[6:25] it works exactly the same as we just
[6:27] covered for this string example works
[6:29] exactly the same on lists and tuples
[6:32] now let's look at adding and
[6:34] concatenating so we can combine two
[6:37] sequences of the same type using the
[6:40] plus sign let's look at a string example
[6:43] first we want to combine horse and shoe
[6:45] and we just print X so we see the result
[6:49] is horseshoe if we have two separate
[6:52] lists and we want to merge those two
[6:54] lists together we can use a plus sign
[6:56] and when we print that we get a single
[6:58] list with three elements in it and in
[7:02] the case of tuples if we have two
[7:04] separate tuples and we print the result
[7:08] we get a single tuple with four elements
[7:10] in it now it's important to note here
[7:12] for the second one to be considered a
[7:14] tupple we have to include a comma here
[7:16] if we don't have that comma it's just a
[7:18] string in parentheses if we include this
[7:21] comma that tells python that this is
[7:24] actually a tuple we can use the
[7:28] multiplying function to multiply a
[7:30] sequence using the asterisk in a string
[7:33] example if we want to print bug three
[7:35] times we just do bug times three and
[7:38] then print and you can see the result
[7:40] here is bug bug bug and the same with a
[7:42] list we have a list eight comma five and
[7:45] we want to multiply that by three what
[7:47] we get is eight five eight five eight
[7:49] five so we're not actually multiplying
[7:51] the elements by three we're multiplying
[7:53] the list by three and then the same with
[7:56] tuple we can multiply at up all by three
[7:59] and then we get basically a triplicate
[8:01] of that tupple now let's look at testing
[8:06] membership we can test whether an item
[8:08] is in or not in a sequence these are
[8:12] really easy
[8:12] it's almost English key words in Python
[8:15] they made it so simple so with a string
[8:18] let's say we have a string called bug
[8:20] and we want to check if the letter U is
[8:22] in our string we just say u in X and
[8:26] that's going to give us a boolean result
[8:28] true or false in this case u is in X so
[8:32] it returns true and now we have a list
[8:35] pig cow and horse if we print cow not in
[8:41] Y it's going to print false because cow
[8:43] is in Y
[8:45] and for a couple example we have a
[8:47] couple here with four names and if we
[8:49] print one of those names in Z we get
[8:51] true because it is in Z so it's really
[8:54] easy to check membership using in or not
[8:56] in if we want to iterate through the
[8:59] items in a sequence we can say for item
[9:03] in X an item can be any variable name
[9:06] you want it can be for number in X or
[9:08] whatever you like here I just use the
[9:10] variable name item print item if you
[9:14] want both the index and the item here we
[9:18] have a list with 7 8 and 3 in it we say
[9:22] index comma item in enumerate X the
[9:26] numerator is going to return both an
[9:29] index and an item so actually again
[9:32] these variable names are arbitrary the
[9:34] first one is going to be the index the
[9:36] second one is going to be the item
[9:37] itself so you can name them whatever
[9:39] variable name you like but you can get
[9:42] both the index and the item using the
[9:45] enumerate function and then we have
[9:47] access to both the index in the item as
[9:49] you can see the results if you want to
[9:54] get the count or the number of items in
[9:57] a sequence you can just use the Len
[9: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
[60:00] operations for heaps as we had for the
[60:03] previous two data structures let's look
[60:06] at how those work so push we can add a
[60:10] value to the end of the array and then
[60:13] we float it up to its proper position so
[60:17] let's look at an example we want to push
[60:20] a 12 onto this heap what we're going to
[60:23] do is put it at the very last spot in
[60:25] the array which is here right and we
[60:27] have a spot for it so in other words
[60:30] it's gonna be 11 right child it's the
[60:32] last index in the array and then we need
[60:35] to float it up to its proper position
[60:37] well how do we do that we need to
[60:39] compare 12 to 11 if 12 is greater than
[60:41] these two we'll swap places yeah it is
[60:44] greater so we want the 12 and 11 to swap
[60:47] places now we need to compare 12 to its
[60:51] its new parent 16 is 12 greater than 16
[60:56] no it's not so there's no more swapping
[60:58] 12 is already floated up to its proper
[61:01] position in the heap so this is one of
[61:05] the key behind-the-scenes functions that
[61:07] we have to code which is called float up
[61:10] or bubble up when we add an item to the
[61:13] bottom of the tree we need to be able to
[61:15] bubble it up to its correct position in
[61:18] the heap by comparing it to its parent
[61:20] nodes and in swapping so we use that
[61:22] every time we do a push operation peek
[61:26] just returns the value at the top of the
[61:28] heap okay which is going to be heap of
[61:31] number one index number one and that's
[61:34] pretty straightforward we don't really
[61:35] need to pop it off or anything's we just
[61:37] get that item and return it and then pop
[61:40] first we're going to move this topmost
[61:42] item we want to pop off the max which we
[61:45] know is in index position one first
[61:47] we're going to swap it with the item in
[61:49] the last position then we're going to
[61:52] delete it from the heap and then we're
[61:54] going to bubble down the item here to
[61:56] its proper position so let's take a look
[61:59] at the example so 11 is in the last
[62:03] position
[62:04] 25 is the item we want to pop so we're
[62:07] going to swap those two 25 and 11 swap
[62:10] places now we can remove 25 from the
[62:13] heap without affecting the rest of the
[62:15] heap it's in the last place it doesn't
[62:17] affect anything else in the heap our
[62:20] next step is to bubble that 11 down to
[62:23] its correct position so we compare 11 to
[62:26] 24 11 is less than 24 so it needs to
[62:29] move down next we're going to compare 11
[62:32] to 19 and 11 is less than 19 so that's
[62:35] gonna swap places so we do some
[62:38] comparisons with the child nodes to move
[62:41] 11 down until there's either no further
[62:43] room to go down or it's not greater than
[62:46] any of its children nodes so that's the
[62:49] operation for pop and now we can just
[62:51] return to 25 that we pulled off that's
[62:54] it so those are the three key operations
[62:57] and that's basically how they work in a
[62:59] nutshell now let's take a look at the
[63:01] code again the underlying data structure
[63:03] we're using is a list so you're gonna
[63:06] see us using list indices throughout
[63:07] this program now the public functions we
[63:10] have here are push peek and pop for
[63:14] pretty familiar with those by this point
[63:16] but we also have supporting private
[63:18] functions that we need for this heap and
[63:20] we have a basically swap a float up in a
[63:23] bubble down and we use those about
[63:25] internal utility functions these are not
[63:27] part of the user interface and then the
[63:30] string function is so that we can print
[63:32] a heap so our constructor when we create
[63:38] a new heap we have the option of passing
[63:41] in a list of items that we want to add
[63:44] to the heap if we don't pass in a list
[63:46] of items and we'll get back an empty
[63:48] heap with just a 0 in it so we put a 0
[63:52] in the very first element because we
[63:54] don't use that we start our elements at
[63:56] index number 1 for the max heap if we
[64:00] pass in this list of items we're
[64:02] basically going to iterate through those
[64:03] add them one at a time to the end of the
[64:06] list and then float it up to its proper
[64:08] position that's the push operation so
[64:12] essentially we're pushing them all one
[64:13] at a time and when you look at the push
[64:15] method it does exactly the same thing
[64:17] it appends the data that you passed in
[64:19] to the end of the heap and then it
[64:22] floats it up to its proper position in
[64:23] the heap so that is the push operation
[64:25] which is almost identical to the
[64:27] constructor if you pass in items now the
[64:31] peak operation doesn't do much it only
[64:33] returns the top item on the heap that's
[64:36] all
[64:36] it doesn't take it off there's no pop
[64:38] operation going on it's just a peak now
[64:42] let's look at the pop operation there
[64:46] are a few different cases here depending
[64:48] on how many items we have in the list if
[64:51] the list has exactly two items one of
[64:54] those is the zero that we're not
[64:55] counting we're not using that as part of
[64:57] our or max heap so if there are exactly
[65:00] two items that means there's really just
[65:01] one item in our max heap we'll pop off
[65:04] that number one item with index number
[65:06] one and we'll return it we set past that
[65:09] into a variable Max and then here at the
[65:11] end here we return max if there are more
[65:14] than two items then we're going to swap
[65:16] the maximum item which is in position
[65:18] index 1 with the last item so we get the
[65:22] last item in the list we swap those two
[65:26] we pop off the last item and assign it
[65:29] to this variable Max and then we bubble
[65:32] down the first item that we moved into
[65:34] the top position so it's exactly what we
[65:37] just walked through in this slides and
[65:40] then at the end we return to max so
[65:43] that's how the pop operation works then
[65:47] in our utility functions here swap
[65:49] really just swaps two different items we
[65:51] pass in two indices we swap those two
[65:53] items in the in the list now the float
[65:58] up function is going to receive an index
[66:01] of the item that we want to float up
[66:03] probably the very bottom item in the
[66:05] list initially first we'll get the index
[66:08] of its parent if it's already in the top
[66:11] position then there's no floating up to
[66:14] do it's already risen to the top
[66:15] otherwise we're going to compare it to
[66:18] its parent and if it's greater than its
[66:21] parent then those two need to swap
[66:22] places
[66:23] so I'll swap the positions of the item
[66:26] at index passed in with its parent then
[66:29] we'll call the float up function
[66:31] forcibly on the parent so this will
[66:33] continue to float up function until the
[66:36] element reaches its proper position
[66:40] bubble down kind of does the opposite it
[66:43] takes an element that's at the top of
[66:45] the list and it bubbles it down to its
[66:47] proper position so you can pass in an
[66:49] index we get the left child and the
[66:54] right child by multiplying the index by
[66:57] 2 and times 2 plus 1 and then we'll set
[67:01] the largest equal to index we do a
[67:05] little comparison if the item were
[67:08] bubbling down is less than its left
[67:11] child then we're going to swap positions
[67:13] with the left one if the item we're
[67:15] bubbling down is less than the right
[67:17] child then we're going to swap positions
[67:19] with the right child so if there's any
[67:24] swapping to be done at the very end here
[67:26] we check do we need to swap if so we'll
[67:29] call this swap function on the item
[67:33] we're bubbling the target item with the
[67:35] larger of those two and then we'll
[67:39] recursively call the bubble down
[67:41] function again on the same item that we
[67:43] just bubbled until it reaches its proper
[67:45] position and our test code here we don't
[67:52] have a whole lot of test code we create
[67:55] a new max-heap with three items in it
[67:57] obviously the 95 is the highest one and
[68:00] 2221 is the second highest we push a 10
[68:03] on and then we can see that our list now
[68:05] has ignore the zero really has four
[68:08] items in it and when we pop one off we
[68:11] get it of course the 95 and when we peek
[68:13] at the next item none - 95 is gone we
[68:17] can see that the 21 is the next item in
[68:19] the max heap that is how a max-heap
[68:22] works and that's how you can implement
[68:24] it in Python and by simply changing a
[68:26] few greater than or less than signs you
[68:29] could change this to a min heap let's
[68:32] say you have a collection of items that
[68:34] you want to store and you want to be
[68:35] able to iterate through them so you
[68:37] wouldn't be able to find an item in the
[68:39] list you wouldn't be able to insert an
[68:40] item but you need very fast and
[68:42] searching speed especially at the front
[68:44] of the list you want
[68:44] to insert new items at the front you
[68:47] need to be able to remove items from the
[68:48] list you also may want to iterate
[68:50] forward and backward through the list or
[68:53] possibly even in a continuous circle
[68:55] through the list so one possible storage
[68:57] solution for these requirements is a
[68:59] linked list we're going to learn how to
[69:02] use linked lists and what they are and
[69:03] we're going to learn a few different
[69:04] types of linked lists a standard linked
[69:06] list a bi-directional or doubly linked
[69:08] list and also a circular linked list
[69:10] we'll learn how those work the major
[69:12] operations used for with linked lists
[69:14] and we're also going to go through of
[69:17] course how to code a linked list in
[69:19] Python so let's take a look at how
[69:22] linked lists work every linked list is
[69:25] going to be composed of what we'll call
[69:27] nodes you can call it whatever you want
[69:29] in this video we're just going to call
[69:31] each item in a linked list a node you
[69:34] could store whatever data you want in
[69:37] the linked list it could be a student
[69:38] node it could be an employee node
[69:41] whatever it doesn't matter but we're
[69:43] gonna call our node and that's kind of a
[69:45] common nomenclature for the items in the
[69:47] linked list just call them nodes and
[69:49] each node is connected to the next node
[69:51] so it has a pointer to the next node so
[69:54] those two things it has a piece of data
[69:56] which for us is just going to be an
[69:57] integer in this video and it has a
[69:59] pointer to the next node so those are
[70:02] the two key components of every node in
[70:04] the linked list now a linked list looks
[70:07] something like this each node has its
[70:09] own piece of data and it also has a
[70:11] pointer to the next node there can be
[70:13] any number of nodes it's basically
[70:14] unlimited only by the amount of memory
[70:16] you have in your system and the very
[70:18] last node here you'll see there's no
[70:20] next pointer so we're going to store
[70:22] like a nun there to indicate that
[70:24] there's no next node that's the last
[70:26] node in the list at the very front we
[70:30] call that the root node that's the first
[70:33] node in the list so we need a pointer to
[70:35] point to the starting point for the list
[70:38] and this is what we call the root so we
[70:41] have a pointer to the root and the
[70:44] operations that we need for each linked
[70:46] list we need to be able to find data we
[70:49] need to be able to add a piece of data
[70:51] we need to be able to remove a piece of
[70:53] data from the linked list and we need to
[70:56] be able to print the list
[70:57] so we're gonna see how each of these
[70:59] operations works and then we're gonna
[71:01] see how it held a code it in Python
[71:03] now the attributes for a linked list you
[71:06] have a pointer to that root node and
[71:08] then we're also going to track the size
[71:09] of the linked list so it in you given
[71:11] time you could find out how many nodes
[71:12] are in the list
[71:15] let's look at the add operation so
[71:18] here's our linked list we have a pointer
[71:20] to the root we want to add tend that's
[71:22] our command let's add 10 so we're first
[71:25] are gonna create a new node with that
[71:28] data 10 in it we don't have anything in
[71:30] the next pointer yet but what we're
[71:33] gonna do is we're going to point the
[71:35] next pointer to where the root is
[71:38] currently pointing so the root currently
[71:40] points at this five node we're going to
[71:43] put our next pointer for this new node
[71:45] pointing at the root node and then we
[71:49] change our route to the ten
[71:51] so we effectively inserted this new 10
[71:54] node at the very beginning of the linked
[71:57] list that's how we're going to do the
[71:59] insert operation next we want to try and
[72:02] remove a number so let's try and remove
[72:04] five obviously if we try to remove a
[72:06] number like 200 and it's not in this
[72:08] this linked list and we'll get back your
[72:10] a false or a nun or sorry dude or an
[72:12] error or something but if we have if we
[72:15] have a number that's in the list and we
[72:17] want to try and remove that so we're
[72:18] going to remove five first we need to
[72:19] find that five so we start at the root
[72:21] we check if this is the number no it's
[72:24] not oh is this the number yes it is geez
[72:26] so there's the node that we want to
[72:28] remove pretty easy to remove it we we
[72:32] take the previous node to this five we
[72:36] change the previous nodes next pointer
[72:39] to 5's next pointer in other words see
[72:42] five the next node is 17 so we just
[72:46] changed five s previous node which in
[72:48] this case is the root the ten we change
[72:51] that next pointer to where five next
[72:53] pointer goes and so now effectively the
[72:56] five node is just completely cut out of
[72:58] the linked list when we iterate through
[73:00] the linked list starting from the root
[73:01] we're going to follow this path and
[73:03] we're never even going to know that the
[73:04] five is there the five note still exists
[73:06] but we don't have access to it anymore
[73:09] it's effectively deleted from the
[73:11] list so that's the remove operation now
[73:14] let's take a look at how to code a
[73:16] linked list in Python we're going to
[73:18] start with a node class we're going to
[73:20] use the same node class for three
[73:23] different types of linked lists that we
[73:24] cover in this section so W linked lists
[73:27] and circular linked lists are going to
[73:28] use the same node class you'll see in
[73:31] the node class here that we have three
[73:33] attributes we have a piece of data we
[73:36] have a next node and we have a previous
[73:38] node now in our standard linked list we
[73:41] do not need the previous node so we're
[73:43] just not going to use that attribute in
[73:45] the standard linked list but it'll be
[73:47] there for us so that we can reuse the
[73:49] node class for the other two linked
[73:51] lists and then we also have this string
[73:54] representation that gives us back
[73:56] essentially the data in parentheses so
[74:00] that's what the string representation of
[74:02] a node is so in the linked list we have
[74:05] four methods we have an add find remove
[74:09] and a print list let's see how all those
[74:12] work first our constructor has two
[74:15] attributes we keep track of the root
[74:18] node and we also keep track of size so
[74:20] each time we're add or remove node we're
[74:23] going to increment or decrement the size
[74:25] accordingly to add a new node we pass in
[74:29] the data that we want to create that new
[74:31] node with we create a new node with
[74:34] passing in the data and the next note as
[74:37] the root node keep in mind we're
[74:39] inserting this node at the very
[74:41] beginning of the list so the current
[74:45] root node is going to be the second node
[74:48] so we pass that in as the next node for
[74:51] this new node and then we change the
[74:53] root node to the new node we increment
[74:57] our size by one and we're done with the
[74:59] add operation to find a piece of data we
[75:03] passing that piece of data we are going
[75:05] to iterate through the list one note at
[75:08] a time we're going to start at the root
[75:10] node which will call this node and as
[75:13] long as this node is not none as long as
[75:16] there it's a valid node we're going to
[75:18] continue to iterate through this list
[75:20] each time through this while loop this
[75:22] else statement is
[75:24] going to bump us forward to the next
[75:26] node if we haven't found what we're
[75:28] looking for yet
[75:29] so what we're looking for is this nodes
[75:33] data is equal to D and when we find that
[75:36] we return D if we get through all the
[75:39] way through the while loop we haven't
[75:41] found it will return none because that
[75:42] data is not in the list the remove
[75:46] function we pass in a piece of data we
[75:49] need pointers to this node and this
[75:51] notes previous node so we're going to
[75:54] start iterating through the lists to do
[75:56] defined operation at the root which will
[75:59] call this node and then we're going to
[76:01] keep track of the previous node because
[76:03] we need that to be able to remove the
[76:05] node when we find the one we want to
[76:07] remove each time through this while loop
[76:10] we have two pointers now to increment we
[76:13] have to increment the previous node to
[76:15] this node and we have to increment this
[76:18] node to this node next node so if we
[76:21] haven't found what we're looking for yet
[76:22] at the end of this while loop we'll bump
[76:24] forward both of those two pointers and
[76:26] that's how we iterate through the list
[76:30] now our check we check if this nodes
[76:33] data is equal to D that we're a past end
[76:36] that we're looking for if we find it we
[76:39] found that data there's two
[76:41] possibilities for removing that node one
[76:45] that node is in the root that's this
[76:48] else here in which case we just changed
[76:51] the pointer for the root node for our
[76:53] linked list to this nodes next node in
[76:57] other words the second node in the list
[76:59] we bypass the current root and we point
[77:02] our root pointer to the second node in
[77:05] the list that effectively deletes the
[77:07] first node in the list now if it's not
[77:11] in the root in other words it's in some
[77:12] other node in the list then we need to
[77:15] delete that by changing the previous
[77:17] nodes next node pointer to this nodes
[77:21] next node so that is the remove
[77:25] operation if we get all the way through
[77:27] and we haven't found it we return false
[77:29] if we do successfully remove it return
[77:32] true and the print operation we print
[77:37] the list
[77:38] we're going to iterate through the list
[77:40] one note at a time starting from the
[77:42] root this while loop is going to check
[77:45] when we reach the end of the list and
[77:47] then we're going to exit and just print
[77:48] a none and for each node we're going to
[77:51] print the string representation of that
[77:53] node followed by a little arrow so
[77:56] you'll see what that looks like when we
[77:57] run the test code in a second so here's
[78:02] our test code we test a variety of
[78:04] different operations yeah here's what a
[78:06] list printed looks like so our string
[78:09] representation of a node is just the
[78:11] value in parenthesis and then we put an
[78:13] arrow between it in our print function
[78:16] so we'll create a new list called my
[78:19] list we'll add a few items to it and
[78:22] then we'll print the list and you can
[78:23] see what we get here and then we can
[78:25] print the size of the list we can see
[78:27] the size is equal to 3 we remove one
[78:30] item the 8 then you can see the size is
[78:33] equal to 2 and we can also find the 5
[78:37] when we find the 5 it actually returns a
[78:39] 5 when we can print that out and we can
[78:42] also print out the root which is 12
[78:43] that's the last item we added so that's
[78:46] at the front of the list so that's how
[78:49] the linked list works so a circular
[78:52] linked list is almost identical to a
[78:55] standard linked list except that from
[78:56] the very end node instead of having no a
[79:00] none pointer to the next node it's going
[79:04] to have a loop back to the very
[79:05] beginning to the root node the add
[79:08] operation in circular linked lists works
[79:11] slightly differently because we have
[79:13] this loop back to the first node from
[79:16] the end node we'd rather not have to go
[79:18] back and update that every time we
[79:20] insert a new node so we don't insert the
[79:22] new node as the root node anymore now
[79:25] instead we're going to insert it as the
[79:26] second node we leave the root pointer
[79:29] and the last pointer the loop back to
[79:32] the root the same and instead we insert
[79:35] our new node as the roots next node and
[79:38] then the next node for our new node is
[79:41] going to be what was the previously the
[79:43] second node so that's the add operation
[79:45] for circular linked list so that's
[79:48] basically yeah that's the only
[79:50] difference with a circular linked list
[79:52] so what are the advantages of a circular
[79:55] link list well it's great for modeling
[79:57] continuously looping data or objects so
[80:00] something like a Monopoly board or
[80:02] in-game board or a racetrack or
[80:04] something that continuously loops and
[80:07] there are a lot of different looping
[80:08] objects in the real world so if you want
[80:10] to model some continuously looping set
[80:13] of objects in a computer program a
[80:15] circular linked list is one way to do
[80:17] that
[80:17] the circular link list is very similar
[80:19] to the linked list with a few
[80:21] modifications in the add method we have
[80:25] to check whether a the list is empty and
[80:27] if it is then we add the first node then
[80:30] we make its next node point to itself it
[80:34] sounds crazy but we need to loop back to
[80:36] something so we loop back to the first
[80:38] node the root node else if there's
[80:41] already at least one node in the list we
[80:44] can create a new node and insert it into
[80:47] the number two position right after the
[80:49] root and change the roots next node to
[80:53] point to this new node so that's how the
[80:55] add operation works we can see the code
[80:58] here it's only a few lines of code the
[81:02] fine method works exactly the same as in
[81:04] the regular linked list except that in
[81:07] this Elif statement we have to do a
[81:09] check if we've circled all the way back
[81:11] to the root node again because if we
[81:13] have we have to stop our find and return
[81:15] false we didn't find it we search the
[81:17] entire list we didn't find the value
[81:19] we're looking for we turn false for the
[81:26] remove method let's scroll down here for
[81:31] the remove method we need to track both
[81:33] this node and the previous node so we're
[81:37] going to set pointers for both of those
[81:38] to start out so we'll start out at the
[81:40] root node and we'll set previous node to
[81:42] none and you can see towards the end of
[81:45] our while loop here we advance both of
[81:47] these pointers one node so they move
[81:50] both move forward to the next node now
[81:53] we test if we found the data that's this
[81:55] first if statement
[81:56] bingo found if we pass this test and if
[82:01] so there are two possibilities for the
[82:03] remove function
[82:04] number one if the previous node is not
[82:07] none tests whether the data was found in
[82:11] the root node and if not the remove is
[82:14] an easy bypass operation for changing
[82:17] the previous nodes next pointer which is
[82:19] what we do here and taste number two
[82:23] else if we need to delete the root we
[82:27] use this while loop to find the very
[82:29] last node in the list so that we can
[82:31] update its next node to point to the new
[82:35] root because the root has changed so we
[82:39] find that we find the new we find the
[82:41] last node we update the last nodes new
[82:44] next pointer which is the new root and
[82:47] then we update the root pointer itself
[82:51] lastly we decrement the size by one and
[82:54] we return true if we successfully remove
[82:56] the data and in our print list method we
[83:00] iterate through the list we print each
[83:01] node file Bob followed by an arrow you
[83:04] can see and our while loop has to check
[83:07] if you've made it back to the root so we
[83:09] know when to stop so this is the test we
[83:11] have here while this node next node is
[83:14] not the root we continue to iterate
[83:16] through the list now let's take a look
[83:21] at the circular linked list test code
[83:23] here we create a certain new circular
[83:25] linked list we'll just call it CLL we're
[83:28] going to add a bunch of items to it
[83:29] using a for loop adding one item at a
[83:32] time and then we can print the size of
[83:34] the list we can see down here the result
[83:36] the size is five we try to find an
[83:38] eighth if the value is actually in there
[83:41] it will return eight if we try to find
[83:44] an item that's not a no list is going to
[83:46] return false
[83:47] so we can see when we try to find the 12
[83:49] we get back a false and instead of using
[83:53] our print list function here we're going
[83:55] to iterate through continuously so that
[83:57] you can see when we pass by we're gonna
[83:59] print eight items even though they're
[84:01] only five in the list so we're gonna see
[84:04] if it actually does circle back to the
[84:05] next node we're just going to
[84:06] continuously get the next node up until
[84:08] we reach eight of them so we can see
[84:10] five nine eight three seven and then it
[84:12] starts from the beginning again five
[84:14] nine eight three it'll continue on we
[84:17] print up
[84:17] eight items so that shows you that it's
[84:20] a continuous loop and we can continue to
[84:22] loop through that if we want to write a
[84:25] little more test code we can print the
[84:27] list and here's the current contents of
[84:28] the list and then we are removing eight
[84:31] and when we print out remove fifteen
[84:33] result we see that it's false because
[84:36] there's no 15 in the list we can see
[84:37] that and we print the size of the list
[84:40] now we have four items because we
[84:42] removed one we try to remove the five
[84:44] node that completes successfully and
[84:48] then we print the list again and we only
[84:49] have three items left so that wraps up
[84:52] this lecture on a circular length list
[84:55] now let's look at doubly linked lists
[84:58] these are also sometimes called
[84:59] bi-directional linked lists because they
[85:01] have arrows pointing both directions to
[85:04] the next node and to the previous node
[85:06] so a regular linked list looks like this
[85:09] a doubly linked list each node has three
[85:14] pieces of data it has a pointer to the
[85:16] previous node a pointer to the next node
[85:18] and the data itself is storing so ask
[85:22] those three things three components to
[85:25] the node of a doubly linked list so this
[85:29] is what a doubly linked list would look
[85:30] like a simple one with three nodes we
[85:33] have here four or twenty three and a
[85:34] seven so let's say we want to delete an
[85:38] item this is a little more complicated
[85:41] because we have two pointers to fix not
[85:43] just one so we found this item that we
[85:46] want to delete we're going to call that
[85:48] this node and then the previous node to
[85:50] this node is the four and the next note
[85:53] is the seven so how do we delete it well
[85:56] we look at this pointer from the
[85:58] previous node that's pointing to this
[86:00] node and we look at the pointer from the
[86:02] next node that's pointing to its
[86:03] previous node right these ones that are
[86:06] pointing to this node they have to be
[86:09] fixed they basically just have to bypass
[86:11] it so what we do is we change fours next
[86:16] pointer instead of pointing to this it
[86:19] has to point to this nodes next node and
[86:22] then for sevens
[86:25] previous pointer instead of pointing to
[86:28] sevens previous node it has to point to
[86:30] this
[86:31] nodes previous node so we we basically
[86:36] do two adjustments here pre done next
[86:39] equals this dot next and next up pre
[86:43] evils this dot preview changes that we
[86:46] do to cut this node out of the list and
[86:49] you see once we get these red arrows in
[86:50] place once we fix these two pointers
[86:52] we've effectively cut no.23 out of our
[86:55] linked list we've deleted it so that's
[86:58] how the delete operation works in a
[87:00] doubly linked list some advantages of
[87:03] the doubly linked list over a standard
[87:05] linked list you can iterate through the
[87:07] list in either direction that's pretty
[87:09] obvious but when you have a really large
[87:12] linked list and you don't want to
[87:14] iterate through all of the items because
[87:16] you happen to know that your item is
[87:17] towards the end of the list you can
[87:20] actually save quite a lot of time by
[87:21] starting your iteration at the tail end
[87:23] of the list and working right back so
[87:25] you could save a pointer to the very end
[87:28] of the list as well and you can delete a
[87:31] node without iterating through the
[87:34] entire list that is if you have a
[87:35] pointer to that node right if you know
[87:38] where that node is that you want to
[87:39] delete and you don't have to iterate
[87:40] through the whole list to find it each
[87:43] node already stores its previous in next
[87:45] pointer so you can get the nodes on
[87:47] either side of this node that we want to
[87:48] delete without having to iterate through
[87:51] the entire list if you have a pointer to
[87:53] the node you want to delete doubly
[87:55] linked list uses an extra node attribute
[87:57] called priva as I showed you before when
[88:00] we looked at the node class and it also
[88:03] has an extra list attribute called last
[88:05] you can see here last so that we can
[88:09] always access the tail end of the list
[88:11] or the last item in the list now the add
[88:15] method has to check if the list is empty
[88:17] and if so then the root node is also the
[88:21] last node so otherwise it adds a new
[88:25] node to the beginning and it changes the
[88:27] roots previa fails two different
[88:31] conditions here for the add a new node
[88:34] the find method works exactly the same
[88:37] as the find method for the standard
[88:40] linked list so there's really no changes
[88:41] on that the remove function
[88:44] it is a little different there are three
[88:46] possible cases in the remove function so
[88:49] let's review each one of those case
[88:51] number one we're trying to delete a
[88:52] middle node that's this if statement
[88:54] here so the node is not in either the
[88:58] root or in the last node that's the
[89:02] standard case that we showed in two
[89:03] slides so for this we just do a simple
[89:05] bypass we bypass the target node and by
[89:09] changing the previous nodes next pointer
[89:10] and the next nodes previous pointer
[89:13] which is exactly what we're doing here
[89:15] then we've basically bypassed the target
[89:18] node that we're trying to delete now the
[89:20] second case is that we're trying to
[89:22] delete the last node this is just like
[89:25] case one except that the previous nodes
[89:28] next pointer will be changed to none
[89:30] because the second-to-last node is now
[89:33] the last node so that's the only
[89:35] difference here so we we're changing the
[89:38] basically the second-to-last nodes next
[89:40] pointer to none and the third case is
[89:44] we're trying to delete the root node and
[89:47] this is again similar to case one except
[89:50] that we change the root pointer to point
[89:53] to the second node in other words we
[89:56] change root to point two roots next node
[89:58] and that's it those are the three cases
[90:01] for remove the rest of the remove
[90:04] function is really straightforward the
[90:07] print list method is pretty much the
[90:08] same there's not no changes there so
[90:10] let's look at the test code for the
[90:12] doubly linked list here will create a
[90:16] doubly linked list dll we'll call it we
[90:19] add a bunch of items using a for loop to
[90:21] add each one of those items in we can
[90:22] see we print the size is 5 and we can
[90:25] print the entire list if we want using
[90:27] our print list method and then we can
[90:30] remove an 8 will print out the size
[90:32] again we can see the sizes for so these
[90:34] things all work and then if we try to
[90:36] remove items that are not in the list
[90:38] you'll l dot remove 15 that doesn't work
[90:41] if we try to find an item that's not in
[90:43] the list we also get false back and if
[90:46] we add some numbers 21 and 22 and then
[90:50] we remove a 5 and then we print the list
[90:52] again we can see that 21 and 22 were
[90:54] added to the front of the list and the 5
[90:57] was removed
[90:58] was a tail node the last node in the
[91:00] list and we successfully removed that
[91:01] and then just for fun we see that we can
[91:04] print out the last nodes previous node
[91:06] which should be the node right before
[91:08] the three of the nine which is this
[91:10] three which is exactly what it does so
[91:12] we can access nodes from the tail end of
[91:15] the list also that wraps up this section
[91:18] on linked lists so in this section we
[91:22] covered a standard linked list a
[91:23] circular linked list and a doubly linked
[91:26] list or a bi-directional linked list we
[91:29] showed you how those work and then we
[91:32] implemented them in code and again I
[91:34] encourage you to download this code and
[91:36] run it and try it out make some edits to
[91:39] it change it use your own tests on it
[91:42] and see how it works by using a code
[91:45] you're gonna better understand how the
[91:46] code works how linked lists work and how
[91:49] to eventually write your a linked list
[91:50] code hopefully in this lecture we're
[91:53] going to talk about trees after section
[91:56] one where we covered pythons built-in
[91:58] data structures trees is definitely the
[92:00] next most important section of this
[92:02] course trees are critically important
[92:04] data structure in all programming
[92:06] languages and let me explain why to make
[92:07] a point I'm thinking of a number between
[92:10] 1 and 8 million can you guess my number
[92:12] well you guessed 4 million I just say
[92:14] wrong and you're thinking uh-oh aren't
[92:18] you gonna tell me higher or lower no you
[92:20] have to guess until you get my number
[92:22] well you might have to guess every
[92:24] number between 1 and 8 million to figure
[92:26] out which number it is so if you're
[92:28] using a list an unsorted list as your
[92:31] data structure that's what it's like you
[92:33] would have to iterate through the entire
[92:36] list to find the number so you may have
[92:38] to do up to 8 million comparisons to
[92:41] locate that number that I'm thinking of
[92:43] that is the issue with lists when you
[92:45] have a lot of data it's really slow to
[92:48] find data now with a tree it's a little
[92:51] different you guess 4 million and I say
[92:54] lower you guessed 2 million I say higher
[92:58] you've got 3 million lower ok Wow with 3
[93:01] guesses
[93:02] you've shaved off 7 million
[93:03] possibilities and now you've narrowed
[93:05] down the possibilities to between 2 and
[93:07] 3 million
[93:08] you're only 1 million possibilities left
[93:10] with just 3 guesses so with as few as 30
[93:13] guesses you would be able to find any
[93:16] piece of data in a tree with up to 10
[93:18] million nodes so that is how fast binary
[93:22] search trees are a balanced binary
[93:24] search tree will let you locate data in
[93:26] a very large tree with as little as 30
[93:30] comparisons so now let's take a look at
[93:32] some of the major operations of trees
[93:34] and how they work so first let's learn
[93:36] some basic terminology about trees this
[93:39] is a node each part of a tree is called
[93:42] a node and each connection between nodes
[93:46] is called an edge and at the very top of
[93:51] the tree we have a root node you can see
[93:54] that trees are actually upside down
[93:56] compared to real-world trees this is
[93:58] more like a root system of a tree or a
[93:59] flipped upside down tree or like a
[94:02] management hierarchy in a company or
[94:04] something right we only have one
[94:05] president and then you have multiple
[94:07] vice presidents and so on down trees are
[94:09] great for modeling organizations but
[94:12] that's not the real benefit of tree the
[94:14] real benefit is the speed now we have
[94:16] parent nodes and child nodes in a binary
[94:19] tree a parent can have up to two
[94:22] children one or two children nodes that
[94:25] have the same parent are called sibling
[94:27] nodes and bottom nodes at the very
[94:30] bottom of the tree that don't have any
[94:33] children are called leaf nodes not all
[94:36] trees are binary trees but in a binary
[94:38] tree each node can have up to two child
[94:40] nodes a left and right child node now
[94:44] some trees may have 5/10 of up to a
[94:47] thousand child nodes for each node we
[94:50] can see the off of five here we have a
[94:52] sub tree a sub tree connects to a root
[94:55] node here and a sub tree is basically
[95:00] any part of a tree that in itself is a
[95:03] tree so it can be a sub tree of five
[95:07] compared to node 4 3 & 5 rows ancestors
[95:10] which is a parent node and every node
[95:12] above it's not the parent in the tree
[95:16] descendants are every node below that
[95:18] node in a tree so node 5's descendant
[95:21] includes everything in its left subtree
[95:23] and everything
[95:24] right sub-tree in a binary search tree
[95:27] each node is greater than every node in
[95:31] its left subtree so here we can see that
[95:33] 15 is greater than every single node in
[95:36] its left subtree and 8 is greater than
[95:40] every node in its left subtree and the 5
[95:44] is greater than every node in this sub
[95:46] tree the 24 is look greater than every
[95:50] node in its left subtree so this is a
[95:52] standard requirement for binary search
[95:54] trees each node is greater than every
[95:57] node in its left subtree and it's also
[96:00] less than each node in its right subtree
[96:03] here we can see that all the nodes in
[96:05] 15's right subtree are greater than 15
[96:08] and all the nodes in 24 right subtree
[96:12] are greater than 20 for all the nodes in
[96:15] 8 right subtree are greater than 8 so
[96:18] those are 2 standard requirements for a
[96:20] binary search tree some of the standard
[96:22] operations that L binary search trees
[96:25] are going to use insert I'm going to be
[96:27] able to add new data to the tree fine we
[96:30] want to be able to locate data in the
[96:31] tree delete is to remove a node get size
[96:35] counts all the nodes in a tree to tell
[96:38] us how many pieces of data we have in a
[96:39] tree in traversals which enable us to
[96:42] walk through the tree node by node and
[96:45] I'll show you how some of those work
[96:47] first let's look at the insert method
[96:49] we're going to always start at the root
[96:52] when we're doing an insert so at the top
[96:54] in this tree it's 215 we're always going
[96:58] to insert a new node as a leaf in other
[97:01] words at the very bottom of the tree but
[97:03] we start at the top to locate the right
[97:06] position the correct position in the
[97:08] tree to insert that new leaf so let's
[97:11] say we want to insert 12 in this tree
[97:13] we're going to start out with
[97:15] comparisons starting at the root is 12
[97:17] less than 15 yes it is so we're going to
[97:20] descend down 15 left subtree next we're
[97:24] going to compare 12 to 8 is 12 less than
[97:27] 8 no it's not so we're going to descend
[97:29] down 8 right subtree towards the 11
[97:33] there's 12 less than 11 no it's not
[97:37] and then we compare 12 to 13 and we say
[97:40] well yeah 12 is less than 13 so we're
[97:43] again we're going to add the 12 as a
[97:46] leaf node so we can add it as 13s left
[97:49] child that's how the insert function
[97:55] works now let's look at the fine method
[97:57] again with fine we'll always start at
[97:59] the root here it's 15 and we're going to
[98:03] do comparisons so if we want to find 19
[98:06] in this tree we're going to start by
[98:07] comparing 19 to 15 is 19 less than 15 no
[98:11] it's greater so we descend down the
[98:13] right subtree and then we compare 19 to
[98:17] 24 19 is less than 24 so we go down 24
[98:21] left subtree you can see how with each
[98:24] comparison and decision we descend down
[98:27] one subtree that cuts in half the number
[98:29] of remaining possibilities to locate an
[98:32] item so now we've already in two
[98:35] comparisons found the 19 in this tree so
[98:38] when we find a piece of data with define
[98:40] function we're always going to return
[98:42] that piece of data and if we didn't find
[98:44] it we want to return false to let the
[98:47] user know that data is not existing in a
[98:49] tree so with delete there are three
[98:52] different possibilities one is that the
[98:55] nobody.one delete is a leaf node another
[98:59] possibility is that it has one child
[99:00] node then there's another possibility
[99:02] that has two child nodes so each one of
[99:05] these we have to handle differently
[99:07] delete is a fairly complicated operation
[99:10] so let's first look at the possibility
[99:12] that the number we want to delete is a
[99:14] leaf node so look at these are all these
[99:17] gray nodes are all leaf nodes so in a
[99:21] case of a leaf node it's easy for us to
[99:23] just delete the leaf node without
[99:25] affecting anything else in the tree
[99:27] these are bottom most nodes so it
[99:30] doesn't affect the organization of
[99:31] anything else in the tree we can just
[99:33] delete that node if it's in the leaf
[99:35] that's the easiest case right there now
[99:39] if we have one child
[99:41] these are cases where we have one child
[99:44] note 11 13 and 28 if we want to delete
[99:48] one of those nodes we have to promote
[99:51] that child node to the targets notes
[99:54] position so for instance if we wanted to
[99:57] delete the 28 we would promote 25 to 28
[100:00] position if we want to delete the 11 we
[100:04] would have to promote the 13 to 11th
[100:06] position and the 12 comes with it you're
[100:09] promoting that entire subtree so that's
[100:11] the one child delete and then if you
[100:14] have two children well that gets a
[100:16] little trickier let's say we're going to
[100:18] delete the 24 and we could see that 24
[100:21] has two children we find the next higher
[100:24] node in order to do that we're gonna
[100:26] descend down 24s right subtree and then
[100:29] all the way to the left so here we get
[100:32] to 25 now if it was a much larger tree
[100:35] it'd be the same operation you take the
[100:37] right subtree and then the left most
[100:39] node in the right subtree and here it's
[100:41] 25 so the operation is to basically swap
[100:45] places the 24 and the 25 and then we can
[100:49] delete the 24 so we put the 25 where the
[100:52] 24 was and we can delete the 24 and the
[100:55] same thing if you want to delete the 4
[100:57] here we want to delete the 4 we can see
[100:59] that 4 has 2 children we want to find
[101:03] the next higher node after 4 and we find
[101:06] that 6 we descend on the right subtree
[101:08] in the left most node and of 6 so we
[101:12] delete the 4 and we promote the 6 to the
[101:14] 4th position and the 7 comes with it
[101:17] because 7 is part of 6 a subtree so
[101:21] that's the delete operation in a
[101:22] nutshell it's actually a little more
[101:23] complicated than that so we're not going
[101:25] to code it in this video however I do
[101:27] have another video on youtube or we code
[101:29] the entire delete function don't get
[101:32] sighs sometimes we may want to find out
[101:35] how many nodes are in a tree so this is
[101:37] a pretty easy operation to get size
[101:40] function returns the number of nodes and
[101:42] it works by using recursion actually all
[101:44] these functions in trees most of them
[101:46] are recursive so find delete insert
[101:49] we're doing it recursively because we
[101:51] continue to call the same function
[101:54] using the same parameter until we find
[101:57] the correct position to execute it so
[101:59] the getsize works the same way the size
[102:02] is equal to 1 plus the size of the left
[102:05] subtree plus the size of the right
[102:07] subtree in other words the size of this
[102:10] tree is equal to well the 5 note is 1
[102:14] plus the left subtree is the subtree
[102:19] starting with 3 and then the right
[102:21] subtree is the subtree starting with 8
[102:23] so we say the size of this tree is 1
[102:26] plus the size of these two sub trees and
[102:29] then we call the same thing the same get
[102:31] size function on 3 s left and right
[102:35] subtrees the size of the 3 sub tree is 1
[102:38] plus the size of 3 s left plus the size
[102:42] of threes right subtrees so we call
[102:44] recursively the get size function as we
[102:46] descend down the tree and eventually we
[102:49] get down to leaf nodes and return to 1
[102:50] oh yeah this is a leaf node size equals
[102:53] 1 and so all those ones get added back
[102:56] up as we decent as we retreat back from
[102:59] the call stack we almost talk about
[103:01] traversals sometimes we need to traverse
[103:04] the data in a tree and there are
[103:06] multiple ways of doing that a few
[103:08] different traversal algorithms are
[103:10] called pre-order traversal level
[103:12] traversal inorder traversal and post
[103:15] order traversal so in this video we're
[103:18] going to cover pre-order in-order
[103:19] traversal the pre-order traversal we
[103:22] visit the route before we visit the
[103:25] route sub trees so in other words we're
[103:28] always going to start at the root and
[103:29] then we'll visit the root sub tree and
[103:32] the same thing here with node 3 this is
[103:36] basically a sub tree starting at node 3
[103:38] we're going to visit 3 before we visited
[103:41] sub trees so we start at the top and
[103:44] then we descend down the left sub tree
[103:45] and again we descend down the left sub
[103:47] tree and then we hit the right sub tree
[103:49] and then we'll come back up and descend
[103:51] down 5's right sub tree
[103:53] we'll get the left subtree and then the
[103:55] right subtree so 1 2 3 4 5 6 7 you can
[104:01] see the order this is pre order
[104:04] traversal and inorder traversal visits
[104:07] the
[104:07] route between visiting route subtrees so
[104:11] that means that it can deliver values in
[104:13] sorted order so here we may want all
[104:16] these values in sorted order in which
[104:19] case we're going to start with the
[104:20] bottom left most node and work our way
[104:23] up so 1 3 4 we visit the ones parent
[104:28] node and then it's right subtree and
[104:31] then we visit threes parent node and
[104:34] then it's right subtree starting with
[104:36] the left most node so we're always in
[104:38] other words working our way up from the
[104:39] bottom and working our way to the right
[104:41] so that's an inorder traversal what are
[104:45] the advantages of binary search trees
[104:47] number 1 trees use recursion to
[104:49] implement most of their operations which
[104:51] makes them pretty easy to implement most
[104:53] of the code is pretty easy to write it's
[104:55] not very complicated well except for the
[104:57] delete which has a lot of different
[104:58] cases but the big huge advantage of
[105:02] binary search trees is speed they're
[105:04] really really fast at locating data you
[105:07] can insert delete and find data in a
[105:11] tree in Big O of H or the height of the
[105:14] tree depending on how many levels there
[105:17] are in a tree or put another way log in
[105:21] of the data the log of 10 million is
[105:24] about 30 in other words if you don't
[105:26] know a Big O means this is an order of
[105:28] operations and an approximation of how
[105:30] many operations it takes to achieve
[105:32] something so you can do all of these
[105:34] different operations in about the log n
[105:38] of the amount of data you have which is
[105:39] very fast so in a balanced binary search
[105:42] tree with ten million nodes you can do
[105:46] all the insert delete and find functions
[105:49] in as little as 30 comparisons that's
[105:52] incredible that's incredible so trees
[105:54] are extremely fast now let's take a look
[105:57] at how to implement trees now let's look
[106:00] at how to implement a tree in Python so
[106:03] we have this Jupiter and random here
[106:05] we're going to implement a binary search
[106:07] tree we have a few functions we have a
[106:09] constructor an insert find and get size
[106:13] method and then we have two different
[106:15] ways to traverse the tree pre-order and
[106:18] inorder traversal and I'll walk you
[106:20] through how all that
[106:21] works so in our constructor we have
[106:23] three attributes we have a piece of data
[106:25] that we're going to pass in as a
[106:27] required attribute and then optionally
[106:28] you can pass in a left subtree in a
[106:31] right subtree in this program we're
[106:33] really not using the left and right
[106:35] subtrees in the constructor so I have
[106:37] them defaulting to nine but each node is
[106:40] its own subtree and it has a left and
[106:42] right subtree so the insert function the
[106:47] key is defined of correct location to
[106:49] insert it and we're always going to
[106:50] insert it at the very bottom of the tree
[106:52] as a new node the first possibility is
[106:55] the node that we're in is equal to the
[106:58] data that we're trying to add in which
[107:00] case we're going to reject that we don't
[107:02] want any duplicates in our tree so in
[107:04] this case we're going to return false
[107:05] because we got a duplicate if the data
[107:08] passed in is less than the data in the
[107:10] current node then we're going to descend
[107:12] down the left subtree so we return self
[107:16] left subtree insert so in other words
[107:20] we're calling recursively the insert
[107:22] function descending down the left
[107:25] subtree and still passing the data along
[107:27] and the reason we have this return is
[107:29] because we want to return either true or
[107:31] false at the end of the day if the data
[107:33] was successfully inserted or not or if
[107:36] we reach the bottom level of the tree
[107:38] and we we've found the right position to
[107:40] insert it will create a new subtree with
[107:44] that piece of data and we'll set it up
[107:46] as the left subtree of its parent node
[107:48] and we return true because we added that
[107:51] data or we can descend down the right
[107:54] subtree if we descend on the right
[107:56] subtree again we're just doing a
[107:58] recursive function call to the insert
[108:00] function or passing the data in down the
[108:03] right subtree and when we reach the
[108:06] bottom of the right subtree
[108:08] we'll insert a new tree and we'll attach
[108:11] that as the right child of the parent
[108:14] node and then return true the find
[108:18] function works very similar except that
[108:19] we don't actually create a new item and
[108:21] insert it but we recursively descend
[108:25] down the either the left subtree or the
[108:27] right subtree so if we find that piece
[108:29] of data in the current node that we're
[108:30] in will return that piece of data
[108:33] if not we'll do a comparison to the
[108:36] current node to see if we should descend
[108:38] down the left sub tree or the right sub
[108:40] tree now if we reach the bottom of the
[108:43] tree where we have a nun note we're
[108:45] going to return false otherwise we call
[108:48] the find function recursively on the
[108:51] left subtree and we pass the data along
[108:53] as the same parameter and then the same
[108:56] on the right subtree when we reach the
[108:58] bottom of the right subtree and we
[108:59] didn't find the data yet in other words
[109:01] we reach a nun note then we're gonna
[109:03] return false because the data is not in
[109:05] the tree or if we didn't reach an
[109:08] unknown yet then we'll continue to send
[109:10] down the right subtree to find that data
[109:12] so this is a fine function we basically
[109:15] are just doing comparison and then
[109:16] descending down either the right or left
[109:18] subtree until we reach the bottom
[109:22] getsize like I showed you in the
[109:24] diagrams before if the node that we're
[109:27] in is not nun then we're going to return
[109:29] one plus the size of the left subtree
[109:31] plus the size of the right subtree so
[109:34] this works recursively we continue to
[109:36] call get size as we descend down the
[109:38] tree the left subtree and the right
[109:40] subtree we add all those together we add
[109:42] each one for each node we visit the
[109:45] pre-order traversal checks first if the
[109:47] node that we're in is not nun and if
[109:50] it's not then we'll print that data and
[109:52] then we'll continue down the left
[109:54] subtree calling the preorder traversal
[109:56] function recursively until we reach a
[109:58] nun note then we'll continue down the
[110:00] right subtree recursively until we reach
[110:03] a nun note the inorder traversal is not
[110:05] a whole lot different and you can see
[110:07] what's different between these two is
[110:09] that we here in the inorder traversal we
[110:11] have the print statement between those
[110:13] two subtrees and here the print
[110:16] statement in pre-order is before we
[110:18] descend on those two subtrees so that's
[110:20] really the key difference between
[110:21] pre-order and inorder traversal
[110:23] now let's take a look at the test code
[110:26] so in this test code we're going to
[110:28] create a new tree we do that using a
[110:31] value of 7 we pass in as a parameter so
[110:33] now we have a tree with a 7 as the root
[110:36] we insert a 9 into it so we have two
[110:39] items in the tree and then we just go
[110:41] through this whole list and add a whole
[110:42] bunch of different items oh look there's
[110:44] a duplicate so it's not going to add
[110:45] this
[110:46] and we insert each one of those items
[110:50] now we're going to print out the tree
[110:52] for I in range 16 so this will count
[110:55] from 0 through 15 we're going to do a
[110:57] find operation on each one of those
[110:59] numbers and we can see what it prints
[111:02] out is 4 0 it prints false 4 5 it prints
[111:05] false and 4 8 it prints false but all
[111:07] the rest of them it returns the number
[111:09] and it prints it out so you can see that
[111:11] there's no zero
[111:12] there's no 5 and there's no 8 in this
[111:14] list so it's unable to find those that
[111:16] return to false and that's what we print
[111:18] the get size function returns a 13 so
[111:22] that's the count of the nodes in the
[111:24] tree is 13 and then we do a pre-order
[111:27] traversal we print a blank line and we
[111:29] do an inorder traversal and you can see
[111:32] the inorder traversal is exactly the
[111:35] numbers in sorted order and again you
[111:38] can see that the 0 the 5 and the 8 are
[111:41] missing in this inorder traversal so
[111:45] that concludes this lecture on trees I
[111:48] recommend you to download the code try
[111:51] it out maybe try and code the postorder
[111:54] traversal and try and ricing different
[111:56] tests to actually use the tree maybe try
[111:58] and sorting letters in it or something
[112:00] or a million numbers and see how fast
[112:02] the tree performs so another really
[112:05] important data structure is graphs
[112:07] graphs are perfect for modeling
[112:10] real-world objects in a lot of cases a
[112:13] graph consists of vertices and edges
[112:16] connecting those vertices so for
[112:19] instance in a social network the
[112:21] vertices could be people right and the
[112:24] connections are friendships or
[112:27] relationships between people so there
[112:30] are two different types of graphs we can
[112:31] use undirected graphs where the
[112:33] relationship is both ways it's
[112:35] bi-directional so in this case in a
[112:38] social network typically relationships
[112:40] work both ways because both people know
[112:42] each other so here you can see there are
[112:44] a bunch of vertices and then a bunch of
[112:47] edges between the people who know each
[112:49] other so an undirected graph is a very
[112:52] common way to model relationships in a
[112:56] social network or connections between a
[112:58] real network where
[112:59] that nodes would be computers and the
[113:01] connections would be cables connecting
[113:04] those computers now another type of
[113:06] graph is a directed graph so if you
[113:09] wanted to model for instance airplane
[113:12] flights between cities well in some
[113:14] cases there may be a one-way flight or
[113:17] even a round-trip flight but each leg of
[113:20] that flight is gonna be represented by
[113:22] an arrow in other words which direction
[113:24] is going so if you have a flight going
[113:26] from Chicago to Seattle well it's not
[113:29] necessarily doesn't necessarily have a
[113:31] return flight so the best way to model
[113:33] this is using a directed graph which
[113:37] shows a one-way relationship so
[113:40] transportation and networking are just a
[113:42] couple of very many different possible
[113:44] applications for graphs in modeling real
[113:46] world problems so in this section we're
[113:49] going to cover the two most common ways
[113:51] to implement graphs which is using an
[113:53] adjacency list and an adjacency matrix
[113:56] an adjacency list stores a list of
[114:00] neighbors for each vertex in the vertex
[114:03] itself an adjacency matrix stores a 2d
[114:07] array of all the connections between the
[114:09] vertices in the graph object so let's
[114:12] take a look at this undirected graph
[114:14] with 5 vertices and a number of edges
[114:17] connecting them so in an adjacency list
[114:20] implementation each vertex would store
[114:23] its own list of vertices that is
[114:25] connected to so in this case a is
[114:28] connected to B C and D and that list of
[114:32] neighboring vertices would be stored in
[114:34] node A's neighbor lists and node B is
[114:38] connected to never to C's a and C and
[114:41] that would be stored in node B's list of
[114:44] neighbors now using the same undirected
[114:50] graph we could implement this using an
[114:53] adjacency matrix and the jason c matrix
[114:56] has all the from vertices and two
[114:58] vertices and it puts a zero where
[115:01] there's no edge and a one where there's
[115:03] an edge so here we can see from A to B
[115:06] there is an edge now since this is an
[115:10] undirected graph this is a
[115:12] mirror image across the diagonal as you
[115:14] might expect
[115:15] so if edge a connects to B then B also
[115:19] connects to a and this 2d matrix would
[115:23] be stored in the graph object itself so
[115:26] each vertex doesn't have to remember its
[115:28] own neighbors now if you have weighted
[115:31] edges it's much easier to implement this
[115:34] with an adjacency matrix why because
[115:36] instead of putting just a 1 you can put
[115:38] the weight in the matrix an adjacency
[115:42] list you'd have to probably put a tuple
[115:44] which includes the weight in the
[115:47] directed graph it's fairly easy to
[115:49] implement in either one of these so in
[115:52] an adjacency list you would just put the
[115:54] outbound edges from each vertex so from
[115:57] a you can see the a has an outbound edge
[115:59] to see so we would list in AZ Jason C
[116:02] list only node C and the directed graph
[116:07] and an adjacency matrix is similar it's
[116:10] not going to be symmetrical across the
[116:12] diagonal anymore because B connects to a
[116:16] but a does not connect directly to B so
[116:20] we can see that we have B to a is a 1
[116:22] but a to B is a zero which
[116:26] implementation is better well first
[116:29] let's look at two different types of
[116:30] graphs in a dense graph every vertex may
[116:34] be connected to every other vertex in
[116:36] the graph and that kind of graph there
[116:38] are are a lot of edges relative to the
[116:41] number of vertices so maybe each vertex
[116:43] is connected to every other vertex in
[116:46] the graph in which case the number of
[116:47] edges would be equal to the number of
[116:50] vertices squared in a sparse graph there
[116:55] are relatively few edges or maybe
[116:57] approximately similar to the number of
[116:59] vertices
[117:01] so when adjacency matrix takes up V
[117:05] squared space regardless of how dense
[117:07] the graph is so because we have a list
[117:10] of vertices along the x-axis and along
[117:13] the y-axis of this matrix it takes up V
[117:16] squared space for the matrix so a matrix
[117:20] for a graph with about 10,000 vertices
[117:22] would take up at least a hundred
[117:24] megabytes
[117:26] so some trade-offs and adjacency list is
[117:29] faster and uses less space for a really
[117:32] sparse graph but the con is that it's
[117:36] slower for dense graphs because for
[117:38] dense graphs it would have to iterate
[117:40] through all of the neighbors an
[117:42] adjacency matrix is faster for dense
[117:46] graphs because it can easily look things
[117:48] up using an index it's also simpler for
[117:51] weighted edges it's very easy to
[117:53] implement weighted edges but the con is
[117:56] that it uses a lot of space so as the
[117:59] number of vertices grows the amount of
[118:01] space required for the adjacency matrix
[118:03] grows by a factor of V squared next
[118:07] we're going to learn how to implement
[118:08] each of these methods in Python now
[118:11] let's look at the code I'll post the
[118:13] code on my github site both in a Jupiter
[118:15] notebook format which we're going to
[118:16] walk through in this video as well as
[118:18] the regular Python file so you can
[118:21] download that and test it in whichever
[118:22] format you prefer and try it out and I
[118:25] strongly recommend you do that so you
[118:26] can really understand how graphs work
[118:28] now in the code we basically have two
[118:31] classes we have a vertex class which is
[118:33] pretty simple and there's not a whole
[118:34] lot to it and then we have the graph
[118:37] class which is a little bit more
[118:38] substance to it but we'll walk through
[118:40] exactly how everything works and then we
[118:42] have a little bit test code and I'll
[118:43] show you how that works so first let's
[118:45] look at the vertex class we have two
[118:47] different methods here we have a
[118:49] constructor this init is just a
[118:50] constructor that creates a new vertex
[118:52] and basically it just sets two different
[118:55] attributes for a vertex object you can
[118:58] pass in the name in which is the name of
[119:00] the vertex which for us is just a single
[119:02] letter and then it assigns it to this
[119:04] named attribute for the vertex and then
[119:07] it also creates an empty set for the
[119:09] neighbors for that vertex and then add
[119:13] neighbors you can pass in the name of a
[119:15] vertex not to vertex object but the name
[119:17] of a vertex it adds that to the
[119:19] neighbors set for that vertex and
[119:21] remember sets don't store duplicates if
[119:25] that neighbor has already been added to
[119:27] the vertex it doesn't matter it won't be
[119:29] added a second time now let's look at
[119:32] the graph class which is a little more
[119:34] complex so we have a few different
[119:36] methods here
[119:38] first each graph object stores a
[119:40] vertices dictionary of all of the
[119:42] vertices and that is in the format of
[119:45] named vertex name and then vertex object
[119:49] so you can always access from vertex
[119:51] name you can always access the vertex
[119:52] object through the dictionary and when
[119:56] we add a vertex we pass in that vertex
[119:59] we check if that the object passed in is
[120:01] actually a vertex object and if the name
[120:04] is in the vertex list yet and if it if
[120:06] it's already in that dictionary then we
[120:08] obviously not gonna add it a second time
[120:09] and then we if it's not then we'll add
[120:11] that vertex to the vertex dictionary and
[120:14] return true otherwise we return false
[120:16] which says the add was unsuccessful and
[120:19] to add an edge every time we create a
[120:22] new edge we check if the both of the
[120:24] vertices are actually existing real
[120:26] vertices in the graph because if the
[120:27] vertex does not exist in that graph we
[120:29] can't have an edge connecting that
[120:31] vertex and assuming that both vertices
[120:33] are valid vertices then we add you two
[120:37] V's neighbor list and be to use neighbor
[120:39] list that's why we have two different
[120:41] add operations here and we return true
[120:44] and then to print the graph we're really
[120:47] just going to print out the neighbor
[120:49] list for each vertex of the name of the
[120:52] vertex and then that vertex is neighbor
[120:53] list and our test code
[120:56] well we'll create a new graph G here and
[120:58] then we're a few different ways to add
[121:00] vertices to that graph here's three
[121:02] different ways so we can create a new
[121:04] vertex a by passing into the vertex
[121:06] constructor the name of vertex a and
[121:09] then we can add vertex a using the add
[121:12] vertex method another way is we can do
[121:15] this all both of those steps in one
[121:17] operation using just add vertex and then
[121:20] create a new vertex called vertex B and
[121:22] then we could also use a for loop if we
[121:25] want to add a whole series of vertices
[121:27] here a through K we have to use order to
[121:30] get the numerical equivalent of a so
[121:33] that we can iterate through those using
[121:35] the range function and then we convert
[121:38] that back into a letter using CHR the
[121:41] character equivalent of that number so
[121:43] there's three different ways there that
[121:45] we can add vertices to our graph when we
[121:47] did all three and we don't have to worry
[121:49] about duplicates because we check for
[121:50] duplicates in
[121:51] add vertex function and then in adding
[121:56] edges well I just created a list of
[121:58] edges here basically a list consists of
[122:00] two letters which is the two vertices
[122:02] that that edge connects to and then we
[122:05] iterate through those and we add edge
[122:07] with the first letter and the second
[122:09] letter passing those two in and lastly
[122:13] we print the graph so now we have a
[122:15] graph with a bunch of vertices and a
[122:17] bunch of edges what does that graph look
[122:19] like
[122:19] well our print function doesn't really
[122:22] visualize the graph but it does show us
[122:24] what the adjacency lists look like look
[122:27] the adjacency list for a it looks like
[122:28] this it has neighbors B and E and B has
[122:32] neighbors a and F C has just a neighbor
[122:35] G so and if you take a look at the edges
[122:39] list you can figure that out to write a
[122:41] has an edge to B and E right and so you
[122:44] see B and E and Hayes neighbor lists but
[122:47] you're also going to see a in EES
[122:49] neighbor list so if we look down to E
[122:50] yep sure enough there's a so that's how
[122:54] an adjacency lists implementation works
[122:57] in code and again you can download the
[123:00] code and run this and try it out spend a
[123:02] little more time getting acquainted with
[123:03] it how about that and this
[123:06] implementation of graphs we use strings
[123:08] lists sets and dictionaries for data
[123:12] structures that we covered in section 1
[123:14] of this course in the next lecture we're
[123:18] going to learn how to implement graphs
[123:20] using adjacency matrix in this lecture
[123:24] we're gonna look at how graphs can be
[123:25] implemented using the adjacency matrix
[123:27] method so we walk through how the
[123:29] adjacency matrix works let's look at the
[123:32] code again this this code is posted on
[123:35] my github site both in a Python file
[123:38] and in a Jupiter notebook file you're
[123:40] welcome to download either one this code
[123:42] or I'm going to show here is the Jupiter
[123:44] notebook has a lot of comments in it so
[123:47] first we have a vertex class the vertex
[123:49] class is extremely simple in the matrix
[123:52] implementation because the matrix is
[123:54] basically in the graph class so the
[123:57] vertex class really doesn't have to do
[123:58] anything we have a constructor where we
[124:01] simply pass in the name of the vertex so
[124:04] we assign that
[124:05] in name to a single attribute called
[124:07] name and that's it that's all vertex has
[124:09] is a name the graph class is a little
[124:12] more complicated we have three key
[124:14] attributes here we have a dictionary of
[124:17] vertices and then we have a matrix of
[124:21] edges this is actually going to be a
[124:22] two-dimensional list of edges and then
[124:24] we have edge indices because the edges
[124:27] are unlabeled all it is is a series of
[124:29] zeros and ones so this is basically the
[124:32] labels that goes with the edges so this
[124:33] is not the only way to implement this
[124:35] this is how I chose to do it you can you
[124:38] can implement in a different different
[124:39] way if you want if you find this too
[124:40] complicated so we're gonna have a few
[124:42] different functions here or methods that
[124:44] are part of the graph class we're going
[124:46] to add vertex which is going to update
[124:48] all three of these attributes we're
[124:50] going to add an edge which only really
[124:52] needs to update the edges matrix and
[124:54] then we have a print function when we
[124:57] add a vertex we pass in that vertex
[124:59] first we're going to verify that that's
[125:01] a valid vertex object and that it's not
[125:04] already in the vertices list and if it's
[125:07] not then we'll go ahead and add it so
[125:09] the first step is to update the vertices
[125:11] dictionary by adding the name and vertex
[125:14] to that dictionary so in other words
[125:16] we'll have a and then the vertex object
[125:18] a next we're going to use a loop to
[125:22] append a column to the rightmost side of
[125:25] that matrix so the edges matrix so we
[125:30] use a for loop to do that and we append
[125:32] a column of zeros to the rightmost end
[125:34] of the edges matrix and then we need to
[125:38] put on the very bottom of the matrix we
[125:40] need to append two zeros a row of zeros
[125:42] on the very bottom so we do that using
[125:46] the self dot edges append 0 times length
[125:50] of edges plus 1 in other words however
[125:52] many edges there are we're going to add
[125:54] a 0 at the very bottom row for each one
[125:57] of those now since we just added a
[125:59] vertex there's obviously no edges
[126:01] connecting to it yet so we know these
[126:02] are all zeros but as we add edges
[126:05] connecting to that vertex then we're
[126:07] going to flip them to a 1 and the last
[126:10] step in adding a vertex is we update the
[126:13] edge vertices we add that vertex name
[126:16] and the index that we can find that
[126:18] vertex
[126:19] in the edges list and when we add an
[126:26] edge we pass in U and V which is the
[126:29] from and two vertices for the edge we
[126:33] have a default weight of one that's
[126:35] normal to have a default weight of one
[126:37] but you can override that by passing in
[126:39] whatever weight you want so if you want
[126:40] to use weighted edges it's pretty easy
[126:42] to do we check to make sure that both
[126:44] vertices that we passed in are valid
[126:46] vertex names in other words they're
[126:48] actually in the vertices dictionary so
[126:51] edges is a 2-dimensional list so we need
[126:53] two different indices to access a
[126:56] specific position in the matrix so we
[127:00] have U and V and then we have a B and u
[127:03] so we want to flip both of those four
[127:05] edges those two positions in this table
[127:08] set it equal to weight whatever weight
[127:10] you passed in or 1 if this is a default
[127:13] and lastly when we print a graph well
[127:16] you'll see how it prints out down below
[127:18] but we're starting out by printing the
[127:20] name of the vertex and then we're going
[127:23] to print out the row of ones and zeroes
[127:25] for that vertex so our test code we used
[127:29] exactly the same test code that we use
[127:31] for the other implementation of the
[127:33] graph using adjacency lists the test
[127:36] code is identical so we create a new
[127:39] graph we have three different ways of
[127:41] adding a vertex to the graph first we
[127:44] for a we create a new vertex object and
[127:46] then we do add vertex a and then for B
[127:50] we add vertex and we'll create a new new
[127:53] vertex inside the parentheses here and
[127:56] then we use the for loop method where we
[127:58] iterate through the a through K and we
[128:02] add them to the graph and then to add an
[128:04] edge I created a list of edges here this
[128:06] is the same list we used in the other
[128:08] test code for edge and edges and
[128:11] iterating through those edges we add
[128:13] each edge one that's one at a time we
[128:16] pass into the add edge method two
[128:18] parameters in this case it would be the
[128:21] a and the B so we're getting the left
[128:23] character and the right character we're
[128:25] passing those in as the attributes and
[128:26] then when we print out the graph we see
[128:28] what this looks like this is what our
[128:30] neighbors matrix looks like at the end
[128:32] of it is
[128:33] so you can see where we have a one is a
[128:36] neighbor for a so this would be B C D E
[128:41] so B and E are s neighbors right
[128:45] wherever there's a one and then this is
[128:49] column a so we can see that a has an
[128:52] edge to B and E so in other words you
[128:55] can see that it's symmetrical across
[128:56] this diagonal and every place where
[129:00] there is a one reflects an edge between
[129:02] two vertices so I recommend you download
[129:06] the code test it out try to use it and
[129:08] get familiar with it these are two
[129:10] different implementations for graphs and
[129:11] it's important to understand both
[129:12] because there is no one best method as I
[129:16] already explained in different instances
[129:19] each method has its advantages in this
[129:22] course we've covered a lot of different
[129:24] data structures we've learned how to use
[129:27] different data structures as well as how
[129:28] to implement and some of the pros and
[129:30] cons of each now you'll have a lot of
[129:33] new tools in your tool belt as a
[129:34] programmer to south problems as you're
[129:37] developing code thank you for taking
[129:40] this course
[129:49] you