1
00:00:01,520 --> 00:00:10,610
OK, so this is going to be a video going over the solution to the most recent coding exercise and that

2
00:00:10,610 --> 00:00:22,190
coding the exercise, you were asked to implement a D structure for our linked list, our list and also

3
00:00:22,190 --> 00:00:32,270
to implement a function for checking whether the linked list was a palindrome by looking at the characters

4
00:00:32,480 --> 00:00:39,920
for one character, for each node kind of put together in a row, assuming that was the palindrome word.

5
00:00:41,060 --> 00:00:48,680
So we've been going along with our link list without having a destructor, and so we've made ourselves

6
00:00:49,010 --> 00:00:52,790
vulnerable to memory leaks and things like that.

7
00:00:52,790 --> 00:00:56,150
So it's always important to implement the destructor.

8
00:00:56,180 --> 00:01:01,970
We do not have an assignment operator and a copy constructor, which is normally good to implement,

9
00:01:01,970 --> 00:01:08,480
but we just haven't been using that lately, but we definitely want to implement the structure.

10
00:01:09,500 --> 00:01:13,700
So I'm going to go ahead and start out by declaring that here.

11
00:01:15,530 --> 00:01:25,370
So I'm going to say L List, and then I'm also going to put my palindrome function here, which I made

12
00:01:25,370 --> 00:01:29,720
a Google returns a rule.

13
00:01:36,250 --> 00:01:39,550
And yet you might have something other than a war.

14
00:01:40,000 --> 00:01:47,530
It can't seem to make sense to have it as a bull, since it's kind of a yes or no question whether it's

15
00:01:47,530 --> 00:01:48,850
palindrome or not.

16
00:01:50,590 --> 00:01:55,990
OK, so let's go over to the CP file to put our implementation in here.

17
00:01:56,440 --> 00:02:04,180
I'm going to go ahead and copy this template and do the destructor first.

18
00:02:04,510 --> 00:02:12,310
So let's put the resolution in here to you list.

19
00:02:12,910 --> 00:02:22,090
And so in the normal way I implement this is to make a while loop where we update the head kind of move

20
00:02:22,090 --> 00:02:22,900
the head along.

21
00:02:23,440 --> 00:02:30,040
We start at the beginning and as our head moves along, we make a temporary pointer that is equal to

22
00:02:30,040 --> 00:02:33,040
the head and then delete that temporary pointer.

23
00:02:33,970 --> 00:02:40,060
So I'm going to make a while loop here and say, Well, head is not equal to no point here.

24
00:02:42,400 --> 00:02:50,750
I'm going to declare or create a temporary pointer here called Destroy and set it equal to head.

25
00:02:50,770 --> 00:02:56,710
Each time our current head, as we move headlong and I'm going to move head along on this line where

26
00:02:56,710 --> 00:02:59,740
I say head equals head arrow next.

27
00:03:01,120 --> 00:03:04,840
And then I'm going to delete that temporary pointer that I made.

28
00:03:05,320 --> 00:03:07,360
So delete destroy.

29
00:03:09,000 --> 00:03:10,290
And that's all I need to put in there.

30
00:03:10,710 --> 00:03:16,620
Let's just make sure that we are in fact allocating that memory that we don't dynamically allocated

31
00:03:16,620 --> 00:03:21,270
every time we use the new key word, for example, like this line right here in the append function?

32
00:03:23,540 --> 00:03:32,680
So I'm going won't go down here to implement our palindrome function, and so put the template there

33
00:03:32,710 --> 00:03:34,660
now I'm just going to call this blue.

34
00:03:35,290 --> 00:03:39,290
It was analyst t is palindrome.

35
00:03:39,530 --> 00:03:41,750
I believe the capital P.

36
00:03:43,800 --> 00:03:53,370
And the way that I do this, since we have a doubly lengthy list, I'm going to make a pointer to the

37
00:03:53,370 --> 00:04:00,750
head and a pointer to the tail and kind of simultaneously move forwards with my pointer that start at

38
00:04:00,750 --> 00:04:02,400
the head and backwards.

39
00:04:03,000 --> 00:04:09,540
With the point of this started at the tail end, compare the characters that are stored in the data

40
00:04:09,540 --> 00:04:10,020
member.

41
00:04:10,770 --> 00:04:16,330
And if they ever don't match, then I'm going to say that it's false immediately.

42
00:04:16,860 --> 00:04:23,970
Otherwise, if it successfully goes all the way through in those two kind of iterator style moving pointers,

43
00:04:24,810 --> 00:04:30,060
cross or meet, then I know that the word is in fact a palindrome.

44
00:04:30,870 --> 00:04:37,230
So that is going to be my kind of algorithm, if you will, for solving this problem.

