Insert a Node at the Particular Position

[click to read Insert at beginning] …………………….. [click to read Insert at last]

New node to be inserted at a particular position in the linked list. As a linked list traversing is linear, therefore we cannot directly reach to desired position, first we need to reach the required position. We use similar logic that we have used to reach to last node by just changing the while loop condition.

Here, first we reach to desired node and then insert the node as shown in the figure. It requires following steps

1. Locate the node preceding the insertion point , since it will have to be modified (make current point to it)
2. Make the new node point to the node after the insertion point (i.e. the node pointed to by the node that current points to)
3. Make the node pointed to by current point to the new node.

Alternatively, the frequent logic that is generally used while traversing the linked list is to declare two temporary node-type pointers, say current and previous. current will always refer to the current node and previous refers to node just before the current at any instant while traversing. Now the new node can be inserted between the previous and current node by just performing two steps:

1. Pass the address of the new node in the next field of the previous node.
2. Pass the address of the current node in the next field of the new node

(Note – cur is referred as current in the text)

Here, we are keep two variables current and previous. initially the current and previous are the pointing to the first node but as we move forward the current will represent to the node on which we are and previously for the node that is the predecessor of that node.

Overflow is a condition that occurs when we try to create a node but there is not a sufficient memory available, it comes in picture when we do insertion operations. Similarly, there is unde flow when we talk about the deletion operation. The very first task when you want to insert a node you need to first create a node, sometimes we don’t have any sufficient memory available in our computer and it returns an error.

      cur=head;

assigning the address at head to current, i.e. now head and current both point to the first node.

      for(int i=1;i<pos;i++)

Here we keep on traversing to reach to the desired position pos. very time after reaching to next node it will check that it reaches to desired position or not and perform the following operation

           { pre=cur; cur=cur->next; }

If required node has not been reached then set the current node as previous and current node will point to next node in the list. After reaching to desired node

pre->next=temp;

            temp->next=cur;

Write the address of new node at the address field of previous (i.e. previous will now point to new node) and write the value of the current pointer to the address field of new node (i.e. the new node now point to the node pointed by current.). Hence the new node is inserted between previous and current.

Insert a node after the particular value

Another version of this insertion is to insert a new node after a node which contains specific value. For example there is a linked list which contains some sorted values (say 1,45, 54, 89, 91, 99) we may be interested to insert 65 then our interest is to insert this value after node whose data value is 54. The following algorithm can be used to implement this scenario

Note – keep in mind the order of the statements makes a difference. Let’s have a look on two different set(versions) of statements

temp->next=head;             head=temp;

head=temp; temp->next=head;

Here, in first version we assign the value (address) stored at head to temp-next and then assign new value (address) to temp.

In the second version, we updated the head value and then made assignment of this new head value to temp-next. In the second case the previous value of head is been overwritten and we assigned a new value. Such points much be carefully taken care while writing code using pointer variables.