1
00:00:00,000 --> 00:00:04,301
In this video, I'm gonna tell you a little
bit about my approach toward teaching data

2
00:00:04,301 --> 00:00:08,602
structures in this course. So knowing when
and how to use basic data structures is an

3
00:00:08,602 --> 00:00:12,195
essential skill for the serious
programmer. Data structures are used in

4
00:00:12,195 --> 00:00:16,395
pretty much every major piece of software.
So let me remind you of what's the point,

5
00:00:16,395 --> 00:00:20,696
the raison d'etre of the data structure?
Its job is to organize data in a way that

6
00:00:20,696 --> 00:00:25,072
you can access it quickly and usefully.
There's many, many examples of data

7
00:00:25,072 --> 00:00:30,908
structures and hopefully you've seen a few
of them and perhaps even used a few of

8
00:00:30,908 --> 00:00:36,263
them in your own programs. And they range
from very simple examples like lists,

9
00:00:36,263 --> 00:00:41,824
stacks and queues to more intricate but
still very useful ones like heaps, search

10
00:00:41,824 --> 00:00:49,330
trees, hash tables. Relatives thereof like
balloon filters. Union find structures and

11
00:00:49,330 --> 00:00:54,152
so on. So why do we have such a laundry
list of data structures? Why is there such

12
00:00:54,152 --> 00:00:59,336
a bewildering assortment? It's because
different data structures support

13
00:00:59,336 --> 00:01:04,474
different sets of operations and are
therefore well suited for different types

14
00:01:04,474 --> 00:01:09,322
of tasks. Let me remind you of a concrete
example that we saw back when we were

15
00:01:09,322 --> 00:01:13,202
discussing graph search. In particular,
breadth first search and depth first

16
00:01:13,202 --> 00:01:17,135
search. So we discussed how implementing
breadth first search the right data

17
00:01:17,135 --> 00:01:20,757
structure to use was a queue. This is
something that supports fast, meaning

18
00:01:20,757 --> 00:01:25,017
constant time insertion to the back, And
constant time deletion from the front.

19
00:01:25,017 --> 00:01:29,413
Depth first search by contrast is a
different algorithm with different needs.

20
00:01:29,413 --> 00:01:33,922
And because of its recursive nature, a
stack is much more appropriate for depth

21
00:01:33,922 --> 00:01:38,603
first search. That's because it supports
constant time deletion from the front, But

22
00:01:38,603 --> 00:01:43,398
constant time insertion to the front. So
the last in first out support of a stack

23
00:01:43,398 --> 00:01:48,022
is good for depth first search. The first
in first out operations of a queue work

24
00:01:48,022 --> 00:01:52,424
for breadth first search, Now because
different data structures are suitable for

25
00:01:52,424 --> 00:01:56,643
different types of tasks you should learn
the pros and cons of the basic ones.

26
00:01:56,643 --> 00:02:01,079
Generally speaking the fewer operations th
at a data structure supports the faster

27
00:02:01,079 --> 00:02:05,297
the operations will be. And the smaller
the space overhead require by the data

28
00:02:05,297 --> 00:02:09,408
structure. Thus, as programmers, it's
important that you think carefully about

29
00:02:09,408 --> 00:02:13,465
the needs of your application. What are
the operations that you need a data

30
00:02:13,465 --> 00:02:17,792
structure to export? And then you should
choose the right data structure, meaning

31
00:02:17,792 --> 00:02:21,470
the one that supports all of the
operations you need. But ideally no

32
00:02:21,470 --> 00:02:25,978
superfluous ones. Let me suggest four
levels of data structure knowledge that

33
00:02:25,978 --> 00:02:30,703
someone might have, So level zero is the
level of ignorance, for someone who has

34
00:02:30,703 --> 00:02:35,487
never heard of a data structure, And is
unaware of the fact that organizing your

35
00:02:35,487 --> 00:02:39,853
data can produce fundamentally better
software. For example, fundamentally

36
00:02:39,853 --> 00:02:44,552
faster algorithms, Level one I think of as
being cocktail party level awareness. Now

37
00:02:44,552 --> 00:02:48,732
obviously, here I'm talking only about the
nerdiest of cocktail parties. But

38
00:02:48,732 --> 00:02:53,135
nonetheless, this would be someone who
could at least hold a conversation about

39
00:02:53,135 --> 00:02:57,649
basic data structures. They've heard of
things like heaps and binary search trees,

40
00:02:57,649 --> 00:03:02,387
they're perhaps aware of some of the basic
operations, but this person would be shaky

41
00:03:02,387 --> 00:03:07,135
using them in their own program or say in
a technical interview context. Now, with

42
00:03:07,135 --> 00:03:11,042
level two, we're starting to get
somewhere. So here I would put someone who

43
00:03:11,042 --> 00:03:15,477
has solid literacy about data structures.
They're comfortable using them as a client

44
00:03:15,477 --> 00:03:19,596
in their own programs, and they have a
good sense of which data structures are

45
00:03:19,596 --> 00:03:23,793
appropriate for which types of tasks. Now
level three, the final level, is the

46
00:03:23,793 --> 00:03:28,049
hardcore programmers and computer
scientists. And these are people who are

47
00:03:28,049 --> 00:03:32,479
not content to just be a client of data
structures, and use them in their own

48
00:03:32,479 --> 00:03:36,793
programs, but they actually have an
understanding of the guts of these data

49
00:03:36,793 --> 00:03:41,222
structures. How they are coded up, how
they're implemented, not merely how they

50
00:03:41,222 --> 00:03:45,105
are used. Now my guess is that, really a
large number of you will wind up using

51
00:03:45,105 --> 00:03:48,958
data structures in your own programs, and
therefore, learning about what are the

52
00:03:48,958 --> 00:03:52,714
operations of different data structures
and what are they good for, will be a

53
00:03:52,714 --> 00:03:56,323
quite empowering skill for you as a
programmer. On the other hand, I'll bet

54
00:03:56,323 --> 00:04:00,420
that very few of you will wind up having
to implement your own data structures from

55
00:04:00,420 --> 00:04:04,224
scratch, as opposed to just using as a
client the data structures that already

56
00:04:04,224 --> 00:04:08,565
come with the various standard programming
libraries. So with this in mind I'm going

57
00:04:08,565 --> 00:04:13,096
to focus my teaching on taking up to level
two. My discussion gonna focus on the

58
00:04:13,096 --> 00:04:17,004
operations reported by various data
structures and some of canonical

59
00:04:17,004 --> 00:04:21,648
applications. So through this I hope I'll
develop your intuition for what kinds of

60
00:04:21,648 --> 00:04:25,806
data structures are suitable for what
kinds of tasks. Time permitting, however,

61
00:04:25,806 --> 00:04:29,614
I also want to include some optional
material for those of you wanting to take

62
00:04:29,614 --> 00:04:33,422
it to the next level and learn some about
the guts of these data structure, the

63
00:04:33,422 --> 00:04:35,640
canonical limitations of how you code them
up.