45
00:04:37,980 --> 00:04:40,620
Very curious to see how other people implemented it.

46
00:04:41,010 --> 00:04:43,470
If you did it a different way, that's totally fine.

47
00:04:43,830 --> 00:04:48,780
This is just the way that I'm going to put in this solution, so I want to make my first pointer here

48
00:04:48,780 --> 00:04:50,510
and call it forwards.

49
00:04:51,060 --> 00:05:00,060
Set it equal to the head, start at the head and another pointer and call this backwards and set that

50
00:05:00,060 --> 00:05:01,050
equal to the tail.

51
00:05:02,490 --> 00:05:08,040
Then I'm going to make it count because I need to keep track of where I am in the length list.

52
00:05:08,310 --> 00:05:11,520
So I'm going to do a forward count equals zero.

53
00:05:12,390 --> 00:05:16,170
And then I'm also going to have a backwards count and call that be count.

54
00:05:16,890 --> 00:05:22,230
And that is going to be equal to the size of our length list.

55
00:05:23,770 --> 00:05:37,510
So I'm basically going to, yeah, start at the other end and have that equal to be size, and then

56
00:05:37,510 --> 00:05:41,620
I'm going to have a while loop here.

57
00:05:43,090 --> 00:05:54,640
So I'm going to say while the forward count is less than or equal to the backward count,

58
00:05:58,150 --> 00:06:15,970
then if I do, if four words data is not equal to backwards data in that case, I know I can immediately

59
00:06:15,970 --> 00:06:19,120
return false because it's not a palindrome.

60
00:06:19,300 --> 00:06:28,090
If the corresponding position on the other end is different, then I know that.

61
00:06:30,970 --> 00:06:37,120
It is, in fact, not a palindrome, because those things don't match, so we immediately can just bail

62
00:06:37,120 --> 00:06:44,460
out and say that is false, and then I'm going to and the other case that that did not return false,

63
00:06:44,470 --> 00:06:53,230
I'm going to move my forwards pointer and say four words next.

64
00:06:55,120 --> 00:06:58,660
And then I'm going to say backwards

65
00:07:02,110 --> 00:07:03,550
equals backwards.

66
00:07:04,060 --> 00:07:04,900
Previous.

67
00:07:04,900 --> 00:07:15,700
Because I'm moving backwards there and then I'm going to increment that forward count variable and decrement

68
00:07:16,330 --> 00:07:19,600
the backward count variable that started at size.

69
00:07:22,750 --> 00:07:26,710
And then I am going to return true.

70
00:07:26,720 --> 00:07:34,240
So if it did not bail out immediately in return from the function here, I know that if my while loop

71
00:07:34,240 --> 00:07:40,120
has completed, then I have in fact satisfied this condition and the word is a palindrome.

72
00:07:42,490 --> 00:07:43,000
OK.

73
00:07:43,120 --> 00:07:49,060
So I think that that is all that I need there.

74
00:07:50,980 --> 00:07:53,740
I'm going to go ahead and go over to Main.

75
00:07:53,800 --> 00:07:55,240
And just add a check here.

76
00:07:55,240 --> 00:07:58,720
You can see that I already commented out this link to list.

77
00:07:59,710 --> 00:08:00,850
That was.

78
00:08:01,910 --> 00:08:08,180
Using the integers, looking for integers, and because I'm not going to need that, I just want the

79
00:08:08,180 --> 00:08:08,690
char.

80
00:08:09,170 --> 00:08:13,730
So we're just trying to prove that our function works here, not do anything super fancy.

81
00:08:14,540 --> 00:08:25,820
I'm going to put a conditional here and I'm going to check to see if the link char is palindrome by

82
00:08:25,820 --> 00:08:28,010
calling that function and having it return that boolean.

83
00:08:29,210 --> 00:08:33,470
If so, I'll just print something out saying it is a palindrome.

84
00:08:36,230 --> 00:08:41,800
Otherwise, I will print something out that says it is not true.

85
00:08:44,990 --> 00:08:48,210
OK, so it's all put there in Maine.

86
00:08:48,230 --> 00:08:50,870
We do want to go ahead and modify our input file.

87
00:08:51,860 --> 00:08:55,120
And I know that we're not really making great use of this input file.

88
00:08:55,130 --> 00:09:00,080
It could have a lot more content in it, but I'm just doing this for the sake of simplicity.

89
00:09:01,780 --> 00:09:07,510
So we can just see whether our function works as quick as possible, and we're not making some big project

90
00:09:07,600 --> 00:09:11,650
or something, but just trying to touch on these concepts.

91
00:09:12,010 --> 00:09:13,540
So I'm just going to put one word in here.

92
00:09:13,780 --> 00:09:16,420
I know race car is a palindrome.

