Insert a node at begining of linked list

Some how students find linked list very confusing.

It is not.

Let us say you have many nodes in the linked list. And each of this node is dynamically allocated. And hence you can not access them easily. So what is done is each node is connected to previous node with the help of a pointer.

Any node will always have a pointer which has address of next node.

And thus, if you just have address of first node, you can visit second, then third, then fourth and every node of list. 

How do we add new nodes to the list? We can add them at the end. Appending a node to the end of a list is quite simple. Just go till last node, set the pointer of the last node to address of newly created node. That's all.

But what if you want to add a node as the first node? When this newly added node is made is  first node, first node should become second and so on.  But how do you modify first node pointer or head?

Since a function modifying head pointer gets only a copy of head, even if it     changes head, head is not changed in main(). So in order to achieve correct result, the function should return pointer for new value of head.

Let us call the function as modify_first.

The function needs head of course and also the new node which should become the new head.

The function should make the head node as second node of course.

Now after the operation, the HEAD variable which holds address 4000 (which is address of first node) must contain 5200 which is address of newnode.

But what happens to the node with address 4000? We do not want to lose this and hence the list. So we should store this address in the next pointer of newnode.

Hence our code must be some thing like

newnode ->next = head;
head = newnode;

But how do we make changes to head in the calling function ? By returning head.

NODEPTR insert_begining(NODEPTR head, NODEPTR newnode)
{
     newnode->next = head;
     head = newnode;//this and next line can also be written as return newnode
     return head;
}

And do not forget to assign the return value of this function to head. So the function should be called in main as

head = insert_begining(head,newnode);


Let us combine this with our previous program from creating linked list

Here is the complete program.

 #include <stdio.h>  
 struct node  
 {  
  int data;  
  struct node *next;  
 };  
 typedef struct node * NODEPTR;  
 NODEPTR create_node(int val)  
 {  
    NODEPTR newnode;  
    newnode= (NODEPTR) malloc(sizeof(struct node));  
    if (newnode==NULL)  
    {  
       printf("Memory allocation failure..");  
       return NULL;  
    }  
    newnode->data = val;  
    newnode->next = NULL;  
    return newnode;  
 }  
 NODEPTR append_node(NODEPTR head,int val)  
 {  
    NODEPTR newnode,lastnode ;  
    newnode = create_node(val);  
    if(newnode==NULL)  
      return head;  
    /*if the list is empty , assign newnode to head*/  
    if(head ==NULL)  
    {  
     head = newnode;  
     return head;  
    }  
   /*find the last node in the linked list */  
    for(lastnode = head; lastnode->next!=NULL;lastnode = lastnode->next)  
      ;/*do not forget this semicolon*/  
    /*link the new node to lastnode - the last node*/  
    lastnode->next = newnode;  
    return head;  
 }  
 void print_list(NODEPTR head)  
 {  
    NODEPTR temp = head;  
    while(temp!=NULL)  
    {  
        printf("%d---->",temp->data);  
        temp = temp ->next;  
    }  
 }  
 NODEPTR insert_begining(NODEPTR head, NODEPTR newnode)  
 {  
    newnode->next = head;  
    head = newnode;//this and next line can also be written as return newnode  
    return head;  
 }  
 int main()  
 {  
   NODEPTR head = NULL,temp;  
   int i;  
   for(i = 0;i<10;i++)  
   {  
     int n;  
     printf("Enter a number :");  
     scanf("%d",&n);  
     head = append_node(head,n);  
   }  
   printf("The list is :");  
   print_list(head);  
   printf("Enter the node to add at the begining");  
   scanf("%d",&i);  
   temp = create_node(i);  
   head = insert_begining(head,temp);  
   print_list(head);  
   return 0;  
 }