Inserting a node at the beginning of a singly linked list
suggest changeThe 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