Thread: not sure why links in this program are not always null

So laserlight asked me to talk about "my" linked list in the most recent thread i posted here about NULL pointers.

However, I have only made edits to someone elses linked list, and i have been torturing the code (and subsequently, myself) to try and figure out how the program actually works.

So my understanding of a linked list, is the nodes created with a struct type, and the last item on the list must always contain the NULL pointer...or else there would be no indicators of where the list begins and ends:

Code:

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

so we would have a series of nodes connected by the memory addresses for next, each link in the chain meaning two nodes are connected by next.

However, I'm still not getting why sometimes the current->next node is not NULL, but only if you have created more than one node in the program:

Code:

  //shows position and value of nodes at this point in the program
  //For some reason, curent->next stops being displayed as null after
  //you make the first node.
  printf("head value is %d, current value is %d\n", first->value, current->value);
  printf("first link: %p, current->next:"
         " %p, current: %p.\n", first->next, current->next, current);

Output:

S)how, A)dd, R)emove, Q)uit: A
Type a value: 1
head value is 1, current value is 1
first link: (nil), current->next: (nil), current: 0x55723cd1bac0.
S)how, A)dd, R)emove, Q)uit: A
Type a value: 1
head value is 1, current value is 1
first link: 0x55723cd1bae0, current->next: 0x55723cd1bae0, current: 0x55723cd1bac0.
S)how, A)dd, R)emove, Q)uit:

I know that using casts this way violates the strict C standards you get when running -Wpedantic, but this is just an educational program. It has no practical value whatsoever, even the possible applications of this type of linked list are clear. You can just run this to better understand what the program does, i created the code above myself and the diagram aspect of "show()" just to demonstrate to a user how a linked list works...but i don't understand why current->next isn't null after we have created a node. It's null when you run through the list in show:

Code:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<smanage.h>
struct node
{
  int value;
  struct node *next;
};
//pointers declared with file scope
struct node *first;
struct node *current;
struct node *previous;


struct node *create()
{
  struct node *space; 
  space = malloc(sizeof(struct node)); 


  return (space); 
}


int menu()
{
  char choice;


  printf("S)how, A)dd, R)emove, Q)uit: ");
  choice = getchar();


  purge(); 


  return (toupper(choice)); 
}


void add()
{
  //if first is NULL
  if (!first)
  {
    //make head node
    first = create(); 
    //Link current and first together
    current = first; 
  }
  else
  {
    current = first; 
    //link or re-link the nodes together until we
    //reach the end of the list
    while (current->next)
    {
      //connect current->next with current
      current = current->next; 
    }  


    //makes new current node
    current->next = create(); 
  }
  printf("Type a value: ");
  scanf("%d", &current->value); 
  purge(); 


  //shows position and value of nodes at this point in the program
  //For some reason, curent->next stops being displayed as null after
  //you make the first node.
  printf("head value is %d, current value is %d\n", first->value, current->value);
  printf("first link: %p, current->next:"
         " %p, current: %p.\n", first->next, current->next, current);
}


void show(void)
{
  if (!first)
  {
    puts("No nodes to show.");


    return;
  }


  current = first; 


  puts("Showing all nodes: "); 


  int count = 1; 
  //loop until there aren't any more nodes
  while (current)
  {
    //don't show diagram if end of list is reached
    if(!current->next)
    {
      printf("Record %i: %i at %p and %p\n"
      , count, current->value, current, current->next);


      current = current->next; 
      count++;
    }
    else 
    {
      //show diagram if loop hasn't reached the end
      printf("Record %i: %i at %p and %p\n"
             "                                    /\n"
             "                                   /\n"
             "                                  /\n" 
             "                                 /\n"
             "                                /\n"
             "                               /\n" 
             "                              /\n"
             "                             /\n" 
      , count, current->value, current, current->next);


      current = current->next; 
      count++;
    }
  }
}




