Inserting a node Linked Lists

Written by Ali on. Posted in C++

Hello everyone. In the series of Linked Lists we have been doing in CodingMash, we have known how to create Linked Lists and what glitches to avoid. In this post, we’ll see how to add a new node anywhere in the Linked List during runtime operation of the program.

Linked Lists once created can save a lot of time and trouble as we have discussed earlier. Once made, they allow a range of operations to be performed on them. Here, we will discuss the adding on a node in an already created Linked List.

When inserting a node in a Linked List, there are some things to be specifically taken care of. The foremost and the prime being that the statements must be carefully planned and then executed; in case of a small mistake, the information in the Linked List could be lost and would send the program crashing resulting in abnormal termination. The traversing of the List should be done very systematically and the code should be dry run several times before executed.

There are three instances where a node might be inserted in a Linked List: at the beginning or the Head of the Linked List, in the middle of the Linked List or at the end of the Linked List.

Assume the following struct for the addition of a node in the Linked List:

</p>
<p>struct student</p>
<p>{</p>
<p>. string name;</p>
<p>. int rollnum;</p>
<p>. student * Next;</p>
<p>};</p>
<p>

Let us first analyze the addition of a new node at the beginning of a Linked List. If the information has to be entered at the beginning of a Linked List, you first make a new temporary pointer of the same type as the struct. After allocation of memory, you fill in the data members with the required information. Then set the Next of the temporary node equal to the Head pointer and in the very next line set the Head equal to the current pointer. What actually happens is that you make the Next pointer of the temporary node point towards where the Head was pointing. This is what we really wanted, to add a node at the beginning. After that we set the Head pointer equal to the temporary pointer, giving Head the starting address of the node that has been added at the front. This would be something like this:

 

</p>
<p>//here we assume that a Linked List has been created and we’re just adding</p>
<p>//a node to it. The Head holds the Starting address of the Linked List.</p>
<p>. student * Current;</p>
<p>. Current = new student;</p>
<p>. Current -&gt; name = “Alice”;</p>
<p>. Current -&gt; rollno = 13;</p>
<p>. Current -&gt; Next = Head;</p>
<p>. Head = Current;</p>
<p>

Then comes the second case of adding the node in the middle. Now in this case as well you have to be very careful as to manage the pointers carefully as a single mistake can destroy the Linked List and can send the code crashing. The very same procedure, we first make a temporary pointer of type student and allocate memory to it and input data. After that we have to be careful of inserting the node in the list. We first traverse the list till the point where we want to enter the information. Upon reaching the point, which let say is Current -> Next, we first set the Next of the temporary node, temp -> Next, equal to the Next of Current, Current -> Next. After that we then set the traversing pointer, Current, equal to the temporary node, temp -> Next. The following code explains its bit.

</p>
<p>. Current -&gt; Next;            //The position at which the node is to be placed.</p>
<p>. student * temp;</p>
<p>. Current = new student;</p>
<p>. Current -&gt; name = “Alice”;</p>
<p>. Current -&gt; rollno = 13;</p>
<p>. temp -&gt; Next = Current -&gt; Next;</p>
<p>. Current -&gt; Next = temp;</p>
<p>

The last case left is entering the node at the end. This is by far the easiest way to enter a node in an already present Linked List. All you have to do is to traverse the Linked List till the point the Next, Current -> Next, of a node is equal to NULL. At that point, make a pointer of type student, allocate memory and add information to it. Then set the traversed pointer equal to the temporary pointer. Also don’t forget to set the Next of the temporary pointer equal to NULL so that it marks the end of the Linked List.

</p>
<p>. Current -&gt; Next;            //The position at which the node is to be placed.</p>
<p>. student * temp;</p>
<p>. Current = new student;</p>
<p>. Current -&gt; name = “Alice”;</p>
<p>. Current -&gt; rollno = 13;</p>
<p>. Current -&gt; Next = temp;</p>
<p>. temp -&gt; Next = NULL;</p>
<p>

That’s enough food for your brains for this time folks. We’ll soon be back with more to keep your curious minds healthy. Till then, stay safe.

Tags: , ,