---
title: 'Data Structures And Algorithms in Python - Python Data Structures Full Tutorial (2020)'
source: 'https://youtube.com/watch?v=kQDxmjfkIKY'
video_id: 'kQDxmjfkIKY'
date: 2026-06-14
duration_sec: 7809
---

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

> Source: [Data Structures And Algorithms in Python - Python Data Structures Full Tutorial (2020)](https://youtube.com/watch?v=kQDxmjfkIKY)

## Summary

This course provides a comprehensive overview of data structures in Python, covering built-in types like strings, lists, tuples, sets, and dictionaries, as well as advanced structures such as stacks, queues, heaps, linked lists, binary search trees, and graphs. The instructor emphasizes the importance of choosing the right data structure for each programming task to improve efficiency and code quality.

### Key Points

- **Course Introduction** [00:13] — Joe James, a software engineer with a master's in computer science, introduces the course on data structures in Python, comparing them to a carpenter's tool belt.
- **Sequence Types: Indexing** [01:39] — Explains indexing in sequences (strings, lists, tuples) starting at 0, using square brackets to access elements.
- **Slicing Sequences** [02:50] — Covers slicing with start, end, and step parameters; defaults are start=0, end=length, step=1. Negative indices count from the end.
- **Adding and Concatenating Sequences** [06:32] — Shows how to combine sequences of the same type using + and multiply sequences using *.
- **Testing Membership** [08:06] — Using 'in' and 'not in' to check if an item exists in a sequence.
- **Iterating Sequences** [08:59] — Using for loops to iterate items, and enumerate() to get both index and item.
- **Common Sequence Functions** [09:54] — len(), min(), max(), sum(), sorted(), count(), index() are demonstrated on strings, lists, and tuples.
- **Unpacking Sequences** [15:09] — Assigning sequence elements to multiple variables in one line.
- **Lists: Constructors and Comprehensions** [16:03] — Creating lists using list() constructor, square brackets, or list comprehensions (e.g., [m for m in range(8)]).
- **List Methods: del, append, extend, insert, pop, remove, reverse, sort** [18:56] — Demonstrates common list operations including in-place modifications.
- **Tuples: Immutability and Constructors** [24:03] — Tuples are immutable, created with parentheses or commas. They are faster for fixed data.
- **Tuples: Mutable Objects Inside** [26:08] — Although tuples are immutable, if they contain mutable objects like lists, those can be modified.
- **Sets: Unordered, No Duplicates** [28:24] — Sets store unique items, provide fast membership testing via hashing, and support mathematical operations like union and intersection.
- **Set Constructors and Operations** [29:23] — Creating sets with curly braces or set() constructor. Operations: add, remove, pop, clear, union (|), intersection (&), difference (-), symmetric difference (^), subset/superset checks.
- **Dictionaries: Key-Value Pairs** [33:04] — Dictionaries are unordered, created with curly braces and colons. Keys are unique, values can be any type.
- **Dictionary Operations** [34:40] — Adding/updating items with assignment, deleting with del, accessing keys/values/items, membership testing in keys.
- **Iterating Dictionaries** [37:20] — Iterating over keys, or using items() to get key-value pairs.
- **List Comprehensions** [38:55] — A powerful feature to create lists using a for loop inside square brackets, optionally with a filter condition.
- **Stacks: LIFO Data Structure** [46:02] — Stacks are last-in-first-out. Key operations: push (append), pop, peek. Implemented using Python lists or a wrapper class.
- **Queues: FIFO Data Structure** [52:01] — Queues are first-in-first-out. Implemented using collections.deque with append and popleft.
- **Max Heaps: Priority Queue** [54:47] — A max heap ensures every node is ≤ its parent. Insert and pop are O(log n), peek is O(1). Implemented with a list where children are at 2i and 2i+1.
- **Linked Lists: Nodes and Pointers** [69:22] — A linked list consists of nodes, each containing data and a pointer to the next node. Operations: add (at front), find, remove, print.
- **Circular Linked Lists** [78:52] — The last node points back to the root. Insertion is done after the root to avoid updating the tail pointer.
- **Doubly Linked Lists** [84:55] — Each node has pointers to both next and previous nodes. Allows bidirectional traversal and easier deletion.
- **Binary Search Trees: Fast Search** [91:53] — BSTs enable O(log n) search, insert, and delete. Each node is greater than all nodes in its left subtree and less than all in its right subtree.
- **BST Insert and Find** [96:47] — Insert and find use recursion to traverse the tree, comparing values to decide left or right.
- **BST Delete Cases** [98:52] — Three cases: leaf node (easy delete), one child (promote child), two children (swap with inorder successor).
- **Tree Traversals** [101:35] — Pre-order (root, left, right), in-order (left, root, right – gives sorted order), post-order (left, right, root).
- **Graphs: Vertices and Edges** [105:57] — Graphs model relationships. Undirected graphs have bidirectional edges; directed graphs have one-way edges.
- **Adjacency List vs Matrix** [107:51] — Adjacency list stores neighbors per vertex; adjacency matrix uses a 2D array. Lists are better for sparse graphs, matrices for dense graphs.
- **Graph Implementation: Adjacency List** [110:56] — Vertex class stores name and neighbor set. Graph class stores vertices dictionary and provides add_vertex, add_edge, and print methods.
- **Graph Implementation: Adjacency Matrix** [123:24] — Graph class stores vertices dictionary, edge matrix (2D list), and edge indices. Adding a vertex expands the matrix.

### Conclusion

Mastering data structures in Python equips you with the right tools for efficient programming. The course covers built-in structures and advanced ones, emphasizing practical implementation and trade-offs.

## Transcript

hi I'm Joe James I have master's degree
in computer science and I'm a software
engineer in Silicon Valley and in this
course we're gonna learn about data
structures in Python you might be
wondering well why should I care about
data structures in Python let's imagine
for a second that your carpenter you
wouldn't try to pound in a nail with the
screwdriver that just doesn't make sense
carpenters no you can't do that you also
wouldn't try to drive into screw with
the pair of pliers so carpenters know
that for every task there's a best tool
for the job
and that's why carpenters carry around a
tool belt full of tools and those tools
are specialized for different tasks and
that's exactly what you're going to do
when you master data structures in
Python data structures are your tool
belt for each task you face as a
programmer you're going to know exactly
which data structure to use and how to
use it you're going to save time write
better code and do it more efficiently
so in this course we're gonna learn
about pythons built-in data structures
strings lists tuples sets and
dictionaries then we're going to
continue to learn about queues stacks
and heaps we're also going to learn
about linked lists then we're going to
cover binary search trees and graphs
you're gonna learn how to use these data
structures how to implement them in
Python and you're going to learn the
strengths and weaknesses of each of
these data structures so let's look at
some of the code first we'll look at
sequence types string list and tupple so
I put a link here to the documentation
this is the official Python
documentation encourage you to check
that out if you have any questions or
you want more detail on you needing
these items just look at the
documentation link here so first is
indexing we can access any item in a
sequence by using its index we put that
index inside square brackets an indexing
starts with zero the first element is
always zero
so the fourth element is going to be
index three so here we have a string
frog as four letters in it if we want
the fourth element which is G we print
out X of 3 that gives us the G as you
can see in the output here if we have a
list of pig cow and horse these are
strings we can print out X of 1 and
that's going to give us cow and again
it's just square brackets and a tuple
with four names in it and if we want the
very first name we print out X of zero
with the zero in square brackets and
that gives us Kevon so that's indexing
now let's look at slicing we can slice
out sub strings sub lists or sub temples
using indexes so the way indexing works
is you put inside the square brackets
separated by colons three possible
parameters so we can put a start and end
plus one and a step and I'll show you
what each of these means so let's just
use a string for this example computer
the word computer again the sea is index
0 so here we're going to print out X of
1 to 4 so since we didn't put a third
parameter that means the step is assumed
to be 1 that's the default step so when
we put 1 that means the O and that is
inclusive the from is or the start is
always inclusive the end is non
inclusive so if we look at item number 4
that's the U that's the fifth item it's
not inclusive so it's really just going
to get OMP for us and when we look at
the result it prints out OMP now here's
an example using a step so we print out
X of 1 to 6 again we're going to start
at the O because the 1 is inclusive and
we're going to go up to 6 which is the e
but it's non inclusive and we're going
to do it in a step of 2 so in other
words we're going to get to O the P and
the T and that's what we print out opt
so it takes every other item when we
have a step of 2
next we're going to not put a end
plus-one we're just gonna leave an open
colon there and what happens is when we
put the open colon 3 : nothing basically
the default is end of string so
everything from the third item on so
here the third item is P because we
start counting at zero the third item is
P and we get everything from P onward P
UT ER so if you don't know how long a
string is or you just want to get all of
the remaining elements skip the first
three three items or something you use
an open : next we're not going to
declare a start so we can skip the start
by just putting : five so in other words
our default is we're going to start from
the beginning of the string we're going
to get up to the sixth item because the
v is not inclusive so c om p u and you
can see our result here are Co MP u so
you can see if you don't declare a start
the start defaults to the beginning and
if you don't declare an end the end
defaults to the end and if you don't
declare a step the step defaults to one
so that's basically what's happening
here let's look at a negative index so
if we print out just a negative index
negative one that counts from the right
side of the string so here we want the
very last item in the string we put
negative 1 we get the are the last
element and then here we get the last
three items so we put a negative three
as the from and to the end of the string
so that gives us ter that gives us the
last 3 elements and then if we want to
get everything except the last two
elements of the string we leave this
start blank so we get everything from
the beginning up until the last two
items so that is how slicing works and
it works exactly the same as we just
covered for this string example works
exactly the same on lists and tuples
now let's look at adding and
concatenating so we can combine two
sequences of the same type using the
plus sign let's look at a string example
first we want to combine horse and shoe
and we just print X so we see the result
is horseshoe if we have two separate
lists and we want to merge those two
lists together we can use a plus sign
and when we print that we get a single
list with three elements in it and in
the case of tuples if we have two
separate tuples and we print the result
we get a single tuple with four elements
in it now it's important to note here
for the second one to be considered a
tupple we have to include a comma here
if we don't have that comma it's just a
string in parentheses if we include this
comma that tells python that this is
actually a tuple we can use the
multiplying function to multiply a
sequence using the asterisk in a string
example if we want to print bug three
times we just do bug times three and
then print and you can see the result
here is bug bug bug and the same with a
list we have a list eight comma five and
we want to multiply that by three what
we get is eight five eight five eight
five so we're not actually multiplying
the elements by three we're multiplying
the list by three and then the same with
tuple we can multiply at up all by three
and then we get basically a triplicate
of that tupple now let's look at testing
membership we can test whether an item
is in or not in a sequence these are
really easy
it's almost English key words in Python
they made it so simple so with a string
let's say we have a string called bug
and we want to check if the letter U is
in our string we just say u in X and
that's going to give us a boolean result
true or false in this case u is in X so
it returns true and now we have a list
pig cow and horse if we print cow not in
Y it's going to print false because cow
is in Y
and for a couple example we have a
couple here with four names and if we
print one of those names in Z we get
true because it is in Z so it's really
easy to check membership using in or not
in if we want to iterate through the
items in a sequence we can say for item
in X an item can be any variable name
you want it can be for number in X or
whatever you like here I just use the
variable name item print item if you
want both the index and the item here we
have a list with 7 8 and 3 in it we say
index comma item in enumerate X the
numerator is going to return both an
index and an item so actually again
these variable names are arbitrary the
first one is going to be the index the
second one is going to be the item
itself so you can name them whatever
variable name you like but you can get
both the index and the item using the
enumerate function and then we have
access to both the index in the item as
you can see the results if you want to
get the count or the number of items in
a sequence you can just use the Len
function so in a string example we have
bug we get Len of X 3 this list we have
three items in the list so we print lin
of y we get three and our tuple the Len
of Z is four to find the minimum item
Python checks is lexicographically which
means the smallest on the ASCII scale so
you can use the minimum function on
either alpha or numeric types but you
cannot mix alpha and numeric types into
a list or a temple you'll get an error
so here on our string example we print
the min of X we get the smallest letter
which is B and in the list we print the
minimum of Y which is cow because it
basically is going to compare the first
letter first and see it comes first
alphabetically and the same with the
tupple we print the one that comes first
alphabetically in that's Craig so that's
the min
the maximum item in a sequence again
lexicographically and it can be done
alpha or numerically but not both
so it's bug the maximum is you and with
pig cow and horse we see that pig
actually comes last alphabetically and
in our couple example in is the last
letter alphabetically we can find the
sum of items in a sequence they have to
be numeric so if you mix in other items
that are non numeric let's say strings
or something it's going to give you an
error so in the case of a string we
throw a string in here and we find that
we print sum you're just going to get an
error but if we have a list of numbers
and we print the sum of that list you
can see we get 27 you can also do
slicing you can combine slicing to get a
sum of part of the list so if here we
want to just get the last two numbers 8
and 12 we can do negative 2 onward and
that gives us 20 because we adding 8 and
12 only and for the tupple we have
another tuples e with 4 items in it and
we add those together we get 80 sorting
returns a new list of items in sorted
order but it returns it as a list so
here we have a string bug we print the
the sorted version of X and what we get
back is the letters basically separated
and sorted as a list elements of a list
our list example it's Caesar these are
strings it puts them in sorted order and
it returns to the list in sorted order
and it's important to understand this
does not change the original list the
sorted function is not an in-place sort
it returns a new list with a sort result
in our example we have four names here
and we put those in sorted order and get
Craig Jenny Kevin and Nicholas
so let's say you don't want to sort by
the first letter that you want to sort
instead by the second letter well you
can use a lambda function to do that I'm
not going to cover lambda functions in
detail in this video but I want to make
you aware that you can sort stuff either
by reverse order or using some other
parameter and we do that using key
equals some lambda function and here we
for each item K you can again you can
use as an arbitrary variable name k
we're gonna take the one item which is
the second letter so here it's going to
be e i e and r and we're going to put
those in sorted order based on the
second letter and we can see those with
the second letter in sorted order if we
want to get the count of items in a
sequence we can use the count function
and here we're going to we have the word
hippo in a string we're going to count
the number of times the letter P appears
in hippo and we can see that the result
is two here I added a word cow to the
list twice so if we get the count of the
word cow we see that that also is two
and here we just get the word count of
Kevin in this list and we can see that
is one and we can get the index of an
item by passing in that item and asking
for the index of it and what it's going
to give us is the index of the first
occurrence of the item so in the case of
hippo if we're looking for P it's going
to give us let's see H is zero I is one
the first P is two so we can see the
result we get is two it stops looking
after it finds the first item that
matches in the sequence and our list
example we have cow we have two cows in
here and we're going to get the index of
cow and we're going to get one as a
return value and then for the tuple we
get the index of Jenny and we can see
that's 0 1 2 so unpacking of items in a
sequence and we can unpack those into a
number of variables it's important that
our number of variables exactly matches
the length of that list or string
because we're if not we're going to get
an error so here we have a list x equals
cow and horse and if we won't unpack
those and assign each of these values to
its own variable we can say a comma B
comma C equals x and then that's
basically going to put these in order
assigning them to a b and c so when we
print out a b and c now these are each
separate variables pig cow and horse so
that's called unpacking in the next
lecture we'll learn more detailed
features of lists tuples sets and
dictionaries so now let's dig into some
of the specifics of lists tuples sets
and dictionaries again as a recap lists
are the most general-purpose data
structure in python you're going to use
these for almost everything in Python I
should say a lot of stuff and this can
grow and shrink in size as needed so you
can continue adding items to them or
deleting items from them and the size of
the list will shrink accordingly
automatically python does that for you
and this is our a sequence type so all
of the sequence functions that we
covered above are all useful for lists
and they're also sortable a lot of data
structures are not sortable lists are
that makes them useful for sorting data
so let's look at some of the
Constructors for lists how do we create
a new list so there are few different
ways of doing this one we can create an
empty list by just saying x equals list
and in parentheses that calls the list
constructor with no no parameters and it
gives us a new empty list and another
way to do it is this is probably the
most common way is to pass in the items
we want in that list inside square
brackets these square brackets we can
separate each item with a comma we can
pass in here we have multiple different
data types we have strings we have
integers and in floating point values
all in the same list and that's one nice
thing about the versatility of lists you
can see here we can also create a tuple
which will cover tupple constructors in
a minute but as we create a new tuple
and we can pass that tupple in to the
list constructor just by putting it
inside the parentheses in the list
constructor and that will create a new
list and Pat and assign it to Z
and lastly we can use list
comprehensions I'm going to have another
section on list comprehensions in a few
minutes so I just wanted to give you a
little teaser of what you can do with
list comprehensions to create new lists
with sets of values so here we're going
to create a new list called a and we put
square brackets and basically inside of
that is a for loop in the range function
so we can say m4m in range 8 that's
going to count from 0 to 7 and for each
value M it's going to assign M to the
list so we here we get a new list with
value 0 through 7 in it and then if we
want to do something more fancy here's
just a taste of it I in range 10 so
we're going to count 0 through 9 and
we're only going to take the ones that
are greater than 4 if I is greater than
4 then it'll pass I squared into the
list so here we get 5 through 9 squared
into this new list so that's a taste of
what you can do with list comprehensions
to create a new list using a for loop
and the range function you can also add
if to filter items and you can do
whatever you want to the items that
you're iterating now let's take a look
at the delete function if we want to
delete a single item from a list or
we're going to delete the entire list we
can do that using del here we have a
list called X and we have 5 3 8 6 in it
and if we want to delete the one thigh
tum' which is the 3 and we can just pass
in the one in the square brackets the
index of the item del x of 1 that
deletes the one time 2 3 and we can see
the new list there and if we want to
delete the entire list we just say del X
next the append function if we want to
add an item on to the list this is going
to add it to the tail end of the list we
create a new list 5 3 8 6 when we do X
dot append and then we pass in that 7 is
an argument then we can append 7 to the
tail of the list extend basically is
similar to the plus function that we
used up
we're basically combining two separate
lists into one list so here we have x
equals 5 3 8 6 y equals 12 13 and we can
extend x with y and then we print out
the new x and you can see we have all 6
items in it we could also have used the
plus for that so insert we can insert an
item at a given index in the list here
we have the same list we used above and
we insert at the one position the item 7
so here we can see the result is 5 7 3 8
6 this is the position or the index we
want to insert it at and this is the
item we want to insert and then we can
see here that you can not only insert an
integer or a floating point value you
can Sir tale' issed
into a list as an item we have a list
here with a and M min as two items and
then we print out the revised list and
we see that the second item are the 1
thight 'm in the list is another list
with a and M in it so that's the insert
function let's take a look at pop pop
basically pops off the last item from
the list and it returns that item so you
can use that item if you want to you
don't have to but you are basically
shrinking your list by one item so here
we have 5 3 8 6 as we pop off one item
we're using X dot pop that pops off the
last item is 6 we didn't assign it to
anything or do anything with it but we
can see the new list is just 5 3 8 here
we print X dot pop and it pops off the 8
the last item on the list now and we
print that so we can see the the return
value is 8 when we do X dot Pop remove
we can remove the first instance of an
item so if there are multiple instances
of an item Python is going to start
searching at the beginning of the list
until it finds that item that matches
it's going to stop searching is going to
remove that item so here we have
multiple threes in this list we're just
going to remove the very first one so if
we do X don't remove 3 we can see the
revised list is without the first 3
reverse function can reverse the order
of a list
it's an in-place reverse which means
that it changes the original list the
original list is no longer the same as
it was so here we have an original list
of x equals 5 3 8 6 and then we apply
reverse to it it's not putting these in
sorted order
it's simply reversing the order of the
items so we get 6 8 3 5 as the reversed
list and then we can apply the sort
function to it which is also an in-place
sort you should note that we can use
sorted of AX
these are Python functions sort there
are two different ones and you're a
little bit confusing here sort is an
in-place sort sorted returns a new list
so it's not an in-place sort so here
using the X dot sort function we don't
pass anything in as a parameter to the
sort function we're applying the sort
function to the X which is what's
calling the sort function and we can see
that we put these items in sorted order
and then if you want to do a reverse
sort we can pass into the sort function
a parameter called reverse equals true
and that will give you a descending sort
so we get 8 6 5 3 if we try and use
reverse equals true and again this is
the same parameter that you would use in
the sorted function if you wanted to
reverse sort using sorted function but
this one is an in-place sort as you can
see Python lists are really powerful
data structure and they have a lot of
built-in functions and features but
unless you want to become the Carpenter
who tries to turn every problem into a
nail by pounding on it with a hammer
let's continue on in the course and
learn other data structures and see what
they can be used for so let's take a
closer look at tuples just to recap we
said that tuples are immutable that
means they can't be changed and you
can't add items to the tupple once it's
created they are useful for fixed data
if you're gonna have a lot of changes to
your data then you should use lists they
are useful for fixed data they're much
faster for finding items than a list is
and these are sequence types which means
that all of the above functions are
still going to work so you can use all
those sequence functions that we've used
above on tuples so let's take a look at
some of the Constructors for tuples how
do we create a new tuple there are a few
different ways of doing this
the tupple uses the parentheses as its
constructor so here we can create an
empty new tuple using x equals
parentheses empty parentheses or if we
want to pass in items 1 2 3 the
parentheses are actually optional so
even when you take the parentheses away
1 2 3 separated by commas Python notices
this is a tupple now if you want a
couple of just one item you still have
to put the comma that comma tells python
that this is a one item tuple and not
just an integer and then you can see
that we print here X and the type of X
and we get a couple with just the two in
it and the class is a tupple now let's
create list one equals two four six this
is a list with three items in it we pass
that list into the tupple constructor
and it creates a tuple called X so here
we print out X which is that tupple two
four six you can now see that it doesn't
have square brackets it has the
parentheses around it because it's at up
all and we print out the type of X and
it's a class couple so there are several
different ways there to create tuples
tuples again are immutable however this
may be a little confusing so pay
attention member objects may be mutable
if you have a list as one of the items
inside a couple you can't make changes
to that list you can add or delete items
from that list you can change the items
in the list so let's take a look at what
we mean here if we have a couple with
one two three in it
and then we try to delete the one theit
'im which is the two that's going to
fail that's going to give us an error in
Python if we try to change the value of
the two to eight that also fails we
cannot change the value of the two so it
looks like the tupple is totally
immutable and unchangeable and we get
one two three so even if you try those
you're just going to get an error but
look at this if we assign a list a two
item list as the zeroeth item in this
tuple well that list we can we can just
mutable so we can change or drop items
off of this list if we want so here
we're going to pass in two indices the
zero tells python that yeah we want the
zeroeth item of tuple Y which is this
list with one and two in it and in that
list we want the one thight 'm which is
the two and that's what we're going to
delete so we're basically deleting this
two from this list and then we're going
to print out y and we can see that the
result is we get a single item list with
the 1 and a 3 so we were able to edit
this list with the one and two we're
able to drop items off of that list and
then if also if we want to add items to
the tempo we cannot just add or append
however we can use this concatenation
function where we do y plus equals an
additional temple and it will it will
merge the two tuples into one so here
again you need the comma to tell python
that this is a tupple and not just an
integer it's a one item tuple so if we
do y plus equals four we can see that
the four is added on to our original
type of y so concatenating will work now
let's look at sets set store non
duplicate items so unique items are
really what sets are ideal for you get
very fast access compared to lists and
the reason why is when you iterate
through a list looking for an item the
only way to do it is to start at the
beginning and look at every single item
and do a
comparison so if you have a billion
items in that list you're going to do a
bill you may have to do a billion
comparisons to find that item but in a
set it hashes that item so it can find
it instantly using the hash it has much
faster access than lists so especially
for very large data sets it has much
faster access to items than lists it's
great for checking membership the set is
also great for doing math set operations
things like Union and intersection and
keep in mind that sets are unordered
which means you cannot sort a set so
let's take a look at the Constructors
for a set there are a few different ways
to create a new set we can use these
curly braces and you'll see here as we
pass in 3535 we've got some duplicates
there
what python does is it filters out the
dupes and gives us a set with just three
and five in it and if we create a new
empty set we can just use the set
constructor with parentheses and then we
print out y you can see we get an empty
set if we want we can also pass in a
list here we have two three four and we
call the set constructor using the
parentheses and our pass in our set is a
parameter and we're getting a new set Z
and then we print that out we get two
three four as a set so that's a few
different ways to create sets some of
the set operations you can use you can
add an item to a set by using X dot add
so here we add a seven to this list of
three eight five and then we remove a
three using X dot remove so you can see
the result here is that after you add
the seven you get the four item list and
when you delete the three you get back
down to eight five and seven so add and
remove both work for sets and then if
you want to get the length of a set you
just use Lin checking membership we use
in or not in so if we want to check if
five is in the set we just do five in X
or five not in X and that's going to
give us a boolean return here we can see
we got true for five and X
and then we can also pop a random item
bear in mind the set is not ordered so
we don't know which item we're gonna get
we're gonna get a random item off the
set and then here it actually the pop
function returns the item itself and so
we're printing out that item and the new
list X so here we can see the item it
gave us is 8 and the new set is 5 and 7
and then if we want to delete all the
items from the set and get our empty set
back we can do X clear let's look at
some of the mathematical set functions
so we said that we can do intersection
and union which are and and or functions
so the intersection is done using an
ampersand with two sets and the union is
done using the pipe or bar so a set one
pipe set to symmetric difference or
exclusive or in other words and items
that are in set one but not in set two
or in set two but not in set one and
they a difference we can just use a
subtraction so set one - set - because
it's the difference between those two
and then we can check if one set is a
subset or fully contained and the other
set using the less than or equal to or
greater than or equal to super first
superset so we have two different sets
here set one and set two and when we do
the intersection we can see that the
intersection is three they both have
this value three when we do the Union we
get all the items that are in either set
so 1 2 3 4 5 so when we do exclusive or
using the up caret we get 1 2 4 5 which
is all the items that are in one set or
the other but not in both and then - we
get 1 & 2 and then since neither set is
a subset of the other set both of these
to return false so those are some of the
mathematical set operations you can do
on sets now let's take a look at
dictionaries so first to recap on
dictionaries dictionaries are key value
pairs
so most programming languages have some
equivalent of the Python dictionary they
don't always call it that some of them
call it a hashmap
Java calls it a hashmap dictionaries are
unordered this means they cannot be
sorted they can be converted to a list
and then sorted as a list
but it cannot be sorted as a dictionary
so some of the functions that we can do
how do we create new dictionaries let's
take a look at our constructors so if we
create a new dictionary using the curly
braces then we need to pass in members
key value pairs separated by a colon and
then spaced out with commas okay so here
we have three key value pairs the key is
on the Left colon and then the value and
these are three different ways of
creating exactly the same dictionary so
in the second example we pass in a list
of tuples
so the tuple contains two items it has
the string and separated by a comma that
floating point so there are three tuples
in the list passed into the dictionary
constructor which is in parentheses and
then the third one passes into the
dictionary constructor notice search
there are no quotation marks around the
strings here we just have pork equals 25
point 3 in Python knows that this is a
string so these are three different ways
to create dictionaries in Python they
all do exactly the same thing some of
the operations of dictionaries now we
notice that shrimp is not in our
dictionary so if we want to add shrimp
we can say X of shrimp equals 38.2 this
in this case there is no shrimp in the
dictionary add so it's going to add a
new key value pair for shrimp 38.2 if
there already was a shrimp in the
dictionary then it would update the
value to 38.2 for shrimp it looks up
this key and it will update the value
for it so this is add or update and
python is not going to tell you if that
was in there or not if you if you want
to check you can check first right if
shrimp
dictionary but if you just do this X of
shrimp equals 38.2 it's going to
overwrite anything that was already in
the dictionary for shrimp if you want to
delete an item this is just del X of
shrimp is going to delete shrimp for
them a dictionary and then you can see
that we print out the new dictionary
there's no shrimp in it and if we want
to get the length of the dictionary you
can print Lin of X they'll tell you how
many key value pairs are in the
dictionary and if you want delete all
the items from dictionary you can use X
dot clear and lastly to delete the
entire dictionary and free up the memory
that it's using you can use del X so to
access keys and values in the dictionary
you can access these separately or you
can access them together so here are a
few different ways of doing that we have
this dictionary Y with pork beef and
chicken in it those are the keys the
strings pork beef and chicken so if we
do y dot keys we get a list of pork beef
and chicken it dumps these out as a list
if we do wideout values it dumps these
out as a list the values those 14-point
values and if we do items we can say
print Y dot items it's going to print
out all the key value pairs so here at
Princeton amount is a list of tuples or
key value pairs to check membership in
just the keys you don't have to specify
keys you can if you want you can say
beef in Y dot keys or you can just
simply say beef in Y and that's gonna
check in wise keys only it's not going
to check in to values if you want to
check for membership only in the values
you can check clams in Y dot values and
all these membership tests are going to
have a boolean return true or false so
to iterate a dictionary keep in mind
that these items are in random order and
you're not going to be able to iterate
them in any kind of sorted order it's
going to python is going to give them
back to you in whatever order at once so
for key in Y print key
that will give you all the keys in the
dictionary one at a time and then you
can get the value by saying why of key
so here you can see we printed out each
key and its value if we want to iterate
with a separate variable for both the
key and the value sometimes this is
helpful if you're doing a lot of
operations inside the loop you can put
whatever variables you want
I used K comma V as my variable names
and what you do is you iterate Y dot
items and then items returns at up all a
to item couple of the key and the value
and then it assigns them to whatever
variable names you have here so K and V
in my case so you can see the result
here is the same we iterate through the
items we print out both the key and the
value so that wraps up this video on
built-in Python data structures now you
should have a pretty good understanding
of how to use pythons built-in data
structures strings lists tuples sets and
dictionaries make sure you download the
code and get some practice using it
because it's hands-on practice is going
to make you a good programmer in the
next section we'll learn how to use list
comprehensions to create new lists hi
I'm Joe this chapter we're going to
cover a pretty cool feature of python
called list comprehensions that enables
you to create new lists of values using
a comprehension are basically sort of a
for loop and iteration inside of a list
creator so our basic format is transform
sequence and filter so we can apply a
filter to it if we want and we put that
inside square brackets and that's going
to the result is going to be assigned to
a new list so we're going to use the
random module a little bit in this don't
need that for all this comprehension
before it to my examples so I'm going to
import that so we have a series of about
10 examples or something I'll show you
and get increasingly more complex so
here we're going to just get values
within a range typically in list
comprehensions or anything is the range
function
here we just use range of 10 and you
know the range function returns a
sequence of numbers in this case it
starts with 0 which is a default and it
goes up through 9 because the 10 is non
inclusive so 0 through 9 and what we're
going to add to this new list is X for X
in that range so in this part the first
X we could apply some sort of a
transform or a function on that X if we
wanted to x squared to X whatever we
want and then this is where we declare
the variable each X in this range so the
result is a series of values under 10 so
0 through 9 under 10 integers okay so
that's the simplest example of a list
comprehension now let's look at some of
the other more crazy stuff that you can
do with list comprehensions we could get
all the squares if we want I told you we
can we could apply a transformation to
the X if we want so here we declare our
variable is X as we iterate through
under 10 which is this list we just
created okay so we don't necessarily
have to use the range function we can
use any sequence here which means we
could use a list we could use a couple
set or even a string or a range function
so x squared for X in under 10 so it's
going to iterate through these it's
going to return the square of each one
of them and it's going to assign that to
this new list called squares and then
we're going to print out squares so you
can see the result is 0 through 81 the
squares of the previous list ok let's
see what else we can do
get odd numbers using mod ok so odds
equals x for X in range 10 so here we're
going to just basically iterate through
0 through 9 the variable we're going to
use is called X and we're gonna send X
to this odds list but here look we apply
a test a condition if X mod 2 is
2:1 in other words if it's odd if X is
odd then we'll send it to this odds list
when we print it out we see that we get
one three five seven and nine now let's
get them multiples of ten so we're going
to use the arrange function again as our
sequence zero through nine and instead
of adding X to the list we're gonna add
x times ten so this is not a whole lot
different from me x squared we did we
get two multiples of ten so zero through
nine D now let's get all the numbers
from a string so we start out with a
string named s that has a combination of
letters and numbers in it maybe
sometimes you want to filter out and
delete all the numbers or whatever but
here what we're gonna do is just create
a new list with all those numbers so
nums
equals x for X in s in other words we're
going to iterate through the letters or
characters in s and we're going to test
if each one is numeric and if it is then
we're gonna add it to this list and then
when we print out the list
we're basically we get a list so I'm
gonna use this little join function to
join the numbers into a single single
string so we get 207 3 in other words we
managed to grab all the integers in this
string so here we're going to get the
index of a list item and we're going to
do that by using the enumerate function
so we iterate using enumerate names name
this is a list the names is a list and
we're going to numerator
the enumerate returns both a key and a
value for each item in the list so we
start out with Cosmo and 0 and then we
get Pedro and one on you and - right so
we're eating each name we're getting the
key and the value our test is if the
value is equal to Anya okay so that
means here then the key is going to be
equal to two and then what do we add to
the list well we add K we add K we add
the key we had to so at the end result
here we get a list with just a two in it
because that's the only one that passes
this test and then when we print out the
zeroeth item in the list of course it's
a twos it's a one item list and we can
also delete an item from a list here we
have a list of letters actually a string
we start by iterating through the string
ABCDE F converting it to a list of
letters just by adding each letter in
the string to a list so now we have a
list of ABCDE F as individual letters we
shuffle those using this random function
so now we have shuffled letters ABCDE F
and each one of them is basically a
string object in the letters list so
we're going to create a new list that
passes this test a for a in letters if a
is not C right in other words every
letter in this list except for uppercase
C so we're gonna get a B D EF and you
see when we print them out we get DF e a
B but we do not get C so we get yeah
that works pretty cool huh
we basically filtered out the C wherever
it is in the list we don't know but we
filtered it out that wraps up this
lecture on list comprehensions you can
download this code from my github site
and use tests to code and run these
examples and I encourage you to use list
comprehensions these are really a useful
tool in Python for creating lists in
this section we're going to learn how to
use stacks queues and heaps first we'll
cover the fundamentals of each of these
data structures what key operations each
of them has and then how you can
implement them in Python these are three
very useful data structures let's start
by learning about stacks a stack is a
last in first out data structure that's
called LIFO so what that means is that
all the push and pop operations are to
the top of the stack the only effect the
top item on the stack the only way to
access
the bottom items on the stack like in
this diagram item one is to first remove
all of the items above it we have a
couple of different key operations here
push allows us to push an item on to the
top of the stack and we use the pop
command to pop an item off of the top of
a stack some other stack operations are
peak sometimes you might want to get an
item off of the top of the stack without
actually removing it let's say we need
access to the top item we want to know
what it is and we can use the peak
command to see a copy of the top item
without actually removing it from the
stack or clear to remove all the items
from the stack and empty the stack out
there are a lot of different use cases
for stacks one very common use case is
the command stack all computer programs
track each command that you execute and
most programs you use have the option of
undoing the previous command in order to
do that the program has to keep track of
which commands you've executed in which
order so it does that using a stack each
time you execute a command it pushes
that command on to the stack so that has
a record of it and if you click the undo
button it's going to pop the last
command off of the stack and it's going
to reverse that command so the command
stack is used to execute the undo
function in programming now let's take a
look at how stacks can be implemented in
code we have the Python list which makes
a great foundational data structure to
store the stack in and actually Python
gives us most of the functionality that
we need to create a stack with the list
so the underlying data structure beyond
our stack is going to be a Python list
Python gives us the append function
which we can use to push an item onto
the stack and it gives us a pop function
which we can use to remove an item from
the stack we're actually pushing items
onto a list and opting them from a list
so here's one implementation using the
Python
list we can create a new stack my stack
equals an empty list and then we can
push items onto the stack using a pin is
here we pushed for 7 12 and 19 onto the
stack and then when we print out the
stack we can see four items now a little
more test coat here when we pop an item
off of the stack we can see that we get
to 19 first and we pop the second item
off we get to 12 so it's popping off the
last item first which is exactly what we
want
so that's typical stack operation
however it's using a Python list now if
we wanted to write a wrapper class so
that we can add some additional
functionality to our stack that's
actually not that hard so let's take a
look at how that can be done here's a
stack using a list as the underlying
data structure but using a wrapper class
so that we can rename our functions as
we like and we can also add additional
functions and features to our stack so
we'll start with a constructor an init
function and this basically just has a
new list it creates an empty list just
as we did before the push is going to
add an item so we receive an item and we
just use the append function to add that
item on to the list what the user is
going to see is he's pushing an item on
the stack but what we're doing behind
the scenes is appending that item to a
list next the pop function first we want
to check if the list actually has items
on the list if the list is empty we
don't want to try a pop operation if
there's at least one item on the list
then we'll pop that item off and return
it
the peek function allows us to just look
at the top item on the list and return
that item but without taking it off so
here we return the top item on the list
but without removing it and lastly if
someone wants to print out the stack or
show all the items that are on the stack
what we're going to do is just show the
string representation of the list now
let's look at some tests
see how our stack works my stack equals
stack and then we can push an item will
push a1 will push a3 and then when we
print out the stack we can see that yeah
we have a1 and a3 on our stack and when
we pop on an item off of the stack we
get the three which was the last item
that we put on the stack when we peak we
get the one which is the only item
actually left on the stack but as
peeking is going to give us the top item
on the stack if we pop another item we
get one and now the stack is empty so if
we try to pop another item we get none
so basically all those key features of
our staff are all working just fine so
this is how we can use a wrapper class
to implement a stack in Python with an
underlying data structure of the Python
list so the Python list is a very
versatile data structure and here we've
used it to create a stack now let's take
a look at queues queue is a FIFO or
first in first out data structure this
is really intuitive because we see
queues in every walk of life almost in
everything you do on a daily basis you
encounter queues queues have two key
functions you in queue an item by adding
it to the end of the line udq an item
means removing it from the front of the
line
so some use cases for queues just about
everything you wait in line for so bank
tellers placing an order at McDonald's
or your favorite restaurant
DMV customer service supermarket
checkout pretty much anything that has a
line is what a queue is and it's
important to be able to model that in a
computer program so the queue data
structure allows us to do that now let's
take a look at how we can implement a
queue in Python it's actually pretty
simple because python already provides
us a built-in library called the deck or
de quue that's a double-ended queue that
allows you to add and remove items from
both ends of the queue for our simple
queue we don't really need that function
now
we just want to be able to add items to
one end of the queue and pop them off of
the other so we can use the append
function to add items or push items on
to our queue and we can use pop left to
remove items or pop items off of the
cube you can see the full documentation
in Python here if you want to learn more
about how double into queues work so for
basically just using double ended queue
in python as a single ended queue we can
use from collections import deck that's
going to import our double ended queue
library and then we'll create a new
queue my queue and that's going to be a
double ended queue object and then we
can append items or push items using the
append function so we can push a 5 and
we can push a tin on to the queue and
then when we print out the queue we see
that we have a double ended queue with a
5 and a 10 on it and then if we want to
pop items off of the queue we use pop
left and here we get to 5 that pops an
item off the tail end of the queue or
the left end of the queue so it's pretty
easy to implement a queue in Python this
is obviously a common enough data
structure that Python built in a library
for it now as a fun exercise for you you
may try writing a wrapper class for the
double-ended queue to make a
single-ended queue using push and pop as
we did similar for the stack in this
lecture we're going to learn how to use
max heaps now implementation wise the
underlying data structure is going to be
a list and it's the functions of a max
heap are not a whole lot different from
stack and queue so I think you're going
to be able to pick this up fairly easily
now when you look at this graphical
representation of a max heap though it
looks a lot like a tree and I know we
haven't covered trees yet that's going
to be covered in section 5 but bear with
me I think you're going to figure this
out pretty easily so the one condition
of a max heap is that every node is less
than or equal to
it's parent that's the key so you'll see
that 25 is the parent of 16 and 24 right
25 has a left child and a right child
and it's greater than or equal to both
of those and then 16 is greater than or
equal to both of its left and right
children and so on so every node in the
tree has to be less than or equal to its
parent and every parent node has to be
greater than or equal to be the nodes
below it so that is the core condition
of a max-heap and the reason it's like
this is so that we can instantly remove
this max number anytime we want anytime
we want to pop the top number off of the
heap we know that it's the highest
number in that heap so the highest
number always rises to the top of the
heap and it can be instantly removed and
used so max heaps are fast if you're
familiar with Big O notation you can
insert or add an item to a max heap in
Big O of log n time which is extremely
fast and you can get an item you can get
the max item off the top of the heap and
Big O of one time which is pretty much
instantaneous you can remove the max or
pop in Big O of log in time so the
response time for a max heap is
extremely fast and that's why we use max
heaps for some things if you need to pop
this the maximum number off a heap you
can get very quickly
max heaps are easy to implement in
Python using a list not as easy as the
other two data structures we just
covered but not too hard so I think
you'll be able to follow this but I'll
warn you the code is a little bit longer
and hairier than the previous two
examples that we just covered but I've
already written all the code all you
have to do is just follow along with the
explanation so you can see that using a
list we open index the correspond to
list index it corresponds to each node
starting with one at the top and then
2/3 across 4 5 6 7 across on the next
tier and then on the next tier 8 9 10 so
it's a pretty easy indexing system that
corresponds to these nodes under the
tree
[Music]
and then when you look at our our list
how we put the items into the list well
look 25 is an index 1 and then 16 and 24
so look we know that 16 is not greater
than 24 but it looks like wow it's lower
than note 3 here or index 3 why is that
well because our rule is that 16 has to
be greater than everything below it on
the tree which it is so our condition is
met this is a max-heap
16 does not have to be greater than 24
we didn't say greater than everything
behind it on the list no no on the tree
so that this is a valid max-heap okay
and that is how it is implemented in the
list using these list indices so we can
instantly access any node in the tree or
any node in the max heap now let's say
we wanted to access the 5 we know that
the index is 4 this is it index number 4
for this this 5 node now we can also
access 5s parent which is the 16 we
simply divide the index by 2 so this 4
divided by 2 gives us the index of 5s
parent node which is 16 and if we want
to access 5 children it's the same thing
5s left child is times 2 to get the
index of 5 left child 8 and then times 2
plus 1 gives us the index of 5s right
child 8 9 so if we're taking take a
given node at index 4 we can access his
right and left child by x 2 and x 2 plus
1 and we can access force parent by just
divided by 2 so it's pretty quick easy
operations to access the parent and
children node in this tree
no max heap operations like I said these
are exactly the same operations that we
just covered for stacks and queues so we
want to be able to insert or push an
item onto the heap we want to be able to
peek find out what is the
item on the heap without popping it off
and then we want to be able to remove an
item from the heap and return it which
is a pop operation so the same three
operations for heaps as we had for the
previous two data structures let's look
at how those work so push we can add a
value to the end of the array and then
we float it up to its proper position so
let's look at an example we want to push
a 12 onto this heap what we're going to
do is put it at the very last spot in
the array which is here right and we
have a spot for it so in other words
it's gonna be 11 right child it's the
last index in the array and then we need
to float it up to its proper position
well how do we do that we need to
compare 12 to 11 if 12 is greater than
these two we'll swap places yeah it is
greater so we want the 12 and 11 to swap
places now we need to compare 12 to its
its new parent 16 is 12 greater than 16
no it's not so there's no more swapping
12 is already floated up to its proper
position in the heap so this is one of
the key behind-the-scenes functions that
we have to code which is called float up
or bubble up when we add an item to the
bottom of the tree we need to be able to
bubble it up to its correct position in
the heap by comparing it to its parent
nodes and in swapping so we use that
every time we do a push operation peek
just returns the value at the top of the
heap okay which is going to be heap of
number one index number one and that's
pretty straightforward we don't really
need to pop it off or anything's we just
get that item and return it and then pop
first we're going to move this topmost
item we want to pop off the max which we
know is in index position one first
we're going to swap it with the item in
the last position then we're going to
delete it from the heap and then we're
going to bubble down the item here to
its proper position so let's take a look
at the example so 11 is in the last
position
25 is the item we want to pop so we're
going to swap those two 25 and 11 swap
places now we can remove 25 from the
heap without affecting the rest of the
heap it's in the last place it doesn't
affect anything else in the heap our
next step is to bubble that 11 down to
its correct position so we compare 11 to
24 11 is less than 24 so it needs to
move down next we're going to compare 11
to 19 and 11 is less than 19 so that's
gonna swap places so we do some
comparisons with the child nodes to move
11 down until there's either no further
room to go down or it's not greater than
any of its children nodes so that's the
operation for pop and now we can just
return to 25 that we pulled off that's
it so those are the three key operations
and that's basically how they work in a
nutshell now let's take a look at the
code again the underlying data structure
we're using is a list so you're gonna
see us using list indices throughout
this program now the public functions we
have here are push peek and pop for
pretty familiar with those by this point
but we also have supporting private
functions that we need for this heap and
we have a basically swap a float up in a
bubble down and we use those about
internal utility functions these are not
part of the user interface and then the
string function is so that we can print
a heap so our constructor when we create
a new heap we have the option of passing
in a list of items that we want to add
to the heap if we don't pass in a list
of items and we'll get back an empty
heap with just a 0 in it so we put a 0
in the very first element because we
don't use that we start our elements at
index number 1 for the max heap if we
pass in this list of items we're
basically going to iterate through those
add them one at a time to the end of the
list and then float it up to its proper
position that's the push operation so
essentially we're pushing them all one
at a time and when you look at the push
method it does exactly the same thing
it appends the data that you passed in
to the end of the heap and then it
floats it up to its proper position in
the heap so that is the push operation
which is almost identical to the
constructor if you pass in items now the
peak operation doesn't do much it only
returns the top item on the heap that's
all
it doesn't take it off there's no pop
operation going on it's just a peak now
let's look at the pop operation there
are a few different cases here depending
on how many items we have in the list if
the list has exactly two items one of
those is the zero that we're not
counting we're not using that as part of
our or max heap so if there are exactly
two items that means there's really just
one item in our max heap we'll pop off
that number one item with index number
one and we'll return it we set past that
into a variable Max and then here at the
end here we return max if there are more
than two items then we're going to swap
the maximum item which is in position
index 1 with the last item so we get the
last item in the list we swap those two
we pop off the last item and assign it
to this variable Max and then we bubble
down the first item that we moved into
the top position so it's exactly what we
just walked through in this slides and
then at the end we return to max so
that's how the pop operation works then
in our utility functions here swap
really just swaps two different items we
pass in two indices we swap those two
items in the in the list now the float
up function is going to receive an index
of the item that we want to float up
probably the very bottom item in the
list initially first we'll get the index
of its parent if it's already in the top
position then there's no floating up to
do it's already risen to the top
otherwise we're going to compare it to
its parent and if it's greater than its
parent then those two need to swap
places
so I'll swap the positions of the item
at index passed in with its parent then
we'll call the float up function
forcibly on the parent so this will
continue to float up function until the
element reaches its proper position
bubble down kind of does the opposite it
takes an element that's at the top of
the list and it bubbles it down to its
proper position so you can pass in an
index we get the left child and the
right child by multiplying the index by
2 and times 2 plus 1 and then we'll set
the largest equal to index we do a
little comparison if the item were
bubbling down is less than its left
child then we're going to swap positions
with the left one if the item we're
bubbling down is less than the right
child then we're going to swap positions
with the right child so if there's any
swapping to be done at the very end here
we check do we need to swap if so we'll
call this swap function on the item
we're bubbling the target item with the
larger of those two and then we'll
recursively call the bubble down
function again on the same item that we
just bubbled until it reaches its proper
position and our test code here we don't
have a whole lot of test code we create
a new max-heap with three items in it
obviously the 95 is the highest one and
2221 is the second highest we push a 10
on and then we can see that our list now
has ignore the zero really has four
items in it and when we pop one off we
get it of course the 95 and when we peek
at the next item none - 95 is gone we
can see that the 21 is the next item in
the max heap that is how a max-heap
works and that's how you can implement
it in Python and by simply changing a
few greater than or less than signs you
could change this to a min heap let's
say you have a collection of items that
you want to store and you want to be
able to iterate through them so you
wouldn't be able to find an item in the
list you wouldn't be able to insert an
item but you need very fast and
searching speed especially at the front
of the list you want
to insert new items at the front you
need to be able to remove items from the
list you also may want to iterate
forward and backward through the list or
possibly even in a continuous circle
through the list so one possible storage
solution for these requirements is a
linked list we're going to learn how to
use linked lists and what they are and
we're going to learn a few different
types of linked lists a standard linked
list a bi-directional or doubly linked
list and also a circular linked list
we'll learn how those work the major
operations used for with linked lists
and we're also going to go through of
course how to code a linked list in
Python so let's take a look at how
linked lists work every linked list is
going to be composed of what we'll call
nodes you can call it whatever you want
in this video we're just going to call
each item in a linked list a node you
could store whatever data you want in
the linked list it could be a student
node it could be an employee node
whatever it doesn't matter but we're
gonna call our node and that's kind of a
common nomenclature for the items in the
linked list just call them nodes and
each node is connected to the next node
so it has a pointer to the next node so
those two things it has a piece of data
which for us is just going to be an
integer in this video and it has a
pointer to the next node so those are
the two key components of every node in
the linked list now a linked list looks
something like this each node has its
own piece of data and it also has a
pointer to the next node there can be
any number of nodes it's basically
unlimited only by the amount of memory
you have in your system and the very
last node here you'll see there's no
next pointer so we're going to store
like a nun there to indicate that
there's no next node that's the last
node in the list at the very front we
call that the root node that's the first
node in the list so we need a pointer to
point to the starting point for the list
and this is what we call the root so we
have a pointer to the root and the
operations that we need for each linked
list we need to be able to find data we
need to be able to add a piece of data
we need to be able to remove a piece of
data from the linked list and we need to
be able to print the list
so we're gonna see how each of these
operations works and then we're gonna
see how it held a code it in Python
now the attributes for a linked list you
have a pointer to that root node and
then we're also going to track the size
of the linked list so it in you given
time you could find out how many nodes
are in the list
let's look at the add operation so
here's our linked list we have a pointer
to the root we want to add tend that's
our command let's add 10 so we're first
are gonna create a new node with that
data 10 in it we don't have anything in
the next pointer yet but what we're
gonna do is we're going to point the
next pointer to where the root is
currently pointing so the root currently
points at this five node we're going to
put our next pointer for this new node
pointing at the root node and then we
change our route to the ten
so we effectively inserted this new 10
node at the very beginning of the linked
list that's how we're going to do the
insert operation next we want to try and
remove a number so let's try and remove
five obviously if we try to remove a
number like 200 and it's not in this
this linked list and we'll get back your
a false or a nun or sorry dude or an
error or something but if we have if we
have a number that's in the list and we
want to try and remove that so we're
going to remove five first we need to
find that five so we start at the root
we check if this is the number no it's
not oh is this the number yes it is geez
so there's the node that we want to
remove pretty easy to remove it we we
take the previous node to this five we
change the previous nodes next pointer
to 5's next pointer in other words see
five the next node is 17 so we just
changed five s previous node which in
this case is the root the ten we change
that next pointer to where five next
pointer goes and so now effectively the
five node is just completely cut out of
the linked list when we iterate through
the linked list starting from the root
we're going to follow this path and
we're never even going to know that the
five is there the five note still exists
but we don't have access to it anymore
it's effectively deleted from the
list so that's the remove operation now
let's take a look at how to code a
linked list in Python we're going to
start with a node class we're going to
use the same node class for three
different types of linked lists that we
cover in this section so W linked lists
and circular linked lists are going to
use the same node class you'll see in
the node class here that we have three
attributes we have a piece of data we
have a next node and we have a previous
node now in our standard linked list we
do not need the previous node so we're
just not going to use that attribute in
the standard linked list but it'll be
there for us so that we can reuse the
node class for the other two linked
lists and then we also have this string
representation that gives us back
essentially the data in parentheses so
that's what the string representation of
a node is so in the linked list we have
four methods we have an add find remove
and a print list let's see how all those
work first our constructor has two
attributes we keep track of the root
node and we also keep track of size so
each time we're add or remove node we're
going to increment or decrement the size
accordingly to add a new node we pass in
the data that we want to create that new
node with we create a new node with
passing in the data and the next note as
the root node keep in mind we're
inserting this node at the very
beginning of the list so the current
root node is going to be the second node
so we pass that in as the next node for
this new node and then we change the
root node to the new node we increment
our size by one and we're done with the
add operation to find a piece of data we
passing that piece of data we are going
to iterate through the list one note at
a time we're going to start at the root
node which will call this node and as
long as this node is not none as long as
there it's a valid node we're going to
continue to iterate through this list
each time through this while loop this
else statement is
going to bump us forward to the next
node if we haven't found what we're
looking for yet
so what we're looking for is this nodes
data is equal to D and when we find that
we return D if we get through all the
way through the while loop we haven't
found it will return none because that
data is not in the list the remove
function we pass in a piece of data we
need pointers to this node and this
notes previous node so we're going to
start iterating through the lists to do
defined operation at the root which will
call this node and then we're going to
keep track of the previous node because
we need that to be able to remove the
node when we find the one we want to
remove each time through this while loop
we have two pointers now to increment we
have to increment the previous node to
this node and we have to increment this
node to this node next node so if we
haven't found what we're looking for yet
at the end of this while loop we'll bump
forward both of those two pointers and
that's how we iterate through the list
now our check we check if this nodes
data is equal to D that we're a past end
that we're looking for if we find it we
found that data there's two
possibilities for removing that node one
that node is in the root that's this
else here in which case we just changed
the pointer for the root node for our
linked list to this nodes next node in
other words the second node in the list
we bypass the current root and we point
our root pointer to the second node in
the list that effectively deletes the
first node in the list now if it's not
in the root in other words it's in some
other node in the list then we need to
delete that by changing the previous
nodes next node pointer to this nodes
next node so that is the remove
operation if we get all the way through
and we haven't found it we return false
if we do successfully remove it return
true and the print operation we print
the list
we're going to iterate through the list
one note at a time starting from the
root this while loop is going to check
when we reach the end of the list and
then we're going to exit and just print
a none and for each node we're going to
print the string representation of that
node followed by a little arrow so
you'll see what that looks like when we
run the test code in a second so here's
our test code we test a variety of
different operations yeah here's what a
list printed looks like so our string
representation of a node is just the
value in parenthesis and then we put an
arrow between it in our print function
so we'll create a new list called my
list we'll add a few items to it and
then we'll print the list and you can
see what we get here and then we can
print the size of the list we can see
the size is equal to 3 we remove one
item the 8 then you can see the size is
equal to 2 and we can also find the 5
when we find the 5 it actually returns a
5 when we can print that out and we can
also print out the root which is 12
that's the last item we added so that's
at the front of the list so that's how
the linked list works so a circular
linked list is almost identical to a
standard linked list except that from
the very end node instead of having no a
none pointer to the next node it's going
to have a loop back to the very
beginning to the root node the add
operation in circular linked lists works
slightly differently because we have
this loop back to the first node from
the end node we'd rather not have to go
back and update that every time we
insert a new node so we don't insert the
new node as the root node anymore now
instead we're going to insert it as the
second node we leave the root pointer
and the last pointer the loop back to
the root the same and instead we insert
our new node as the roots next node and
then the next node for our new node is
going to be what was the previously the
second node so that's the add operation
for circular linked list so that's
basically yeah that's the only
difference with a circular linked list
so what are the advantages of a circular
link list well it's great for modeling
continuously looping data or objects so
something like a Monopoly board or
in-game board or a racetrack or
something that continuously loops and
there are a lot of different looping
objects in the real world so if you want
to model some continuously looping set
of objects in a computer program a
circular linked list is one way to do
that
the circular link list is very similar
to the linked list with a few
modifications in the add method we have
to check whether a the list is empty and
if it is then we add the first node then
we make its next node point to itself it
sounds crazy but we need to loop back to
something so we loop back to the first
node the root node else if there's
already at least one node in the list we
can create a new node and insert it into
the number two position right after the
root and change the roots next node to
point to this new node so that's how the
add operation works we can see the code
here it's only a few lines of code the
fine method works exactly the same as in
the regular linked list except that in
this Elif statement we have to do a
check if we've circled all the way back
to the root node again because if we
have we have to stop our find and return
false we didn't find it we search the
entire list we didn't find the value
we're looking for we turn false for the
remove method let's scroll down here for
the remove method we need to track both
this node and the previous node so we're
going to set pointers for both of those
to start out so we'll start out at the
root node and we'll set previous node to
none and you can see towards the end of
our while loop here we advance both of
these pointers one node so they move
both move forward to the next node now
we test if we found the data that's this
first if statement
bingo found if we pass this test and if
so there are two possibilities for the
remove function
number one if the previous node is not
none tests whether the data was found in
the root node and if not the remove is
an easy bypass operation for changing
the previous nodes next pointer which is
what we do here and taste number two
else if we need to delete the root we
use this while loop to find the very
last node in the list so that we can
update its next node to point to the new
root because the root has changed so we
find that we find the new we find the
last node we update the last nodes new
next pointer which is the new root and
then we update the root pointer itself
lastly we decrement the size by one and
we return true if we successfully remove
the data and in our print list method we
iterate through the list we print each
node file Bob followed by an arrow you
can see and our while loop has to check
if you've made it back to the root so we
know when to stop so this is the test we
have here while this node next node is
not the root we continue to iterate
through the list now let's take a look
at the circular linked list test code
here we create a certain new circular
linked list we'll just call it CLL we're
going to add a bunch of items to it
using a for loop adding one item at a
time and then we can print the size of
the list we can see down here the result
the size is five we try to find an
eighth if the value is actually in there
it will return eight if we try to find
an item that's not a no list is going to
return false
so we can see when we try to find the 12
we get back a false and instead of using
our print list function here we're going
to iterate through continuously so that
you can see when we pass by we're gonna
print eight items even though they're
only five in the list so we're gonna see
if it actually does circle back to the
next node we're just going to
continuously get the next node up until
we reach eight of them so we can see
five nine eight three seven and then it
starts from the beginning again five
nine eight three it'll continue on we
print up
eight items so that shows you that it's
a continuous loop and we can continue to
loop through that if we want to write a
little more test code we can print the
list and here's the current contents of
the list and then we are removing eight
and when we print out remove fifteen
result we see that it's false because
there's no 15 in the list we can see
that and we print the size of the list
now we have four items because we
removed one we try to remove the five
node that completes successfully and
then we print the list again and we only
have three items left so that wraps up
this lecture on a circular length list
now let's look at doubly linked lists
these are also sometimes called
bi-directional linked lists because they
have arrows pointing both directions to
the next node and to the previous node
so a regular linked list looks like this
a doubly linked list each node has three
pieces of data it has a pointer to the
previous node a pointer to the next node
and the data itself is storing so ask
those three things three components to
the node of a doubly linked list so this
is what a doubly linked list would look
like a simple one with three nodes we
have here four or twenty three and a
seven so let's say we want to delete an
item this is a little more complicated
because we have two pointers to fix not
just one so we found this item that we
want to delete we're going to call that
this node and then the previous node to
this node is the four and the next note
is the seven so how do we delete it well
we look at this pointer from the
previous node that's pointing to this
node and we look at the pointer from the
next node that's pointing to its
previous node right these ones that are
pointing to this node they have to be
fixed they basically just have to bypass
it so what we do is we change fours next
pointer instead of pointing to this it
has to point to this nodes next node and
then for sevens
previous pointer instead of pointing to
sevens previous node it has to point to
this
nodes previous node so we we basically
do two adjustments here pre done next
equals this dot next and next up pre
evils this dot preview changes that we
do to cut this node out of the list and
you see once we get these red arrows in
place once we fix these two pointers
we've effectively cut no.23 out of our
linked list we've deleted it so that's
how the delete operation works in a
doubly linked list some advantages of
the doubly linked list over a standard
linked list you can iterate through the
list in either direction that's pretty
obvious but when you have a really large
linked list and you don't want to
iterate through all of the items because
you happen to know that your item is
towards the end of the list you can
actually save quite a lot of time by
starting your iteration at the tail end
of the list and working right back so
you could save a pointer to the very end
of the list as well and you can delete a
node without iterating through the
entire list that is if you have a
pointer to that node right if you know
where that node is that you want to
delete and you don't have to iterate
through the whole list to find it each
node already stores its previous in next
pointer so you can get the nodes on
either side of this node that we want to
delete without having to iterate through
the entire list if you have a pointer to
the node you want to delete doubly
linked list uses an extra node attribute
called priva as I showed you before when
we looked at the node class and it also
has an extra list attribute called last
you can see here last so that we can
always access the tail end of the list
or the last item in the list now the add
method has to check if the list is empty
and if so then the root node is also the
last node so otherwise it adds a new
node to the beginning and it changes the
roots previa fails two different
conditions here for the add a new node
the find method works exactly the same
as the find method for the standard
linked list so there's really no changes
on that the remove function
it is a little different there are three
possible cases in the remove function so
let's review each one of those case
number one we're trying to delete a
middle node that's this if statement
here so the node is not in either the
root or in the last node that's the
standard case that we showed in two
slides so for this we just do a simple
bypass we bypass the target node and by
changing the previous nodes next pointer
and the next nodes previous pointer
which is exactly what we're doing here
then we've basically bypassed the target
node that we're trying to delete now the
second case is that we're trying to
delete the last node this is just like
case one except that the previous nodes
next pointer will be changed to none
because the second-to-last node is now
the last node so that's the only
difference here so we we're changing the
basically the second-to-last nodes next
pointer to none and the third case is
we're trying to delete the root node and
this is again similar to case one except
that we change the root pointer to point
to the second node in other words we
change root to point two roots next node
and that's it those are the three cases
for remove the rest of the remove
function is really straightforward the
print list method is pretty much the
same there's not no changes there so
let's look at the test code for the
doubly linked list here will create a
doubly linked list dll we'll call it we
add a bunch of items using a for loop to
add each one of those items in we can
see we print the size is 5 and we can
print the entire list if we want using
our print list method and then we can
remove an 8 will print out the size
again we can see the sizes for so these
things all work and then if we try to
remove items that are not in the list
you'll l dot remove 15 that doesn't work
if we try to find an item that's not in
the list we also get false back and if
we add some numbers 21 and 22 and then
we remove a 5 and then we print the list
again we can see that 21 and 22 were
added to the front of the list and the 5
was removed
was a tail node the last node in the
list and we successfully removed that
and then just for fun we see that we can
print out the last nodes previous node
which should be the node right before
the three of the nine which is this
three which is exactly what it does so
we can access nodes from the tail end of
the list also that wraps up this section
on linked lists so in this section we
covered a standard linked list a
circular linked list and a doubly linked
list or a bi-directional linked list we
showed you how those work and then we
implemented them in code and again I
encourage you to download this code and
run it and try it out make some edits to
it change it use your own tests on it
and see how it works by using a code
you're gonna better understand how the
code works how linked lists work and how
to eventually write your a linked list
code hopefully in this lecture we're
going to talk about trees after section
one where we covered pythons built-in
data structures trees is definitely the
next most important section of this
course trees are critically important
data structure in all programming
languages and let me explain why to make
a point I'm thinking of a number between
1 and 8 million can you guess my number
well you guessed 4 million I just say
wrong and you're thinking uh-oh aren't
you gonna tell me higher or lower no you
have to guess until you get my number
well you might have to guess every
number between 1 and 8 million to figure
out which number it is so if you're
using a list an unsorted list as your
data structure that's what it's like you
would have to iterate through the entire
list to find the number so you may have
to do up to 8 million comparisons to
locate that number that I'm thinking of
that is the issue with lists when you
have a lot of data it's really slow to
find data now with a tree it's a little
different you guess 4 million and I say
lower you guessed 2 million I say higher
you've got 3 million lower ok Wow with 3
guesses
you've shaved off 7 million
possibilities and now you've narrowed
down the possibilities to between 2 and
3 million
you're only 1 million possibilities left
with just 3 guesses so with as few as 30
guesses you would be able to find any
piece of data in a tree with up to 10
million nodes so that is how fast binary
search trees are a balanced binary
search tree will let you locate data in
a very large tree with as little as 30
comparisons so now let's take a look at
some of the major operations of trees
and how they work so first let's learn
some basic terminology about trees this
is a node each part of a tree is called
a node and each connection between nodes
is called an edge and at the very top of
the tree we have a root node you can see
that trees are actually upside down
compared to real-world trees this is
more like a root system of a tree or a
flipped upside down tree or like a
management hierarchy in a company or
something right we only have one
president and then you have multiple
vice presidents and so on down trees are
great for modeling organizations but
that's not the real benefit of tree the
real benefit is the speed now we have
parent nodes and child nodes in a binary
tree a parent can have up to two
children one or two children nodes that
have the same parent are called sibling
nodes and bottom nodes at the very
bottom of the tree that don't have any
children are called leaf nodes not all
trees are binary trees but in a binary
tree each node can have up to two child
nodes a left and right child node now
some trees may have 5/10 of up to a
thousand child nodes for each node we
can see the off of five here we have a
sub tree a sub tree connects to a root
node here and a sub tree is basically
any part of a tree that in itself is a
tree so it can be a sub tree of five
compared to node 4 3 & 5 rows ancestors
which is a parent node and every node
above it's not the parent in the tree
descendants are every node below that
node in a tree so node 5's descendant
includes everything in its left subtree
and everything
right sub-tree in a binary search tree
each node is greater than every node in
its left subtree so here we can see that
15 is greater than every single node in
its left subtree and 8 is greater than
every node in its left subtree and the 5
is greater than every node in this sub
tree the 24 is look greater than every
node in its left subtree so this is a
standard requirement for binary search
trees each node is greater than every
node in its left subtree and it's also
less than each node in its right subtree
here we can see that all the nodes in
15's right subtree are greater than 15
and all the nodes in 24 right subtree
are greater than 20 for all the nodes in
8 right subtree are greater than 8 so
those are 2 standard requirements for a
binary search tree some of the standard
operations that L binary search trees
are going to use insert I'm going to be
able to add new data to the tree fine we
want to be able to locate data in the
tree delete is to remove a node get size
counts all the nodes in a tree to tell
us how many pieces of data we have in a
tree in traversals which enable us to
walk through the tree node by node and
I'll show you how some of those work
first let's look at the insert method
we're going to always start at the root
when we're doing an insert so at the top
in this tree it's 215 we're always going
to insert a new node as a leaf in other
words at the very bottom of the tree but
we start at the top to locate the right
position the correct position in the
tree to insert that new leaf so let's
say we want to insert 12 in this tree
we're going to start out with
comparisons starting at the root is 12
less than 15 yes it is so we're going to
descend down 15 left subtree next we're
going to compare 12 to 8 is 12 less than
8 no it's not so we're going to descend
down 8 right subtree towards the 11
there's 12 less than 11 no it's not
and then we compare 12 to 13 and we say
well yeah 12 is less than 13 so we're
again we're going to add the 12 as a
leaf node so we can add it as 13s left
child that's how the insert function
works now let's look at the fine method
again with fine we'll always start at
the root here it's 15 and we're going to
do comparisons so if we want to find 19
in this tree we're going to start by
comparing 19 to 15 is 19 less than 15 no
it's greater so we descend down the
right subtree and then we compare 19 to
24 19 is less than 24 so we go down 24
left subtree you can see how with each
comparison and decision we descend down
one subtree that cuts in half the number
of remaining possibilities to locate an
item so now we've already in two
comparisons found the 19 in this tree so
when we find a piece of data with define
function we're always going to return
that piece of data and if we didn't find
it we want to return false to let the
user know that data is not existing in a
tree so with delete there are three
different possibilities one is that the
nobody.one delete is a leaf node another
possibility is that it has one child
node then there's another possibility
that has two child nodes so each one of
these we have to handle differently
delete is a fairly complicated operation
so let's first look at the possibility
that the number we want to delete is a
leaf node so look at these are all these
gray nodes are all leaf nodes so in a
case of a leaf node it's easy for us to
just delete the leaf node without
affecting anything else in the tree
these are bottom most nodes so it
doesn't affect the organization of
anything else in the tree we can just
delete that node if it's in the leaf
that's the easiest case right there now
if we have one child
these are cases where we have one child
note 11 13 and 28 if we want to delete
one of those nodes we have to promote
that child node to the targets notes
position so for instance if we wanted to
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