void delrec(void)
{
  if (!first)
  {
    puts("No nodes to remove"); 
    return;
  }
  //use show to display node list
  puts("Choose node to remove: "); 
  show(); 


  int node, count; 
  //select node to remove, store value
  printf("node: ");
  scanf("%i", &node); 
  purge(); 
  puts("");


  count = 1; 
  //start list at first node like in
  //other functions
  current = first; 


  while (count != node)
  {
    //when user selected node is
    //reached, previous is linked with
    //current, current is linked with current->next
    previous = current; 
    current = current->next; 
    
    count++;
    //if number chosen doesn't reflect
    //real number of nodes...
    if (!current)
    {
      puts("node not found"); 


      return;
    }
  }
  //remove node by linking either
  //first or previous-> node with node past
  //the one user selected to remove
  if (!previous)
  {
    first = current->next; 
  }
  else
  {
    previous->next = current->next; 
  }  
  //user confirmation message
  printf("Node %i removed.\n", node); 
  //allow the memory allocated for that
  //node to be allocated again
  free(current); 
}


int main()
{
  int choice = 0;


  while (choice != 'Q')
  {
    choice = menu(); 


    switch (choice)
    {
      case 'S':
        show(); 
        break;
      case 'A':
        add(); 
        break;
      case 'R':
        delrec(); 
        break;
      case 'Q':
        break; 
    }
  }


  return 0; 
}

P.S.: sorry if this is too much code at once for you, but i'm not telepathic and don't know which parts of this program i should post here. Also, smanage just contains functions i use for string input, one of those functions being "purge()" which clears the buffer:

Code:

void purge()
{
while(getchar != '\n');
}

You are forgetting to set current to current->next, which not only causes current->next to not always show NULL, but also causes the list to be created incorrectly (e.g., try adding 1, 2, 3 and then show the result). So try:

Code:

    current->next = create();
    current = current->next;

Also, your create() function is not correct since it should explicitly set the next pointer to NULL (which it is not guaranteed to be). You may as well also set the value there, too:

Code:

struct node *create(int value)
{
  struct node *p = malloc(sizeof *p);
  if (!p) {
    perror("create");
    exit(EXIT_FAILURE);
  }
  p->value = value;
  p->next = NULL;
  return p;
}
 
