Simpler and faster code for reversing list? 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).


What changes can i make to the code/the reversing algorithm?
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&lt;stdio.h&gt;
#include&lt;conio.h&gt;
#include&lt;string.h&gt;
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-&gt;item=(char*)malloc(strlen(data));
    temp-&gt;item=data;
    temp-&gt;next=NULL;
    temp-&gt;prev=NULL;
    if((*List)-&gt;item==NULL)
        (*List)=temp;
    else
    {
        while(last-&gt;next!=NULL)
            last=last-&gt;next;
        temp-&gt;prev=last;
        last-&gt;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-&gt;next!=NULL)
        last=last-&gt;next;
    temp=last;
    while(temp-&gt;prev!=NULL)
    {
        temp1-&gt;item=temp-&gt;item;
        temp1-&gt;next=temp-&gt;next;
        temp1-&gt;prev=temp-&gt;prev;
        temp-&gt;next=temp-&gt;prev;  //swap prev and next links
        temp-&gt;prev=temp1-&gt;next;
        temp=temp-&gt;next;
        if(flag1==0)  //record the last node which becomes the first node in new list
        {
            flag1++;
            flag=temp;
        }
    }
    temp1-&gt;item=temp-&gt;item;
    temp1-&gt;next=temp-&gt;next;
    temp1-&gt;prev=temp-&gt;prev;
    temp-&gt;next=NULL;
    temp-&gt;prev=temp1-&gt;next;
    (*List)=flag-&gt;prev;  //give control of the first node
    free(temp1);
};
void display(NODE *List)
{
    if(List-&gt;next==NULL)
    {
        printf("%s",List-&gt;item);
        return;
    }
    NODE *temp;
    temp=List;
    do
    {
        printf("%s&lt;--&gt;",temp-&gt;item);
        temp=temp-&gt;next;
    }while(temp-&gt;next!=NULL);
    printf("%s\n",temp-&gt;item);
}
int main()
{
    int i=0,n;
    char s[10][50];
    NODE *List;
    List=(NODE*)malloc(sizeof(NODE));
    List-&gt;item=NULL;
    List-&gt;next=NULL;
    List-&gt;prev=NULL;
    printf("Provide number of words(max 10): ");
    scanf("%d",&amp;n);
    printf("Enter string of words for the list: ");
    while(i&lt;n)
    {
        scanf("%s",s[i]);
        Insert(s[i],&amp;List);
        i++;
    }
    printf("\nOriginal List is: ");
    display(List);
    Reverse(&amp;List);
    printf("\nReversed List is: ");
    display(List);
    getch();
    return 0;
}
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 &lt;-- |p      | &lt;--- |p     | &lt;--- |p     | &lt;--- |p     |
           |      n| ---&gt; |     n| ---&gt; |     n| ---&gt; |     n| ---&gt; 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:


Naming: upper case names are usually reserved for constants. So call NODE something else: eg. Node or node.
malloc should not be cast
you malloced the string and then didn't use it.(Insert() line 5/6))
you have code to find the end of the list twice. It is a simple loop that belongs in a separate function.
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).
One variable per line.


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

#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;

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

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

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

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

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

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

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

    for (;list != NULL; list = list-&gt;next) {
        if (list-&gt;prev != NULL) {
            printf("&lt;--&gt;");
        }
        printf("%s", list-&gt;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) &amp;&amp; strcmp(s, ".")) {
        list = insert(s, list);
    }

    display("Original List is: ", list);
    list = reverse(list);
    display("Reversed List is: ", list);
    return 0;
}