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.