1
00:00:00,000 --> 00:00:03,677
In this video, I'm going to tell you a 
little bit about my approach towards 

2
00:00:03,677 --> 00:00:07,610
teaching data structures in this course. 
So, knowing when and how to use basic 

3
00:00:07,610 --> 00:00:10,930
data structures is an essential skill for 
the serious programmer. 

4
00:00:10,930 --> 00:00:14,505
Data structures are used in pretty much 
every major piece of a software. 

5
00:00:14,505 --> 00:00:18,591
Something reminds you what's the point, 
the raison d'etre of the data structure 

6
00:00:18,591 --> 00:00:22,320
it's job is to organize data in a way 
that you could access it quickly and 

7
00:00:22,320 --> 00:00:26,148
usefully. 
There's many, many examples of data 

8
00:00:26,148 --> 00:00:31,814
structures and hopefully, you've seen a 
few of them and perhaps even use a few of 

9
00:00:31,814 --> 00:00:37,061
them in your own programs. And they range 
from very simple examples like list, 

10
00:00:37,061 --> 00:00:42,518
stacks, and queues to more intricate but 
still very useful one like heaps, search 

11
00:00:42,518 --> 00:00:47,135
trees, hash tables, relatives thereof, 
like bloom filters, union fine 

12
00:00:47,135 --> 00:00:51,472
structures, and so on. 
So, why do we have such a laundry list of 

13
00:00:51,472 --> 00:00:54,830
data structures? 
Why is there such a bewildering 

14
00:00:54,830 --> 00:00:58,856
assortment? 
It's because different data structures 

15
00:00:58,856 --> 00:01:04,124
support different sets of operations and 
are therefore well suited for different 

16
00:01:04,124 --> 00:01:07,915
types of tasks. 
Let me remind you of a concrete example 

17
00:01:07,915 --> 00:01:11,723
that we saw back when we were discussing 
graph search and in particular, 

18
00:01:11,723 --> 00:01:13,679
breadth-first search and depth-first 
search. 

19
00:01:13,679 --> 00:01:17,117
So, we discussed how implementing 
breadth-first search, the right data 

20
00:01:17,117 --> 00:01:20,766
structure to use is a Q, this is 
something that supports fast commuting 

21
00:01:20,766 --> 00:01:24,915
constant time insertion to the back and 
constant time deletion from the front. 

22
00:01:24,915 --> 00:01:29,405
Depth-first search by contrast, 
is a different algorithm with different 

23
00:01:29,405 --> 00:01:31,875
needs. 
And because of its recursive nature, a 

24
00:01:31,875 --> 00:01:33,839
stack is much more appropriate for 
depth-first search. 

25
00:01:34,906 --> 00:01:39,284
That's because it supports constant time 
deletion from the front, but constant 

26
00:01:39,284 --> 00:01:43,101
time insertion to the front. 
So, the last and first out of support of 

27
00:01:43,101 --> 00:01:47,479
a stack is good for depth-first search. 
The first in, first out operations of a 

28
00:01:47,479 --> 00:01:51,548
queue work for breadth-first search. 
Now, because different data structures 

29
00:01:51,548 --> 00:01:55,699
are suitable for different types of 
tasks, you should learn the pros and cons 

30
00:01:55,699 --> 00:01:58,826
of the basic ones. 
Generally speaking, the fewer operations 

31
00:01:58,826 --> 00:02:02,330
that a data structure supports, the 
faster the operations will be. 

32
00:02:02,330 --> 00:02:05,889
And the smaller the space overhead 
required by the data structure. 

33
00:02:05,889 --> 00:02:10,040
Thus, as a programmer, it's important 
that you think carefully about the needs 

34
00:02:10,040 --> 00:02:13,275
of your application. 
What are the operations that you need a 

35
00:02:13,275 --> 00:02:16,617
data structure to export? 
And then, you should choose the right 

36
00:02:16,617 --> 00:02:19,636
data structure. 
Meaning the one that supports all of the 

37
00:02:19,636 --> 00:02:22,440
operations you need. 
But ideally, no superfluous ones. 

