In this video, I'm going to tell you a little bit about my approach towards
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 a software.
Something reminds you what's the point, the raison d'etre of the data structure
it's job is to organize data in a way that you could 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 use a few of
them in your own programs. And they range from very simple examples like list,
stacks, and queues to more intricate but still very useful one like heaps, search
trees, hash tables, relatives thereof, like bloom filters, union fine
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 and in particular,
breadth-first search and depth-first search.
So, we discussed how implementing breadth-first search, the right data
structure to use is a Q, this is something that supports fast commuting
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 and first out of 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
that a data structure supports, the faster the operations will be.
And the smaller the space overhead required by the data structure.
Thus, as a programmer, 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 0 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 1, 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 2, 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 3, 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 a data
structure in your own programs and therefore, learning about what are the
operations of different data structures and what are they good for, will be quite
an empowering skill for you as a programmer.
On the other hand, I'll bet there are very few of you who'll 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 you up to level 2. My discussion is going to focus on the
operations supported by various data structures and some of the 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'll also
include some optional material, for those of you wanting to take it to the next
level, and learn something about the guts of these data structures, the canonical
limitations of how you code them up.