1
00:00:01,080 --> 00:00:01,670
OK.

2
00:00:01,710 --> 00:00:03,480
So welcome back again.

3
00:00:03,960 --> 00:00:12,240
The first data structure that we are going to talk about is the linked list, and we are going to go

4
00:00:12,240 --> 00:00:14,280
over two types of link lists.

5
00:00:15,420 --> 00:00:20,630
The first one being a singly linked list and the second one being a list.

6
00:00:21,270 --> 00:00:22,500
So let's get right into it.

7
00:00:24,430 --> 00:00:31,990
So looking at singly linked lists, they are basically just made up of these things that we're going

8
00:00:31,990 --> 00:00:38,950
to call nodes, which we will be implementing as a class or struct.

9
00:00:40,260 --> 00:00:43,620
And they have data associated with them.

10
00:00:44,740 --> 00:00:55,390
You data members, as well as a another member of the class that is a pointer to the next node.

11
00:00:56,140 --> 00:01:02,470
And so we will have this node class as well as a class for the entire list.

12
00:01:04,400 --> 00:01:11,360
And basically the next point her, which will be a node pointer, enables us to get from each node to

13
00:01:11,360 --> 00:01:16,610
the next node and we can traverse it in a sequential fashion like this.

14
00:01:17,730 --> 00:01:23,070
And at the end here, you see, it's pointing to no will be initialized in these pointers to know,

15
00:01:23,070 --> 00:01:28,380
and that's a good way to know if you're going off the end of the list.

16
00:01:28,380 --> 00:01:35,250
So we do not try and reference a null part of memory and get a segfault like you might have encountered

17
00:01:35,520 --> 00:01:37,260
in the previous parts of the course.

18
00:01:39,510 --> 00:01:47,010
So, yeah, there also is a head and tail that we can label, so we might have a.

19
00:01:48,460 --> 00:01:57,160
Had, I guess, part of the last class we would have like a head pointer, they would point to the first

20
00:01:57,160 --> 00:02:02,290
node in the list and a tail pointer that would point to the last and we'd be updating those as we add

21
00:02:02,290 --> 00:02:04,180
things to the list.

22
00:02:05,810 --> 00:02:12,440
OK, so let's move on to the next one, which is doubly linked lists pretty much the same thing, except

23
00:02:12,440 --> 00:02:18,080
now we have a way to access the previous node.

24
00:02:19,100 --> 00:02:22,660
So you can see it's kind of bi directional here.

25
00:02:23,540 --> 00:02:32,450
We can traverse it to the right this way going forward to the next node, as well as going backwards

26
00:02:32,450 --> 00:02:34,880
this way to the previous node.

27
00:02:34,890 --> 00:02:44,930
So we have that next pointer, but we also have a member that is pointing to the previous node as well,

28
00:02:44,930 --> 00:02:51,770
and we will need to update those as we move along and add new things to our list.

29
00:02:52,160 --> 00:02:59,900
And you also see here that this previous pointer is pointing to null at the beginning of the list here.

30
00:03:03,420 --> 00:03:05,660
So why even talk about linguists?

31
00:03:05,670 --> 00:03:07,410
What are they for?

32
00:03:08,160 --> 00:03:10,860
Why should we use them anything special about them?

33
00:03:11,880 --> 00:03:18,420
Well, the first thing to really look about or the main thing, the main thing to look at is why would

34
00:03:18,420 --> 00:03:19,870
you use it over something else?

35
00:03:19,900 --> 00:03:26,430
So one of the main comparisons of this made is using it over an array or vector.

36
00:03:27,210 --> 00:03:36,570
And the advantage that the linguist has over the vector is that if you are inserting a new element into

37
00:03:36,570 --> 00:03:43,740
a vector or an array and mind you, this is not at the end, so it's not a pending an item, but you're

38
00:03:43,740 --> 00:03:48,470
inserting it, let's say, somewhere in the middle, which is anywhere besides the end, you know,

39
00:03:48,480 --> 00:03:49,380
or it can be the beginning.

40
00:03:50,040 --> 00:03:56,580
But it's much more efficient when you have a link list because you don't need to push everything back.

41
00:03:57,120 --> 00:04:04,530
If you add something in an array or vector, just by their nature, being able to index those things

42
00:04:04,860 --> 00:04:06,210
since they're subscript able.

43
00:04:07,430 --> 00:04:11,390
It means that if you're going to put something in some place, you need to move everything out of the

44
00:04:11,390 --> 00:04:11,780
way.

45
00:04:11,990 --> 00:04:18,290
So if you think about it, it's kind of like if you had a bunch of things lined up in a row, they could

46
00:04:18,290 --> 00:04:22,310
be anything like a bunch of cards or something, but they were all pressed right against each other.

47
00:04:22,580 --> 00:04:28,910
If you're going to put something in the middle, you're going to have to move the cards next to it over

48
00:04:28,910 --> 00:04:30,110
to make space for it.

49
00:04:30,560 --> 00:04:34,100
You have to move the card to the right of that card or.

50
00:04:35,580 --> 00:04:37,950
The laughter, you know, let's just say that you were.

51
00:04:39,400 --> 00:04:45,010
Choosing to insert it in like the second position, you'd have to move the car to the left out of the

52
00:04:45,010 --> 00:04:48,340
way and then the cars to the right, I believe the each time you moved, when you have to move the next

53
00:04:48,340 --> 00:04:50,100
one to its right and so on.

54
00:04:50,110 --> 00:05:01,960
So that kind of operation turns into linear time because if you have any items in the vector or array,

55
00:05:01,990 --> 00:05:10,420
you're going to have to move those in items, shift them over to accommodate for the thing that you're

56
00:05:10,420 --> 00:05:11,110
inserting.

57
00:05:11,800 --> 00:05:21,280
So you think back to when we had just talked about at the time complexity and previous lecture, you

58
00:05:21,280 --> 00:05:25,630
remember how we were counting those operations.

59
00:05:26,800 --> 00:05:32,800
And that's basically what's happening in this vector is that we're having to go through all those items

60
00:05:32,800 --> 00:05:34,960
and perform an operation where we're moving it over.

61
00:05:35,830 --> 00:05:41,860
So in a leaf list, you can just insert something and change some pointers around and put the next pointer

62
00:05:41,860 --> 00:05:43,120
pointing to the new thing.

63
00:05:43,130 --> 00:05:43,690
Put the.

64
00:05:44,660 --> 00:05:50,390
The thing to the right pointing back to it, if you have a creative pointer, we'll get into the implementation

65
00:05:50,390 --> 00:05:59,780
details in the next video, but it's a lot easier and more efficient than inserting something into a

66
00:05:59,780 --> 00:06:00,090
vector.

67
00:06:00,090 --> 00:06:03,920
And I don't know if I would say easier because you are you going to have to move around some pointers

68
00:06:05,000 --> 00:06:06,800
kind of change the things they're pointing at.

69
00:06:07,310 --> 00:06:10,520
But in terms of efficiency, it is a lot better.

70
00:06:10,700 --> 00:06:18,470
So that is a reason to use a linguist and inserting that can be done in constant time.

71
00:06:18,800 --> 00:06:25,100
Since you remember back to that previous lecture about time complexity, you know that that's one of

72
00:06:25,100 --> 00:06:30,380
the best begos that that we could see there if you were looking at that graph.

73
00:06:30,650 --> 00:06:33,440
So that is all we have on link list.

74
00:06:33,440 --> 00:06:36,680
Let's get to the implementation details about these things.