0:00

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.