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.

Â