How does this linked list work?

[antirsi96]

I am currently learning linked lists and I cannot figure something out. Why don't i need to print the last element n->data after the while loop? Why is it printed within the while loop even though the loop will stop if the node is null.

struct node{
   int data;
   node* next;
};

int count(node* n){
   int c = 0;
   while(n->next != 0)
      if(n->next == 0) break;
      else{
	 c++;
	 n = n->next;
      }
   return c;
}

int main(){
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
   
   node* root = new node; node* n;
   root->next = 0;
   
   int i;
   
   n = root;
   while(scanf("%d", &i) != EOF){
      n->data = i;
      n->next = new node;
      n = n->next;
   }
   n = 0;

   n = root;
   
   if(n!=0)
   while(n->next != 0){
      printf("%d\n", n->data);
      n = n->next;
   }
   
   n = root;
   int size = count(n);

   printf("The number of elements is: %d\n", size);
   free(root);
   return 0;
}

[helios]

The loop is incorrect, or at the very least unorthodox.

//Note: outside if removed
while(n){
   printf("%d\n", n->data);
   n = n->next;
}

[dhayden]

Why don't i need to print the last element

Because the last element contains garbage. Consider the case where you input one element:
- line 21 creates the first element.
- line 28 puts the data in the first element
- line 29 creates a second element.
By the way, that second element is uninitialized.

To start, create a constructor for node:

node::node(int i) :
   data(i),
   next(NULL)
{;}

Next you should create exactly as many elements as you need in the list. That means initializing root to NULL and creating the node after you read the value for it.

To create the list, you need to handle the case where the list is empty:

node *root = NULL;
node *last = NULL; // points to last item in list, or NULL
while(scanf("%d", &i) != EOF){
   node *n = new node(i)
   if (last) {
      last->next = n;   // list isn't empty. Add n to the end.
   } else {
      root = n;   // list is empty, make n the root
   }
   last = n;
}

Since this isn't he beginner forum, I'll point out that you can simplify the code by using a pointer to the current pointer instead of a "last" pointer:

node *root = NULL;
node **pp = &root;   // Points to root or the last node's "next" pointer.
while(scanf("%d", &i) != EOF){
   node *n = new node(i);
   *pp = n;
   pp = &n->next;
}

Finally, you'll have to change count() and the loop at lines 37-40 to deal with the fact that the list contains exactly the right number of items.


Speaking of count(), line 9 doesn't do anything. Line 8 guarantees that n->next is not NULL inside the loop.