2
\$\begingroup\$

I wrote this code for reversing a doubly linked list containing words in each node, which works perfectly fine. My teacher says the algorithm is difficult to understand and the code as a whole could be made more efficient(reducing overhead and memory consumption).

  1. What changes can i make to the code/the reversing algorithm?
  2. Also is there a way I could input the sentence without having to ask the number of words in advance?

Here is the code:

#include<stdio.h>
#include<conio.h>
#include<string.h>
typedef struct NODE
{
    char *item;
    struct NODE *next;
    struct NODE *prev;
}NODE;
void Insert(char data[],NODE **List)
{
    NODE *temp,*last;
    last=(*List);
    temp=(NODE*)malloc(sizeof(NODE));
    temp->item=(char*)malloc(strlen(data));
    temp->item=data;
    temp->next=NULL;
    temp->prev=NULL;
    if((*List)->item==NULL)
        (*List)=temp;
    else
    {
        while(last->next!=NULL)
            last=last->next;
        temp->prev=last;
        last->next=temp;
        last=temp;
    }
}
void Reverse(NODE **List)
{
    int flag1=0;
    NODE *temp,*temp1,*last,*flag;
    temp1=(NODE*)malloc(sizeof(NODE));
    last=(*List);
    while(last->next!=NULL)
        last=last->next;
    temp=last;
    while(temp->prev!=NULL)
    {
        temp1->item=temp->item;
        temp1->next=temp->next;
        temp1->prev=temp->prev;
        temp->next=temp->prev;  //swap prev and next links
        temp->prev=temp1->next;
        temp=temp->next;
        if(flag1==0)  //record the last node which becomes the first node in new list
        {
            flag1++;
            flag=temp;
        }
    }
    temp1->item=temp->item;
    temp1->next=temp->next;
    temp1->prev=temp->prev;
    temp->next=NULL;
    temp->prev=temp1->next;
    (*List)=flag->prev;  //give control of the first node
    free(temp1);
};
void display(NODE *List)
{
    if(List->next==NULL)
    {
        printf("%s",List->item);
        return;
    }
    NODE *temp;
    temp=List;
    do
    {
        printf("%s<-->",temp->item);
        temp=temp->next;
    }while(temp->next!=NULL);
    printf("%s\n",temp->item);
}
int main()
{
    int i=0,n;
    char s[10][50];
    NODE *List;
    List=(NODE*)malloc(sizeof(NODE));
    List->item=NULL;
    List->next=NULL;
    List->prev=NULL;
    printf("Provide number of words(max 10): ");
    scanf("%d",&n);
    printf("Enter string of words for the list: ");
    while(i<n)
    {
        scanf("%s",s[i]);
        Insert(s[i],&List);
        i++;
    }
    printf("\nOriginal List is: ");
    display(List);
    Reverse(&List);
    printf("\nReversed List is: ");
    display(List);
    getch();
    return 0;
}
\$\endgroup\$
5
\$\begingroup\$

Your code has some issues from my perspective. The first that jumps out is that you are passing a pointer to a pointer to a list. This is one level of indirection too many. Just pass a pointer to the list. To make this easier, your list pointer in main() should just be a pointer to the first entry in the list; it should not be the first entry. In other words don't malloc space for a NODE in main().

So when you construct the list it will look like this:

 first _____
            |
            v
            -------       -------       -------       -------
  NULL <-- |p      | <--- |p     | <--- |p     | <--- |p     |
           |      n| ---> |     n| ---> |     n| ---> |     n| ---> NULL
            -------       -------       -------       -------

To reverse this list, you could take the approach given by @iaimtomisbehave, from earlier. But this has two notable points: It needs a last pointer to the end of the list (this might be a plus) as well as first (or start/end); if you just swap last and first then you haven't really reversed the list because to traverse the list you now have to follow the prev pointers instead of following the next pointers. But there is a simple solution: just swap the prev and next pointers of each node as well as swapping first and last.

Some other points:

  1. Naming: upper case names are usually reserved for constants. So call NODE something else: eg. Node or node.

  2. malloc should not be cast

  3. you malloced the string and then didn't use it.(Insert() line 5/6))

  4. you have code to find the end of the list twice. It is a simple loop that belongs in a separate function.

  5. Add some space to make the code look less cramped. Note that while, for, if etc are special and deserve to be followed by an extra space: eg while (condition) (this is just my preference; others may disagree).

  6. One variable per line.

