Simpler and faster code for reversing list?

Question

I wrote the 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<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;
        temp->prev=temp1->next;
        temp=temp->next;
        if(flag1==0)
        {
            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;
    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;
}

This might better be posted on http://codereview.stackexchange.com/, ?SO is generally somewhat hostile to code reviews. — High Performance Mark, Oct 27 '12 at 12:37
[Don't cast the return value of `malloc()`.](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — , Oct 27 '12 at 12:39

score 5 · Answer 1 · answered Oct 27 '12 at 12:39

5

Since it's a double-linked list you could just write two traversal functions. One forward and one reverse. Save two anchors for your list in your control structure: one for the first element and one for the last.

answered Oct 27 '12 at 12:39

Sergey L.

21,822
5
49
75

score 3 · Answer 2 · answered Oct 27 '12 at 12:39

3

You can just swap the next and previous pointers for each node and swap tail and head pointers.

answered Oct 27 '12 at 12:39

SomeWittyUsername

18,025
3
42
85

score 1 · Accepted Answer · answered Oct 27 '12 at 13:18

void reverse (struct node *ptr)
{
struct node *tmp, *kid;

if (!ptr) return;

for (kid = ptr->next; kid; kid = kid->prev) {
        tmp = kid->prev;
        kid->prev = kid->next;
        kid->next = tmp;
        }

for (kid = ptr->prev; kid; kid = kid->next) {
        tmp = kid->prev;
        kid->prev = kid->next;
        kid->next = tmp;
        }

tmp = ptr->prev;
ptr->prev = ptr->next;
ptr->next = tmp;

return;
}

Note: I removed the typedef. I hate typedefs.

Simpler and faster code for reversing list?

3 Answers3