38
00:02:22,440 --> 00:02:26,868
Let me suggest four levels of data 
structure knowledge that someone might 

39
00:02:26,868 --> 00:02:29,560
have. 
So, level 0 is the level of ignorance, 

40
00:02:29,560 --> 00:02:34,587
for someone who has never heard of a data 
structure and is unaware of the fact that 

41
00:02:34,587 --> 00:02:38,357
organizing your data can produce 
fundamentally better software. 

42
00:02:38,357 --> 00:02:40,990
For example, fundamentally faster 
algorithms. 

43
00:02:40,990 --> 00:02:44,387
Level 1, I think of as being cocktail 
party level awareness. 

44
00:02:44,387 --> 00:02:48,563
Now, obviously, here, I'm talking only 
about the nerdiest of cocktail parties. 

45
00:02:48,563 --> 00:02:52,851
But nonetheless, this would be someone 
who could at least hold a conversation 

46
00:02:52,851 --> 00:02:56,582
about basic data structures. 
They've heard of things like heaps and 

47
00:02:56,582 --> 00:02:59,757
binary search trees. 
They're perhaps aware of some of the 

48
00:02:59,757 --> 00:03:03,042
basic operations. 
But this person would be shaky using them 

49
00:03:03,042 --> 00:03:06,700
in their own program or, say, in a 
technical interview context. 

50
00:03:06,700 --> 00:03:09,394
Now, with level 2, we're starting to get 
somewhere. 

51
00:03:09,394 --> 00:03:13,251
So here, I would put someone who has 
solid literacy about data structures. 

52
00:03:13,251 --> 00:03:17,161
They're comfortable using them as a 
client in their own programs and they 

53
00:03:17,161 --> 00:03:20,807
have a good sense of which data 
structures are appropriate for which 

54
00:03:20,807 --> 00:03:23,843
types of tasks. 
Now, level 3, the final level, is the 

55
00:03:23,843 --> 00:03:26,431
hardcore programmers and computer 
scientists. 

56
00:03:26,431 --> 00:03:31,033
And these are people who are not content 
to just be a client of data structures 

57
00:03:31,033 --> 00:03:35,520
and use them in their own programs but 
they actually have an understanding of 

58
00:03:35,520 --> 00:03:39,431
the guts of these data structures. 
How they are coded up, how they're 

59
00:03:39,431 --> 00:03:41,790
implemented, not merely how they are 
used. 

60
00:03:41,790 --> 00:03:45,342
Now, my guess is that really a large 
number of you will wind up using a data 

61
00:03:45,342 --> 00:03:48,847
structure in your own programs and 
therefore, learning about what are the 

62
00:03:48,847 --> 00:03:52,735
operations of different data structures 
and what are they good for, will be quite 

63
00:03:52,735 --> 00:03:54,896
an empowering skill for you as a 
programmer. 

64
00:03:54,896 --> 00:03:58,640
On the other hand, I'll bet there are 
very few of you who'll wind up having to 

65
00:03:58,640 --> 00:04:02,385
implement your own data structures from 
scratch, as opposed to just using as a 

66
00:04:02,385 --> 00:04:05,793
client, the data structures that already 
come with the various standard 

67
00:04:05,793 --> 00:04:09,040
programming libraries. 
So, with this in mind, I'm going to focus 

68
00:04:09,040 --> 00:04:13,256
my teaching on taking you up to level 2. 
My discussion is going to focus on the 

69
00:04:13,256 --> 00:04:17,308
operations supported by various data 
structures and some of the canonical 

70
00:04:17,308 --> 00:04:19,991
applications. 
So, through this, I hope I'll develop 

71
00:04:19,991 --> 00:04:24,371
your intuition for what kinds of data 
structures are suitable for what kinds of 

72
00:04:24,371 --> 00:04:26,330
tasks. 
Time permitting however, I'll also 

73
00:04:26,330 --> 00:04:30,118
include some optional material, for those 
of you wanting to take it to the next 

74
00:04:30,118 --> 00:04:33,953
level, and learn something about the guts 
of these data structures, the canonical 

75
00:04:33,953 --> 00:04:35,680
limitations of how you code them up.