Linked list queries

Question

I have this singly linked list:

#include <stdio.h>
#include <stdlib.h>
struct list_el {
   int val;
   struct list_el * next;
};

typedef struct list_el item;

int main() {
   item * curr, * head;
   int i, num_nodes;

   head = NULL;
   printf("Enter the number of nodes to be created: ");
   scanf("%d", &num_nodes);
   for(i=1;i<=num_nodes;i++) {
      curr = (item *)malloc(sizeof(item));
      printf("\n Enter the value :");
      scanf("%d", &curr->val);
      curr->next  = head;
      head = curr;
   }

   curr = head;

   while(curr) {
      printf("%d --> ", curr->val);
      curr = curr->next ;
   }
   getch();
   return 0;
}

What does the line urr = head; mean? Also, while printing, if prints the linked list in reverse. Why is it so? I think it is because we are assigning the last node as curr with the above statement? If yes, how the curr->next work insid ethe while (curr) loop?

Step through the code, line by line, to see what it really does (if you can't understand this very simple code). Or better yet, try to do it on paper first! — Some programmer dude

WhozCraig WhozCraig · Accepted Answer · 2013-12-03T09:43:00

In order of questions asked:

What does curr = head; mean?

It means take the address held in the pointer-variable head and store it in the pointer variable curr. It is not different than copying by-value any other type, such as int a=1, b; b=a;

(It) prints the linked list in reverse. Why is it so?

As you're adding each new item, that new item becomes the list head. therefore if you enter the numbers in a specific order, the last one will be the first one in the list, and the first will be the last. This type of structure is commonly called a LIFO (Last-In-First-Out).

If you want the list to actually be in the order entered without scanning to the end of the list with each new insertion this is one way to do it (and imho, the most efficient):

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

struct list_el
{
    int val;
    struct list_el * next;
};
typedef struct list_el item;

int main()
{
    item *curr, *head = NULL, **pp = &head;
    int i, num_nodes;

    printf("Enter the number of nodes to be created: ");
    scanf("%d", &num_nodes);

    for(i=1;i<=num_nodes;i++)
    {
        *pp =  malloc(sizeof(**pp)); // note: don't cast malloc() in C
        if (*pp == NULL)
        {
            perror("Failed to allocate node");
            exit(EXIT_FAILURE);
        }

        printf("\n Enter the value :");
        scanf("%d", &(*pp)->val);
        pp = &(*pp)->next;
    }

    // terminate the list
    *pp = NULL;

    // walk the list
    curr = head;
    while(curr)
    {
        printf("%d --> ", curr->val);
        curr = curr->next ;
    }
    getch();
    return 0;
}

How It Works

A pointer-to-pointer, pp, is used to always hold the address of the pointer that will receive the next new node allocation. Initially it starts with the address of the head pointer variable. As each new node is inserted pp is loaded with the address of the next member of that added node. When the loop is finished, it will point to the last next pointer in the list, so we set it to NULL to terminate, and we're finished.

Note that with this algorithm a special if (first-node) check is not needed with each iteration. The head pointer naturally fills in with the first node added (or is set to NULL if no nodes are added).

Finally, I left most of the (lack of) error checking for you to address, though I had to add the malloc() result check, from force of habit if nothing else. You should be checking the success of each library call made in this, particularly the scanf() calls

Input

Enter the number of nodes to be created: 5

 Enter the value :1

 Enter the value :2

 Enter the value :3

 Enter the value :4

 Enter the value :5

Output

1 --> 2 --> 3 --> 4 --> 5 -->

Linked list queries

2 Answers