93
00:09:17,140 --> 00:09:20,920
Going to put that here and I left this other stuff here.

94
00:09:21,190 --> 00:09:22,810
Printing out online.

95
00:09:22,810 --> 00:09:23,770
25.

96
00:09:23,860 --> 00:09:30,640
Just so we can see that forwards and backwards, those things that we had in our print statement, I

97
00:09:30,640 --> 00:09:38,470
left that in there because while we were using it to check whether our link list functionality was correct

98
00:09:38,470 --> 00:09:44,470
or not, it's also nice to just visually see whether the forwards version of a word is the same as the

99
00:09:44,470 --> 00:09:49,240
backwards version right in front of you before seeing whether it's a palindrome or not.

100
00:09:50,290 --> 00:09:52,030
So for that reason, I left it in there.

101
00:09:53,530 --> 00:09:57,170
So let's go ahead and test some different input to see if our function works.

102
00:09:57,190 --> 00:09:58,460
I have that race car in there.

103
00:09:58,480 --> 00:10:02,140
If everything is good to go, this runs, let's go ahead and run it.

104
00:10:07,090 --> 00:10:09,760
OK, so it says it is a palindrome.

105
00:10:11,920 --> 00:10:20,080
So we see the forwards and backwards there, and it looked like it was correct.

106
00:10:20,650 --> 00:10:23,170
Let's go ahead and just modify this a little bit.

107
00:10:23,170 --> 00:10:25,120
So if I say.

108
00:10:29,530 --> 00:10:33,940
Let's just say I'm going to lead that race here.

109
00:10:33,990 --> 00:10:38,440
Just really makes sense, but I'm going to put that there is not a palindrome.

110
00:10:39,670 --> 00:10:42,480
And let's go ahead and say.

111
00:10:48,840 --> 00:10:51,690
These aren't really real wars, but I'm just trying to see whether.

112
00:10:53,720 --> 00:10:56,270
And footwork, so says that is not a palindrome.

113
00:11:00,610 --> 00:11:06,230
And if I say what is another palindrome?

114
00:11:13,550 --> 00:11:17,390
Do you not really able to think of great ones right now?

115
00:11:18,610 --> 00:11:20,460
Says that is June.

116
00:11:20,830 --> 00:11:22,810
So then if I.

117
00:11:25,040 --> 00:11:27,920
But something like this, not a palindrome.

118
00:11:29,420 --> 00:11:40,460
So we are checking up on this, and it's probably good to just see use as many things as you can.

119
00:11:41,530 --> 00:11:47,290
Think of, unfortunately, a race car was the only one that was coming into my head.

120
00:11:52,770 --> 00:11:57,720
Let's see if I just a.

121
00:12:00,320 --> 00:12:04,100
Well, I can just put some random things we'll just say.

122
00:12:08,060 --> 00:12:08,530
That.

123
00:12:10,810 --> 00:12:11,800
Palindrome.

124
00:12:16,270 --> 00:12:17,280
Not a palindrome.

125
00:12:17,320 --> 00:12:18,790
So it seems to be working pretty good.

126
00:12:19,120 --> 00:12:26,770
Go ahead and run some as many input options as you can be really good to check this and also might be

127
00:12:26,770 --> 00:12:32,710
good to make it modify our means so we can actually just take in like a bunch of.

128
00:12:34,470 --> 00:12:35,910
Things from the file.

129
00:12:37,810 --> 00:12:44,230
And create maybe like more like lists like if you put Link his creation, maybe in a loop or something

130
00:12:44,230 --> 00:12:50,230
like that so you can test a whole range of input, maybe grab like some palindrome stuff off the internet

131
00:12:50,840 --> 00:12:54,670
and a big text file and check that that would be a good idea.

132
00:12:54,700 --> 00:13:00,880
I'm not going to modify my file for that here, but that should be an easy modification for it at this

133
00:13:00,880 --> 00:13:01,270
point.

134
00:13:02,530 --> 00:13:07,240
And pretty much that is what this actually was going to be about, just implementing that structure

135
00:13:07,240 --> 00:13:08,230
in this palindrome.

136
00:13:08,920 --> 00:13:16,180
If you implemented it some other way, that is totally fine and congratulations for solving the problem.

137
00:13:16,480 --> 00:13:19,420
This just seemed like a logical way to implement this.

138
00:13:19,930 --> 00:13:25,630
Since we have a doubling link list, we can move from both ends at the same time and kind of converge

139
00:13:25,630 --> 00:13:26,200
in the middle.

140
00:13:27,220 --> 00:13:32,200
So, of course, very curious to see how everyone came up with their solution to this, but other than

141
00:13:32,200 --> 00:13:35,400
that, I will see you in the next lecture.