That's enough I think :-) Here is my version of your program, for what it is worth.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct Node
{
    char *item;
    struct Node *next;
    struct Node *prev;
} Node;

static Node *last_node(Node *list)
{
    while (list->next != NULL) {
        list = list->next;
    }
    return list;
}

static Node *insert(char *data, Node *list)
{
    Node *node = malloc(sizeof(Node));
    /* should handle malloc/strdup failure... */
    node->item = strdup(data);
    node->next = NULL;

    if (list == NULL) {
        list = node;
        node->prev = NULL;
    }
    else {
        Node *last = last_node(list);
        node->prev=last;
        last->next=node;
        last = node;
    }
    return list;
}

static Node *reverse(Node *list)
{
    Node *last = NULL;

    for (;list != NULL; list = list->prev) {
        Node *prev = list->prev;
        list->prev = list->next;
        list->next = prev;
        last = list;
    }
    return last;
}

static void display(const char *msg, Node *list)
{
    printf("%s\n", msg);

    for (;list != NULL; list = list->next) {
        if (list->prev != NULL) {
            printf("<-->");
        }
        printf("%s", list->item);
    }
    printf("\n");
}

int main(int argc, char ** argv)
{
    char s[50];
    Node *list = NULL;
    (void) argc;
    (void) argv;

    printf("Enter string of words for the list.  "
           "End the list with a full-stop on a blank line: ");
    while ((scanf("%49s", s) == 1) && strcmp(s, ".")) {
        list = insert(s, list);
    }

    display("Original List is: ", list);
    list = reverse(list);
    display("Reversed List is: ", list);
    return 0;
}
\$\endgroup\$
3
\$\begingroup\$

For the part where you don't need to ask the user for the number of words perhaps ask the user to terminate it with a full stop and take the input until a '.' is encountered.

\$\endgroup\$
2
\$\begingroup\$

Two minor changes will help reduce the amount of code you are writing and make it a little more efficient. This is how your code assumes the structure should be.

----------
| Start  |
----------
  ||
  \/
----------          -----------          ----------          ----------
| First  |   <==>   | Second  |   <==>   | Third  |   <==>   | Last   |
----------          -----------          ----------          ----------

Instead you can do this, maintain a pointer to the last node and add a parameter to Reverse method that accepts what direction you want to traverse in.

----------                                                   ----------
| Start  |                                                   | End    |
----------                                                   ----------
  ||                                                            ||
  \/                                                            \/
----------          -----------          ----------          ----------
| First  |   <==>   | Second  |   <==>   | Third  |   <==>   | Last   |
----------          -----------          ----------          ----------

So making these changes you will end up with a last node pointer that are set in your main and insert method.

NODE *last;

Now the reverse method should be fairly easy, just traversing in either direction based on the second parameter. If you teacher insists on this as not truly reversing the list you can use the last node to simplify the reverse logic you currently have. Also notice when you are inserting a new node you don't need to traverse all the way to the end.

The rest of the code looks fine. You may want to pay attention to bounds checking, for example will the display code work for an empty list, a list with just one node.

\$\endgroup\$
1
\$\begingroup\$

Your code is fine overall, but there are a few things to notice:

  1. conio.h is a properitary header that is not available on all systems. Avoid using it. There is a function similiar to getch available in the standard headers, where it is called getchar.
  2. Include stdlib.h for malloc
  3. Don't append semicolons to the closing brace of a function definition (as in Reverse)
  4. Always turn on warnings when compiling. I compiled your code with the GNU C compiler (gcc) which gave me the following warnings:

    reverse.c: In function 'main':
    reverse.c:88:10: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
    reverse.c:92:14: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
    reverse.c: In function 'Reverse':
    reverse.c:59:17: warning: 'flag' may be used uninitialized in this function [-Wuninitialized]
    

    The first warning is about the fact that you don't check the return values of your calls to scanf. What happens if the user doesn't input a number? Better check for that case. The other warning is about your function Reverse. What happens if temp->prev==0 from the beginning on? In that case, you while-loop is never executed and flag remains undefined, probably letting your program crash.

    Checking for such things is important to catch subtile errors. If the compiler issues a warning but you're sure that it's errorneous, making a comment is a good idea.

To request only a certain amount of words, you could consider terminating the input with an empty line; when you encounter the sequence \n\n, terminate the input.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.