Member Avatar for red devils

Hi,

i'm new to C programming and i could use some help with an assignment. i would like to store a word in a linked list, with each letter of the word in a separate node of the linked list. i would then like to traverse the linked list to check whether the word is a palindrome. the nodes in the palindrome should be double pointer nodes.

i'm not quite sure how to start here, any assistance will be appreciated.

  • 4 Contributors
  • 7 Replies
  • 187 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by red devils

Dani AI

Generated

A concise, practical plan that builds on and : store one character per doubly-linked node, keep both head and tail, and walk inward from both ends — no full-length pass required. Normalize input first if a case-insensitive or punctuation-ignoring palindrome check is desired (use tolower / isalnum); cast characters to unsigned char before calling ctype macros to avoid undefined behavior.

Example helper functions (allocation checks and freeing omitted for brevity):

#include <ctype.h>
#include <stdlib.h>

typedef struct Letter {
    char ch;
    struct Letter *next;
    struct Letter *prev;
} Letter;

Letter *append_letter(Letter **head, Letter **tail, char c) {
    Letter *n = malloc(sizeof *n);
    if (!n) return NULL;
    n->ch = c;
    n->next = NULL;
    n->prev = *tail;
    if (*tail) (*tail)->next = n; else *head = n;
    *tail = n;
    return n;
}

int is_palindrome(Letter *head, Letter *tail) {
    Letter *L = head, *R = tail;
    while (L && R && L != R && L->next != R) {
        if (L->ch != R->ch) return 0;
        L = L->next;
        R = R->prev;
    }
    if (L && R && L->ch != R->ch) return 0;
    return 1;
}

Notes and common pitfalls:

  • Always check malloc results and free the list on error to avoid leaks.
  • Maintain head and tail when appending/removing nodes; forgetting to update either causes dangling pointers or lost nodes.
  • For normalization (case/punctuation), iterate the source string, skip non-alphanumerics and push tolower((unsigned char)c) into the list.
  • The loop termination used above handles empty, single, even- and odd-length lists without computing length. Off-by-one errors usually come from wrong loop conditions; the L != R && L->next != R pattern prevents missing the middle comparison.

Alternatives: copying characters into a plain array or reversing the second half of a singly linked list can be simpler for short assignments. Time complexity is O(n); extra memory is O(1) with the two-pointer doubly-linked approach. For Unicode or multi-byte input, a different representation is required.

Recommended Answers

All 7 Replies

Member Avatar for Ancient Dragon

First you have to declare a structure that is each node. If you search for "linked lists" you will get lots of examples, such as this tutorial by Stanford University.

Member Avatar for red devils

i'll check the tutorial and see if that helps.

Member Avatar for Luckychap

First create a doubly link list. A doubly link list with each nodes having the address of next and previous node. The structure of the such node is as follows:

struct node {
        char data;
        node *next;
        node *prev;
};

Then write some functions to add, delete and traverse etc And what write functions for what u exactly want.

Member Avatar for red devils

thanks. each node is supposed to store one character of the entered word. the first and last letters of the word would then be compared and if the same, then the second would be compared to the second to last etc. what would be the best way to do this?

Member Avatar for Luckychap

Ok!!

One thing more, you have to maintain two pointers..head and tail. Which will have the addresses of first and last node respectively.

And write a function which will count the length of the link list (ie number of characters).

Once that is done you can loop through the list in this way:

//Assuming that head and tail are global
int isPalindrome() {
       node *tempHead = head;
       node *tempTail = tail;
     
       //function to calculate the length of link list
       int length = getLength();
       int i = 0;
       for(;i<length/2;i++) {
             if(tempHead->data != tempTail->data)
                  return 0;
       
             tempHead = tempHead->next;
             tempTail = tempTail->prev;
      }
      return 1;
}

Hope u got it.

Member Avatar for Adak

<deleted>

Member Avatar for red devils

Thanks a whole lot man!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.