Palindrome Function!

[m4wk]

Hey guys, so I have an assignment for my programming class and we are supposed to write a function "bool isPalindrome" to determine whether or not the file that is being read in from a txt file is a palindrome or not. This function takes the head and the tail of the doubly linked list and returns true if the string is a palindrome, false otherwise.

My question is how should I go about comparing the values in a doubly-linked list? I'm kind of confused on how to iterate through a doubly-linked list and most programming tutorials I've looked at are hard to follow haha.

http://pastebin.com/cimgbbbM
^^^is the .cpp file that we were given to fill in the function.Thanks for any hints/tips/help! :)

[wolfgang]

Its really just a simple while loop.

The double link list structure has 3 members: 1) Pointer to the previous member in the list, 2) The data it itself holds, 3) A pointer to the next member in the list.

You can simply navigate through a list by setting a pointer to the value of one of the lists members. Its usually best to start at the head. Then to transverse the list simply set the value of the pointer to the member "next".

Like this:

CharLinkD *p = head; // set equal to the pointer that knows the data for the head.
p = head->next; // Sets it to the next list member. 

To transverse forward only, you only need one pointer and can stop when p->next == head;

For your project you'll need two pointers to transverse coming from opposite ends of the DLList. Luckily your teacher has given them to you in the function header.

Now all you need to do is set up a while condition that uses the next and prev members of the struct to determine when to stop comparing. You should not do actual comparing here of the values unless you want to stop the instance its not a palindrome.

With two pointers (from your code are set to the head and tail of the list) simply transverse until they meet or the data values of the two data values do not match. If they do match move head to its next pointer, and tail to its previous pointer.

bool isPalindrome(CharLinkD * head, CharLinkD * tail) {
    while ( /* Condition; Stop transversing when the two pointers meet. Remember odd and even digit palindromes may meet differently. Maybe add a condition to stop when answer is false? */ )
    {
        if(/* Data check the "matching" digits of the palindrome. */)
            /* set values here accordingly for the data check */

// Transverse these together toward each other.
// p--> 1223221 <--q
// But don't add a p and q pointer. You already have two working ones in the header.
// hint hint wink wink nudge nudge
        p = p->next;
        q = q->prev;
    }

    // return the answer
}

[m4wk]

So I can follow what you are saying, but I don't think I understand how to "stop transversing when the two pointers meet". I have this so far for the code, but its probably completely wrong :/

http://pastebin.com/4H7MdwUJ

[m4wk]

I was looking at the problem a bit more and this is what I came up with, still not sure if I'm thinking of this situation correctly, it's been a long time since I've dealt with linked lists.

http://pastebin.com/TiM4nb7y


someone please come to the rescue! :P

[keineahnung]

m4wk - that code's only 16 lines long. Why not post it up here instead? Then it's documented for anyone else who's got the same problem and follows the link.
Looking at that function, you don't need the bool answer = true; line because its value never changes. Just return true; at the end.
The conditional statement in your while loop looks a bit laboured but was it working at least some of the time? Any test data you can post up, maybe trying words with both an odd and even number of total letters?
Regards, keineahnung

[m4wk]

Sorry bout the pastebin, it's just a habit when I share code; sorry lol. As for the bool answer = true; it was provided with the rest of the code so I tried working around it, I see what you mean as to why I don't need it.

Does the conditional statement look right at all? How could I have shortened it to mean the same thing? I'm not sure if the code works necessarily, as I just wanted to initially see if my code was even close to being correct. I was provided with a word list of 54,000 words of different lengths, and it's supposed to insert them to a list, and print out the ones that are palindromes.

Regards,
m4wk

[keineahnung]

Does the conditional statement look right at all?

Yes, a bit, but it seems over-complicated - but if it's working with the rest of your program then that's fine.
Imagine you've got a 3-letter palindrome: 'dad'
-both pointers are at 'd', letters match
-increment front, decrement back
-pointers are equal
It looks like your function should handle that OK.

Four-letter palindrome: 'abba'
-both pointers at 'a', letters match
-increment front, decrement back
-both pointers at 'b', letters match
-increment front, decrement back
Now back pointer's at the first 'b', front pointer's at the 2nd 'b'.
Couldn't you test for head < tail?

while ( head != tail && head < tail )
{
    // ...
} // while 

Actually I've only just noticed (duh!) there's a logic error in your code as well - I think those logical OR's (||) should've been AND's (&&). Otherwise if only one of those conditions holds, your loop will continue. That's not what you want - you want to pull out of the loop as soon as one of those conditions is met.
Hope that helps - post some more code up if you're still stuck ;)

[m4wk]

Oh wow, you're right about the conditional. That makes a lot more sense and looks a LOT cleaner than my messy code lol.

Well it works! I switched the conditional to what you recommended (thank you lol), and when I compiled it I had no errors. Ran it, and it listed the palindromes. I love this website, thank you keineahnung! Here was the working function:

bool isPalindrome(CharLinkD * head, CharLinkD * tail) {

        while(head != tail && head < tail)
        {
                if(head->c == tail->c)
                {
                        head = head->next;
                        tail = tail->prev;
                }

                else return false;
        }

        return true;
}

[keineahnung]

Scrap that. Need some sleep.
Your while loop just needs to do this:

while ( head < tail )
{
    // ...
} // while 

Then as soon as they're equal or cross over each other, the loop terminates.

[m4wk]

Wow, even better! Thank you.

[keineahnung]

@m4wk
thank you keineahnung! Here was the working function:

You're welcome - see you around ;)