OK, so this is going to be a video going over the solution to the most recent coding exercise and that
coding the exercise, you were asked to implement a D structure for our linked list, our list and also
to implement a function for checking whether the linked list was a palindrome by looking at the characters
for one character, for each node kind of put together in a row, assuming that was the palindrome word.
So we've been going along with our link list without having a destructor, and so we've made ourselves
vulnerable to memory leaks and things like that.
So it's always important to implement the destructor.
We do not have an assignment operator and a copy constructor, which is normally good to implement,
but we just haven't been using that lately, but we definitely want to implement the structure.
So I'm going to go ahead and start out by declaring that here.
So I'm going to say L List, and then I'm also going to put my palindrome function here, which I made
a Google returns a rule.
And yet you might have something other than a war.
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
palindrome or not.
OK, so let's go over to the CP file to put our implementation in here.
I'm going to go ahead and copy this template and do the destructor first.
So let's put the resolution in here to you list.
And so in the normal way I implement this is to make a while loop where we update the head kind of move
the head along.
We start at the beginning and as our head moves along, we make a temporary pointer that is equal to
the head and then delete that temporary pointer.
So I'm going to make a while loop here and say, Well, head is not equal to no point here.
I'm going to declare or create a temporary pointer here called Destroy and set it equal to head.
Each time our current head, as we move headlong and I'm going to move head along on this line where
I say head equals head arrow next.
And then I'm going to delete that temporary pointer that I made.
So delete destroy.
And that's all I need to put in there.
Let's just make sure that we are in fact allocating that memory that we don't dynamically allocated
every time we use the new key word, for example, like this line right here in the append function?
So I'm going won't go down here to implement our palindrome function, and so put the template there
now I'm just going to call this blue.
It was analyst t is palindrome.
I believe the capital P.
And the way that I do this, since we have a doubly lengthy list, I'm going to make a pointer to the
head and a pointer to the tail and kind of simultaneously move forwards with my pointer that start at
the head and backwards.
With the point of this started at the tail end, compare the characters that are stored in the data
member.
And if they ever don't match, then I'm going to say that it's false immediately.
Otherwise, if it successfully goes all the way through in those two kind of iterator style moving pointers,
cross or meet, then I know that the word is in fact a palindrome.
So that is going to be my kind of algorithm, if you will, for solving this problem.
Very curious to see how other people implemented it.
If you did it a different way, that's totally fine.
This is just the way that I'm going to put in this solution, so I want to make my first pointer here
and call it forwards.
Set it equal to the head, start at the head and another pointer and call this backwards and set that
equal to the tail.
Then I'm going to make it count because I need to keep track of where I am in the length list.
So I'm going to do a forward count equals zero.
And then I'm also going to have a backwards count and call that be count.
And that is going to be equal to the size of our length list.
So I'm basically going to, yeah, start at the other end and have that equal to be size, and then
I'm going to have a while loop here.
So I'm going to say while the forward count is less than or equal to the backward count,
then if I do, if four words data is not equal to backwards data in that case, I know I can immediately
return false because it's not a palindrome.
If the corresponding position on the other end is different, then I know that.
It is, in fact, not a palindrome, because those things don't match, so we immediately can just bail
out and say that is false, and then I'm going to and the other case that that did not return false,
I'm going to move my forwards pointer and say four words next.
And then I'm going to say backwards
equals backwards.
Previous.
Because I'm moving backwards there and then I'm going to increment that forward count variable and decrement
the backward count variable that started at size.
And then I am going to return true.
So if it did not bail out immediately in return from the function here, I know that if my while loop
has completed, then I have in fact satisfied this condition and the word is a palindrome.
OK.
So I think that that is all that I need there.
I'm going to go ahead and go over to Main.
And just add a check here.
You can see that I already commented out this link to list.
That was.
Using the integers, looking for integers, and because I'm not going to need that, I just want the
char.
So we're just trying to prove that our function works here, not do anything super fancy.
I'm going to put a conditional here and I'm going to check to see if the link char is palindrome by
calling that function and having it return that boolean.
If so, I'll just print something out saying it is a palindrome.
Otherwise, I will print something out that says it is not true.
OK, so it's all put there in Maine.
We do want to go ahead and modify our input file.
And I know that we're not really making great use of this input file.
It could have a lot more content in it, but I'm just doing this for the sake of simplicity.
So we can just see whether our function works as quick as possible, and we're not making some big project
or something, but just trying to touch on these concepts.
So I'm just going to put one word in here.
I know race car is a palindrome.
Going to put that here and I left this other stuff here.
Printing out online.
25.
Just so we can see that forwards and backwards, those things that we had in our print statement, I
left that in there because while we were using it to check whether our link list functionality was correct
or not, it's also nice to just visually see whether the forwards version of a word is the same as the
backwards version right in front of you before seeing whether it's a palindrome or not.
So for that reason, I left it in there.
So let's go ahead and test some different input to see if our function works.
I have that race car in there.
If everything is good to go, this runs, let's go ahead and run it.
OK, so it says it is a palindrome.
So we see the forwards and backwards there, and it looked like it was correct.
Let's go ahead and just modify this a little bit.
So if I say.
Let's just say I'm going to lead that race here.
Just really makes sense, but I'm going to put that there is not a palindrome.
And let's go ahead and say.
These aren't really real wars, but I'm just trying to see whether.
And footwork, so says that is not a palindrome.
And if I say what is another palindrome?
Do you not really able to think of great ones right now?
Says that is June.
So then if I.
But something like this, not a palindrome.
So we are checking up on this, and it's probably good to just see use as many things as you can.
Think of, unfortunately, a race car was the only one that was coming into my head.
Let's see if I just a.
Well, I can just put some random things we'll just say.
That.
Palindrome.
Not a palindrome.
So it seems to be working pretty good.
Go ahead and run some as many input options as you can be really good to check this and also might be
good to make it modify our means so we can actually just take in like a bunch of.
Things from the file.
And create maybe like more like lists like if you put Link his creation, maybe in a loop or something
like that so you can test a whole range of input, maybe grab like some palindrome stuff off the internet
and a big text file and check that that would be a good idea.
I'm not going to modify my file for that here, but that should be an easy modification for it at this
point.
And pretty much that is what this actually was going to be about, just implementing that structure
in this palindrome.
If you implemented it some other way, that is totally fine and congratulations for solving the problem.
This just seemed like a logical way to implement this.
Since we have a doubling link list, we can move from both ends at the same time and kind of converge
in the middle.
So, of course, very curious to see how everyone came up with their solution to this, but other than
that, I will see you in the next lecture.