void add()
{
  int value;
  printf("Type a value: ");
  scanf("%d", &value); 
  purge(); 
 
  if (!first)
  {
    first = create(value); 
    current = first; 
  }
  else
  {
    current = first; 
    while (current->next) current = current->next; 
    current->next = create(value);
    current = current->next;
  }
...

sorry if this is too much code at once for you, but i'm not telepathic and don't know which parts of this program i should post here

You should post all of the code when possible (like if it's less than say 500 lines). Otherwise a link to a zip (or github repo or whatever) is a good idea.

Originally Posted by john.c

You are forgetting to set current to current->next, which not only causes current->next to not always show NULL, but also causes the list to be created incorrectly (e.g., try adding 1, 2, 3 and then show the result). So try:

Code:

    current->next = create();
    current = current->next;

Also, your create() function is not correct since it should explicitly set the next pointer to NULL (which it is not guaranteed to be). You may as well also set the value there, too:

Code:

struct node *create(int value)
{
  struct node *p = malloc(sizeof *p);
  if (!p) {
    perror("create");
    exit(EXIT_FAILURE);
  }
  p->value = value;
  p->next = NULL;
  return p;
}
 
void add()
{
  int value;
  printf("Type a value: ");
  scanf("%d", &value); 
  purge(); 
 
  if (!first)
  {
    first = create(value); 
    current = first; 
  }
  else
  {
    current = first; 
    while (current->next) current = current->next; 
    current->next = create(value);
    current = current->next;
  }
...

You should post all of the code when possible (like if it's less than say 500 lines). Otherwise a link to a zip (or github repo or whatever) is a good idea.

Nice work! I didn't even notice that there was an issue with how the records were displayed, i just noticed that for some reason after running add(), the current->next pointer added wasn't NULL like i would think it should be. Just making that change with current->next in add, and also making space->next null in the create() function fixed everything.

However, I'm confused as to why outputting the position the position with the add() function gets it wrong with the way i had it before, but for some reason show() still displays the nodes the way they are meant to:

Code:

//temporarily commenting what i added from your recommendations

//space->next = NULL;
...
//current = current->next;

I would show the output in quotes, but i just tried it, and the ASCI art slashes (showing the link) are not copying over to the forum
so that it looks like it's supposed to. It does output properly on my terminal though.

So obviously, the integrity of the linked list is perfect, but something about my code before is making
it do weird things. Why is the NULL pointer where it's supposed to be in show(), but not add()?

I'm not sure what you're getting at. Your print statement in add() prints first->next where I would've expected it to print first. Is that the problem?

the ASCI art slashes (showing the link) are not copying over to the forum

The forum removes leading spaces sometimes. You could try showing it in code tags instead, which tends to keep the spacing.

EDIT:
You might want to try a structure like this. Not only does it eliminate the global variables, it also makes it easier to append nodes to the end of the list by keeping track of the tail as well as the head.

Code:

#include <stdio.h>
#include <stdlib.h>
 
#define DATA       int
#define DATAFORMAT "%d"
 
typedef struct Node {
  DATA data;
  struct Node *next;
} Node;
 
typedef struct {
  Node *head, *tail;
} List;
 
Node *listNewNode(DATA data, Node *next) {
  Node *node = malloc(sizeof *node);
  if (!node) {
    perror("nodeNew");
    exit(EXIT_FAILURE);
  }
  node->data = data;
  node->next = next;
  return node;
}
 
List *listNew() {
  List *list = malloc(sizeof *list);
  if (!list) {
    perror("listNew");
    exit(EXIT_FAILURE);
  }
  list->head = list->tail = NULL;
  return list;
}
 
void listClear(List *list) {
  for (Node *cur = list->head, *next = NULL; cur; cur = next) {
    next = cur->next;
    free(cur);
  }
  list->head = list->tail = NULL;
}
 
void listFree(List **list) {
  listClear(*list);
  free(*list);
  *list = NULL;
}
 
void listPrepend(List *list, DATA data) {
  list->head = listNewNode(data, list->head);
  if (!list->tail) list->tail = list->head;
}
 
void listAppend(List *list, DATA data) {
  Node *node = listNewNode(data, NULL);
  if (list->tail) list->tail->next = node;
  else            list->head       = node;
  list->tail = node;
}
 
void listShow(List *list) {
  for (Node *node = list->head; node; node = node->next)
    printf(DATAFORMAT " ", node->data);
  printf("\n");
}
 
int main() {
  List *list = listNew();
 
  for (int i = 0; i <  5; ++i) listPrepend(list, i); // add to head
  for (int i = 5; i < 10; ++i) listAppend(list, i);  // add to tail
 
  listShow(list); // 4 3 2 1 0 5 6 7 8 9
  
  listFree(&list);
  return 0;
}

Originally Posted by john.c;1309153[COLOR=#333333

I'm not sure what you're getting at. Your print statement in add() prints [/COLOR]first->next where I would've expected it to print first. Is that the problem?

the ASCI art slashes (showing the link) are not copying over to the forum


The forum removes leading spaces sometimes. You could try showing it in code tags instead, which tends to keep the spacing.]

Yeah, i can't really show you what i am getting at without the correct spacing, as that was the point of the very simple ascii art in the program. I'll try with code tags:

Code:

S)how, A)dd, R)emove, Q)uit: A
Type a value: 1
head value is 1, current value is 1
first link: (nil), current->next: (nil), current: 0x55e326170ac0.
S)how, A)dd, R)emove, Q)uit: A
Type a value: 2
head value is 2, current value is 2
first link: 0x55e326170ae0, current->next: 0x55e326170ae0, current: 0x55e326170ac0.
S)how, A)dd, R)emove, Q)uit: S
Showing all nodes:  
Record 1: 2 at 0x55e326170ac0 and 0x55e326170ae0
                                    /
                                   /
                                  /
                                 /
                                /
                               /
                              /
                             /
Record 2: 0 at 0x55e326170ae0 and (nil)

