Using Linked Lists in C

Question

I'm learning programming in C language and I face some troubles, especially when working with pointers. It's a little bit difficult for me since we don't use pointers in Java or C#.

What I try to do is to create a linked list (code found on the internet) and to push elements in it. Like in the code below.

What happens is that when I uncomment the second line of code, the code works but I receive the following list as answer {0, 1, 2}, even if I don't push the number 0 in the list. I would like to have this as answer: {1, 2}.

int main (){
    node_t * test_list = NULL;

    //test_list = malloc(sizeof(node_t));

    push(test_list, 1);
    push(test_list, 2);

    print_list(test_list);

    return 0;
}

This is how the code looks like:

typedef struct node
{
  int val;
  struct node * next;
}              node_t;

void print_list(node_t * head)
{
  node_t * current = head;

  while (current != NULL)
    {
      printf("%d\n", current->val);
      current = current->next;
    }
}

node_t* new_node(node_t * head)
{
  node_t * head2 = malloc(sizeof(node_t));

  return  head2;
}

void push(node_t * head, int val)
{
  if (head == NULL)
    {
      head = new_node(head);
      head->val = val;
      head->next = NULL;
    }
  else
    {
      node_t * current = head;
      while (current->next != NULL)
          current = current->next;

      /* now we can add a new variable */
      current->next = malloc(sizeof(node_t));
      current->next->val = val;
      current->next->next = NULL;
    }
}

In the push function, I decided to check whether the head is equal to NULL or not. If it's the case, I just want to create a new node and assign it to it. I don't know if it's a good approach. Nevertheless, it is not working.

I would be thankful if someone could guide me to the right path!

Thank you!

(Source of the code: http://www.learn-c.org/en/Linked_lists )

Did you step through the code, line-by-line in the debugger? You are also trying to assign a pointer in push() for head, which is not going to work. Everything in C is pass-by-value. — OldProgrammer
– OldProgrammer, Commented Aug 13, 2015 at 17:20
The modified head in push is not finding its way back to the caller, because you pass it a copy . — Weather Vane
– Weather Vane, Commented Aug 13, 2015 at 17:23
No I did not step through the code with the debugger. But if I uncomment the following line //test_list = malloc(sizeof(node_t)); from the main function, it adds an extra element to the list (the element 0), which I don't want. That's the reason why I tried to make it work with the function new_node(...), but it is not working. — Moh Za
– Moh Za, Commented Aug 13, 2015 at 17:25
suggest consistency in code formatting, so us humans can easily read/understand it. 1) always indent after every opening brace '{' 2) always un-indent before every closing brace '}' 3) never use tabs for indenting as every editor/wordprocessor has different tab widths/tab stops. 4) insert a blank line around each code block 5) add comments so the person reading the code knows what the author thinks they are doing — user3629249
– user3629249, Commented Aug 13, 2015 at 18:05

Violeta Marin · Accepted Answer · 2015-08-13 18:09:10Z

1

I'll try to give an explanation of the extra element 0.

test_list = malloc(sizeof(node_t)); //this changes the pointer test_list                
                                    //which is initially NULL to a non-NULL pointer, hence the mysterious extra element "0"

 push(test_list, 1);

