printing linked list from begining

Question

I got the code from wikipedia for linked list ( http://en.wikipedia.org/wiki/Linked_list ).

But it prints the result in reverse order (5 4 3 2 1 ). How to make this to print from begining ( 1 2 3 4 5).

Answer 1

I assume you're talking about the C implementation in "Language support".

It doesn't print in reverse order. It's because elements are inserted in the head of the list, so inserting 1, 2, 3 would result in a list that contains 3, 2, 1.

This is because the list is represented by its head, so it's faster inserting at the head than the tail. To insert at the tail you would have to go through the entire list. This makes insertion O(n) instead of O(1).

Seeing as this is a singly-linked list, you cannot print it in the other order because you can only step forward.

Answer 2

That is because the way the list is constructed.

To print it in reverse, just recurse to the last entry and print from there.

Answer 3

Looking at the following example:

/****************************************************************/
/*  Function: Add an element to our list                        */
/*                                                              */
/*   Parameters: **p is the node that we wish to insert at.     */
/*               if the node is the null insert it at the beginning    */
/*               Other wise put it in the next space                   */


LLIST *list_add(LLIST **p, int i)
{
    if (p == NULL)           /*checks to see if the pointer points somewhere in space*/
        return NULL;

    LLIST *n = malloc(sizeof(LLIST));   /* creates a new node of the correct data size */
    if (n == NULL)
        return NULL;

    n->next = *p; /* the previous element (*p) now becomes the "next" element */
    *p = n;       /* add new empty element to the front (head) of the list */
    n->data = i;

    return *p;
}

Elements are being added to the beginning of the linked list when you call list_add. This is for efficiency reasons; you don't have to transverse the entire linked list to insert an element (which you would have to do if you wanted to append).

To print in reverse, you can use recursion, build your own stack (which is the blind man's recursion), or recreate the list in reverse. A recursive version:

void list_print_reverse(LLIST *n)
{
    if (n == NULL)
    {
        printf("list is empty\n");
        return;
    }

    if (n->next != NULL)
    {
        list_print_reverse(n->next);
    }

    printf("print %p %p %d\n", n, n->next, n->data);
}

Answer 4

The order in which list is being printed is the order in which elements are present in the list. You can print it in reverse order (i.e in order in which elements were inserted) using recursion. following code will print the list in reverse order

void list_print(LLIST *n) {
if (n == NULL)
{
printf("list is empty\n");
return;
}
}

void print_recursive(LLIST *n) {
if(n->next==NULL)
printf("%d\n",n->data);
else
print_recursive(LLIST n->next);
}

Answer 5

I have this program which prints a string in reverse using recursion. Can you please use your linked list as input to it?

void reversePrint(char *str)
{
if(*str == '\0')
return;
reversePrint(str+1);
printf("%c",*str);
}
int main()
{
char *input;
input = malloc(10);
strcpy(input,"wolfrevo");
reversePrint(input);
}

I can change it myself, but hope it will be a nice excercise for you.

Hints:

1. Pass linked list instead of string // Change the protype too
2. Check for list being NULL
3. Recurse by pass next element of Linked list
4. Print the data inside list instead of string

Answer 6

You can also try a double-linked list. Basically, you have an additional pointer to the previous element

typedef struct node {
    int data;
    struct node *next;     /* pointer to next element in list */
    struct node *previous; /* pointer to previous element in list */
} node;

typedef struct list {
    node *head;            /* first element in list */
    node *tail;            /* last element in list */
} list;

You can then print the list from the head and/or from the tail.