In this video, I'm gonna tell you a little
bit about my approach toward teaching data
structures in this course. So knowing when
and how to use basic data structures is an
essential skill for the serious
programmer. Data structures are used in
pretty much every major piece of software.
So let me remind you of what's the point,
the raison d'etre of the data structure?
Its job is to organize data in a way that
you can access it quickly and usefully.
There's many, many examples of data
structures and hopefully you've seen a few
of them and perhaps even used a few of
them in your own programs. And they range
from very simple examples like lists,
stacks and queues to more intricate but
still very useful ones like heaps, search
trees, hash tables. Relatives thereof like
balloon filters. Union find structures and
so on. So why do we have such a laundry
list of data structures? Why is there such
a bewildering assortment? It's because
different data structures support
different sets of operations and are
therefore well suited for different types
of tasks. Let me remind you of a concrete
example that we saw back when we were
discussing graph search. In particular,
breadth first search and depth first
search. So we discussed how implementing
breadth first search the right data
structure to use was a queue. This is
something that supports fast, meaning
constant time insertion to the back, And
constant time deletion from the front.
Depth first search by contrast is a
different algorithm with different needs.
And because of its recursive nature, a
stack is much more appropriate for depth
first search. That's because it supports
constant time deletion from the front, But
constant time insertion to the front. So
the last in first out support of a stack
is good for depth first search. The first
in first out operations of a queue work
for breadth first search, Now because
different data structures are suitable for
different types of tasks you should learn
the pros and cons of the basic ones.
Generally speaking the fewer operations th
at a data structure supports the faster
the operations will be. And the smaller
the space overhead require by the data
structure. Thus, as programmers, it's
important that you think carefully about
the needs of your application. What are
the operations that you need a data
structure to export? And then you should
choose the right data structure, meaning
the one that supports all of the
operations you need. But ideally no
superfluous ones. Let me suggest four
levels of data structure knowledge that
someone might have, So level zero is the
level of ignorance, for someone who has
never heard of a data structure, And is
unaware of the fact that organizing your
data can produce fundamentally better
software. For example, fundamentally
faster algorithms, Level one I think of as
being cocktail party level awareness. Now
obviously, here I'm talking only about the
nerdiest of cocktail parties. But
nonetheless, this would be someone who
could at least hold a conversation about
basic data structures. They've heard of
things like heaps and binary search trees,
they're perhaps aware of some of the basic
operations, but this person would be shaky
using them in their own program or say in
a technical interview context. Now, with
level two, we're starting to get
somewhere. So here I would put someone who
has solid literacy about data structures.
They're comfortable using them as a client
in their own programs, and they have a
good sense of which data structures are
appropriate for which types of tasks. Now
level three, the final level, is the
hardcore programmers and computer
scientists. And these are people who are
not content to just be a client of data
structures, and use them in their own
programs, but they actually have an
understanding of the guts of these data
structures. How they are coded up, how
they're implemented, not merely how they
are used. Now my guess is that, really a
large number of you will wind up using
data structures in your own programs, and
therefore, learning about what are the
operations of different data structures
and what are they good for, will be a
quite empowering skill for you as a
programmer. On the other hand, I'll bet
that very few of you will wind up having
to implement your own data structures from
scratch, as opposed to just using as a
client the data structures that already
come with the various standard programming
libraries. So with this in mind I'm going
to focus my teaching on taking up to level
two. My discussion gonna focus on the
operations reported by various data
structures and some of canonical
applications. So through this I hope I'll
develop your intuition for what kinds of
data structures are suitable for what
kinds of tasks. Time permitting, however,
I also want to include some optional
material for those of you wanting to take
it to the next level and learn some about
the guts of these data structure, the
canonical limitations of how you code them
up.