Linked list Pointer

Question

I am learning C and I've come up with a conceptual question about pointers.
Here is a simple code to push (add to the beginning) an int to a linked list in C.

The following code works:

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

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

void push(node_t **head, int val) {
  // head is a pointer to the pointer of the first node_t
  node_t *new_node; // new pointer to a node
  new_node = (node_t *)malloc(sizeof(node_t));

  new_node->val = val;
  new_node->next = *head;
  *head = new_node;
}

int main() {
  // creating the first node
  node_t *head;
  head = (node_t *)malloc(sizeof(node_t));
  head->val = 2;
  head->next = NULL;
  
  // pushing a value
  push(&head, 1); // the '&' is important

  return 0;
}

As you notice, we have to pass &head as a parameter. So I though changing the function so I could pass head instead. Here's the modified function :

void push(node_t *head, int val) {
  node_t **p_head;
  p_head = &head; // p_head is a pointer to the pointer of the first node_t

  node_t *new_node; // pointer to a new node
  new_node = (node_t *)malloc(sizeof(node_t));

  new_node->val = val;
  new_node->next = *p_head;
  *p_head = new_node;
}

Why does this version won't work ? Thanks in advance.

Answer 1

You should be able to pass along the structure's pointer for the creation of another structure in a linked list. I would suggest looking at the linked list structure in a slightly different way.

Usually, in the creation of a linked list, whenever a new list item (aka structure in your case) is created, the "next node structure" pointer is set to null and the previous linked list member has its "next node structure" pointer updated to the pointer of the newly created structure. Making some revisions to your program I store some additional information in your structure and produce a linked list of ten members. Following is the revised code.

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

typedef struct node
{
    int val;
    struct node *previous;  /* Added this to use with the passed node pointer */ 
    struct node *next;
} node_t;

node_t * push(node_t *nd, int val)   /* Return the pointer of the newly created node */
{
    node_t *new_node; // New pointer to a node
    new_node = (node_t *)malloc(sizeof(node_t));
    new_node->val = val;
    new_node->previous = nd;
    new_node->next = NULL;

    return new_node;
}

int main()
{
    node_t *work;  // Pointer work variable for building a linked list of nodes

    node_t *head;
    head = (node_t *)malloc(sizeof(node_t));
    head->val = 2;   /* This value will get adjusted to provide unique values */
    head->previous = NULL;
    
    // Create a set of ten nodes.
    
    work = head;
    
    for (int i = 0; i < 10; i++)
    {
        work->next = push(work, (2 * i + i + 12));
        work = work->next; /* Links this node to the newly created node. */
    }

    // Now travel down the chain and print out the pertinent statistics of the nodes.

    work = head;

    while (1)
    {
        printf("This node's values are: this->%p value->%d previous->%p next->%p.\n", work, work->val, work->previous, work->next);
        if (work->next == NULL)  /* We have reached the end of the list */
            break;
        work = work->next;
    }

    return 0;
}
   

When I ran this program, I received the following output on my terminal.

This node's values are: this->0x55bfd6edc2a0 value->2 previous->(nil) next->0x55bfd6edc2c0.
This node's values are: this->0x55bfd6edc2c0 value->12 previous->0x55bfd6edc2a0 next->0x55bfd6edc2e0.
This node's values are: this->0x55bfd6edc2e0 value->15 previous->0x55bfd6edc2c0 next->0x55bfd6edc300.
This node's values are: this->0x55bfd6edc300 value->18 previous->0x55bfd6edc2e0 next->0x55bfd6edc320.
This node's values are: this->0x55bfd6edc320 value->21 previous->0x55bfd6edc300 next->0x55bfd6edc340.
This node's values are: this->0x55bfd6edc340 value->24 previous->0x55bfd6edc320 next->0x55bfd6edc360.
This node's values are: this->0x55bfd6edc360 value->27 previous->0x55bfd6edc340 next->0x55bfd6edc380.
This node's values are: this->0x55bfd6edc380 value->30 previous->0x55bfd6edc360 next->0x55bfd6edc3a0.
This node's values are: this->0x55bfd6edc3a0 value->33 previous->0x55bfd6edc380 next->0x55bfd6edc3c0.
This node's values are: this->0x55bfd6edc3c0 value->36 previous->0x55bfd6edc3a0 next->0x55bfd6edc3e0.
This node's values are: this->0x55bfd6edc3e0 value->39 previous->0x55bfd6edc3c0 next->(nil).

Hopefully, this might give you some food for thought on pointer usage as it pertains to linked lists. Also, since the program is using "malloc" it usually is a good idea to have some cleanup in the program to make sure the memory is freed up (e.g. use the "free()" function).

Hope that helps.

Regards.