void push(node_t * head, int val) {
if (head == NULL) //head is not NULL at this point because you called malloc earlier on it, so 1 will be inserted in the next position
{...}

You should initialize the head of the list with some value, after malloc:

test_list = malloc(sizeof(node_t));


head->val = 5; //some value
head->next = NULL;

push(test_list, 1);
...

Now, the first element won't be 0, it will be 5.

edited Aug 13, 2015 at 18:09

answered Aug 13, 2015 at 17:51

Violeta Marin

903 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Moh Za Over a year ago

If I uncomment the line //test_list = malloc(sizeof(node_t)); in my main function, even if I don't push elements in the linked list, the mysterious element '0' will appear.

Violeta Marin Over a year ago

Exactly, because malloc assigns a value to your NULL pointer and initializes it to 0, even though that's not guaranteed (use calloc for 0-initializing).

Violeta Marin Over a year ago

Also, if you look carefully at the source of your code, you'll see, that after malloc, the structure is initialized with some values: node_t * head = NULL; head = malloc(sizeof(node_t)); head->val = 1; head->next = NULL;

user3275158 · Accepted Answer · 2015-08-13 19:02:26Z

When you have uncommented the below line in your code

//test_list = malloc(sizeof(node_t));

Here you are allocating the head pointer before calling your push functions. So, the below lines of code will never get executed

 if (head == NULL)
    {
        head = new_node(head);
        head->val = val;
        head->next = NULL;}

Since you have malloced once for head pointer and you have not initialized it and followed by two push functions. So you will see 0/garbage,1,2 instead of 1,2 in your list.

And when you have commented the malloc for test_list, then in the below piece of code

if (head == NULL)
    {
        head = new_node(head);
        head->val = val;
        head->next = NULL;
    }else
    {

        node_t * current = head;
        while (current->next != NULL) {
            current = current->next;
        }

Since you are not sending the address of test_list(&test_list-you need to use double pointer)any changes done to head in if case will not be reflected in test_list.

Go through the link for clear understanding- linked_list

Vlad from Moscow · Accepted Answer · 2015-08-13 17:56:43Z

0

Try the following functions.

node_t * new_node( int val )
{
    node_t * n = malloc( sizeof( node_t ) );

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

    return  n;
}

void push( node_t **head, int val ) 
{
    node_t *n = new_node( val );

    if ( n )
    {
        while ( *head ) head = &( *head )->next;
        *head = n;
    }
}

Function push must be called like

push( &test_list, 1 );

As for your function push implementation then it deals with a copy of test_list. So the original value of test_list is not changed.

edited Aug 13, 2015 at 17:56

answered Aug 13, 2015 at 17:44

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

3 Comments

mah Over a year ago

Given what his code currently looks like, I'm pretty sure your suggestion is not going to be useful to him without a bit more of a complete solution (i.e., a full usage example) (which is not a reflection on you/your answer, but rather on the broad nature of this question).

Vlad from Moscow Over a year ago

@mah What I showed is enough thet to resolve the problem with padding new elements to the list. So I do not understand the sense of your comment.

Moh Za Over a year ago

@VladfromMoscow Your code is working perfectly. Thank you very much!

BEPP · Accepted Answer · 2015-08-13 18:21:36Z

Already Vlad from Moscow and Violeta Marin posted the reason why it not works.I made some changes In your code to make it work,

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

  typedef struct node
  {
     int val;
     struct node * next;
  } node_t;

  void print_list(node_t * head) 
  {
      node_t * current = head;
      printf("called\n");
      while (current != NULL) {
         printf("%d\n", current->val);
         current = current->next;
      }
  }


  node_t* new_node()
  {
     //you have to return NULL , if malloc fails to allocate memory 
     node_t * head2 = malloc(sizeof(node_t));
     return  head2;
  }

  void push(node_t **head, int val)
  {
      if (*head == NULL)
      {
          printf("null\n");  
         //you have to check the return value of new_node
         (*head) = new_node();
         (*head)->val = val;
         (*head)->next = NULL;
      }
      else {
          printf("not null\n");
          node_t * current = *head;

          while (current->next != NULL) {
              current = current->next;
          }
          /* now we can add a new variable */
          //you have to check the return value of malloc
          current->next = malloc(sizeof(node_t));
          current->next->val = val;
          current->next->next = NULL;
       }
  }

  void my_free(node_t *head)
  {
    node_t *temp= NULL;
    while(head) 
    {
       temp=head->next;
       free(head);
       head=temp;
    }
}
int main ()
{
   node_t *test_list = NULL;
   push(&test_list, 1);
   push(&test_list, 2);
   print_list(test_list);
   my_free(test_list);
   return 0;
}

user3629249 · Accepted Answer · 2015-08-13 18:50:38Z

the following code:

1) corrects several oversights in the posted code
2) works correctly
3) contains the logic that (generally) is always used to 
   add a node to the end of a linked list
4) demonstrates that to change the contents of a passed in pointer
   the simplest way is to pass '**' 
   and the caller passes the address of the pointer, not the contents of the pointer
5) uses consistent formatting
6) avoids unnecessary/misleading clutter/confusion in the definition of the struct
7) removes unnecessary parameters from functions
8) properly prototypes the functions 
   notice that the new_node() function prototype has '(void)'
   while the actual function body just has '()'

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

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

// prototypes
void          print_list( struct node * head);
struct node * new_node( void );
void          push( struct node ** head, int val);


int main ( void )
{

    struct node * test_list = NULL;

    push(&test_list, 1);
    push(&test_list, 2);

    print_list(test_list);

    return 0;
} // end function: main


// step through linked list, printing the val field from each node
void print_list( struct node * head)
{
    struct node * current = head;

    while (current != NULL)
    {
        printf("%d\n", current->val);
        current = current->next;
    }
} // end function: print_list


// create a new node
struct node * new_node()
{
    struct node * head2 = NULL;

    if( NULL == (head2 = malloc(sizeof( struct node))))
    { // then malloc failed
        // handle error, cleanup, and exit
    }

    return  head2;
} // end function: new_node


// append a new node to end of linked list
// need to use '**' so actual pointer in main() will be updated
void push( struct node ** head, int val)
{
    struct node * current = NULL;

    if (*head == NULL)
    { // then list is empty
        current = new_node();
        current->val = val;
        current->next = NULL;
        *head = current;
    }

    else
    {
        current = *head;

        while (current->next != NULL)
        {
            current = current->next;
        }

        /* now we can append a new node to linked list */
        current->next = new_node();
        current->next->val = val;
        current->next->next = NULL;
    }
} // end function: push

Collectives™ on Stack Overflow

Using Linked Lists in C

5 Answers 5

3 Comments

Comments

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

Comments

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related