Inserting a node at the beginning of a singly linked list

The code below will prompt for numbers and continue to add them to the beginning of a linked list.

/* This program will demonstrate inserting a node at the beginning of a linked list */

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

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

void insert_node (struct Node **head, int nodeValue);
void print_list (struct Node *head);

int main(int argc, char *argv[]) {
  struct Node* headNode;
  headNode = NULL; /* Initialize our first node pointer to be NULL. */
  size_t listSize, i;
  do {
    printf("How many numbers would you like to input?\n");
  } while(1 != scanf("%zu", &listSize));

  for (i = 0; i < listSize; i++) {
    int numToAdd;
    do {
      printf("Enter a number:\n");
    } while (1 != scanf("%d", &numToAdd));

    insert_node (&headNode, numToAdd);
    printf("Current list after your inserted node: \n");
    print_list(headNode);
  }

  return 0;
}

void print_list (struct Node *head) {
  struct node* currentNode = head;

  /* Iterate through each link. */
  while (currentNode != NULL) {
      printf("Value: %d\n", currentNode->data);
      currentNode = currentNode -> next;
  }
}

void insert_node (struct Node **head, int nodeValue) {
  struct Node *currentNode = malloc(sizeof *currentNode);
  currentNode->data = nodeValue;
  currentNode->next = (*head);

  *head = currentNode;
}

Explanation for the Insertion of Nodes

In order to understand how we add nodes at the beginning, let’s take a look at possible scenarios:

The list is empty, so we need to add a new node. In which case, our memory looks like this where HEAD is a pointer to the first node:

HEAD | –> NULL

The line currentNode->next = *headNode; will assign the value of currentNode->next to be NULL since headNode originally starts out at a value of NULL.

Now, we want to set our head node pointer to point to our current node.

-----      -------------
|HEAD | --> |CURRENTNODE| --> NULL /* The head node points to the current node */
-----      -------------

This is done with *headNode = currentNode;

The list is already populated; we need to add a new node to the beginning. For the sake of simplicity, let’s start out with 1 node:

-----    -----------
HEAD --> FIRST NODE --> NULL
-----    -----------

With currentNode->next = *headNode, the data structure looks like this:

---------        -----    ---------------------
currentNode -->  HEAD --> POINTER TO FIRST NODE --> NULL
---------        -----    ---------------------

Which, obviously needs to be altered since *headNode should point to currentNode.

----    -----------    ---------------
HEAD -> currentNode -->     NODE       -> NULL
----    -----------    ---------------

This is done with *headNode = currentNode;

Found a mistake? Have a question or improvement idea? Let me know.

Table Of Contents