Understanding Linked List programming-2

Till now we have learned the data type to be used for linked list and creation of a root node of a singly linked list. In this article we will learn how to add nodes to a previous node.

Adding nodes to Linked List after last node

For adding node after the last node, we must first allocate a memory for that node, then change the pointer of previous node to our new last node. After that insert the value of new last node and make its pointer pointing to NULL. 

     struct linkedlist *newNode=(struct linkedlist*)malloc(sizeof(struct linkedlist));

     current->next=newNode;

     newNode->value=20;

     newNode->next=null;

     current=newNode;

Explanation

• The first line allocates memory for a new node in a similar way explained in previous post.
• The second line make the pointer of current last node to point to newly formed node.
• Third Line inserts an integer value of 20 in the new node.
• Next line of code makes the pointer of new node point to Null.
• Last line makes the new node to current node. 

Here in this we have presumed that the current node is the last node only. If not we have to make an extra step of traversing the last node. This will be explained later.

Traversing a linked list

Before we learn how to insert a node at specific location, we must understand how to traverse a linked list. Traversing a linked list is very simple. I will show the following piece of code which will traverse the linked list and print the current address of node, value of node and address of node current node is pointing to.

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

Explanation

• The first line of above code assigns head node or root node as the current node so that we start traversing form the root node.
• Next I have started a while loop which will run until current node points to NULL. 
• Inside the loop, using printf(), I have printed current node address by using %p (for pointers) with current struct, value inside node by using %d with current->value and address of next node by using %p with current->next.
• Next I have changed the current node by making the address of current node  to that of the next node by current=current->next.

Adding node at given position

To insert node at a given location say n, first of all we need to traverse upto a node n-1. Then store the pointer value of that node. Then create a new node, insert the desired value in it. Then change the pointer of n-1 th node to point to newly created node.  Finally assign the previously saved pointer address to this newly created node. This is coded below.

       struct linkedlist *temp=(struct linkedlist*) malloc(sizeof(struct linkedlist));
   int data,position=1,x;
   int *address;

   printf("Enter the Location: ");

   scanf("%d",&x);   

   printf("Enter the data:");
   scanf("%d",&data);
   current=head;
   while(current!=NULL && position<x-1)
   {
    position++;
    current=current->next;
   }
   address=current->next;
   current->next=temp;
   temp->next=address;
   temp->value=data;
   current=temp;

Explanation

• First line of code allocates memory area for a new node named temp.
• Next I declared 3 integer variables. data for value to be stored in node, x for the position where the new node is to be inserted and initialized position to 1. position variable will help in location the desired position where the node is to be inserted.
• In the third line, an integer pointer has been created to hold the address of x-1 th node.
• In the next four lines of code, i have entered the value of data and x at run time.
• In the following line, I have made the head or root node as the current node to start traversing upto x-1th node.
• . The while loop will traverse until x-1 th node or last node if the specified position is not found.
•  In the next line the address pointed by current node that is currently the x-1th node is saved in the address variable.
• After that the address pointed by the x-1th node is changed to the address of new temp node.
• Next in temp node  the value of next which stores the value of next node is assigned the value stored in address variable.
• Following that the value field of temp is set to data.
• Finally the current node is set as the newly inserted temp node.

We can adopt similar procedure to insert the node in the beginning.