This is how the original version of my program that I've posted, without your changes. Notice how the values in the list are not assigned properly, but when you run show() they are. The last item has the NULL pointer like it should. It confuses me why the show() loop corrects the mistake. The behavior of the badly assigned nodes is consistent, no matter whether you delete nodes or add whatever number. Add() prints the memory addresses incorrectly, but show() somehow makes current->next NULL.

I'm posting the code again so it looks neater, I removed all the comments with sed and commented out the changes you recommended which fix the program:

Code:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<smanage.h>
struct node
{
  int value;
  struct node *next;
};
struct node *first;
struct node *current;
struct node *previous;


struct node *create()
{
  struct node *space; 
  space = malloc(sizeof(struct node)); 


  //space->next = NULL;


  return (space); 
}


int menu()
{
  char choice;


  printf("S)how, A)dd, R)emove, Q)uit: ");
  choice = getchar();


  purge(); 


  return (toupper(choice)); 
}


void add()
{
  if (!first)
  {
    first = create(); 
    current = first; 
  }
  else
  {
    current = first; 
    while (current->next)
    {
      current = current->next; 
    }  


    current->next = create(); 
    //current = current->next;
  }
  printf("Type a value: ");
  scanf("%d", &current->value); 
  purge(); 


  printf("head value is %d, current value is %d\n", first->value, current->value);
  printf("first link: %p, current->next:"
         " %p, current: %p.\n", first->next, current->next, current);
}


void show(void)
{
  if (!first)
  {
    puts("No nodes to show.");


    return;
  }


  current = first; 


  puts("Showing all nodes: "); 


  int count = 1; 
  while (current)
  {
    if(!current->next)
    {
      printf("Record %i: %i at %p and %p\n"
      , count, current->value, current, current->next);


      current = current->next; 
      count++;
    }
    else 
    {
      printf("Record %i: %i at %p and %p\n"
             "                                    /\n"
             "                                   /\n"
             "                                  /\n" 
             "                                 /\n"
             "                                /\n"
             "                               /\n" 
             "                              /\n"
             "                             /\n" 
      , count, current->value, current, current->next);


      current = current->next; 
      count++;
    }
  }
}




void delrec(void)
{
  if (!first)
  {
    puts("No nodes to remove"); 
    return;
  }
  puts("Choose node to remove: "); 
  show(); 


  int node, count; 
  printf("node: ");
  scanf("%i", &node); 
  purge(); 
  puts("");


  count = 1; 
  current = first; 


  while (count != node)
  {
    previous = current; 
    current = current->next; 
    
    count++;
    if (!current)
    {
      puts("record not found"); 


      return;
    }
  }
  if (!previous)
  {
    first = current->next; 
  }
  else
  {
    previous->next = current->next; 
  }  
  printf("record %i removed.\n", node); 
  free(current); 
}


int main()
{
  int choice = 0;


  while (choice != 'Q')
  {
    choice = menu(); 


    switch (choice)
    {
      case 'S':
        show(); 
        break;
      case 'A':
        add(); 
        break;
      case 'R':
        delrec(); 
        break;
      case 'Q':
        break; 
    }
  }


  return 0; 
}

Sorry man, but I still don't get it. As far as I can see it's printing exactly what you are asking it to print and the add() output and show() output match up exactly as I would expect considering that "current = current->next" is commented out (and considering that, by lucky haps, the next pointers are defaulting to NULL).

BTW, your purge code is incorrect. I assume in the code for it you showed earlier, the missing parens on getchar is just a typo. However, you should check for EOF as well as '\n', otherwise it will hang on EOF.

Code:

void purge()
{
  int ch;
  while ((ch = getchar()) != '\n' && ch != EOF) ;
}

I agree with Linus Torvalds that Hungarian notation (of the Systems type, which you are advocating) is brain-damaged.
Hungarian notation - Wikipedia

And it is not easier to read a program with main at the top, unless you are used to it and not intelligent enough to adapt. Mindless analogies to "fallen leaves" have no bearing on the matter.