When the Linked List is Empty:
Let us say that we have an empty linked list i.e. there is no element currently in the linked list. We want to add the first element to this list. So, it is obvious that this element will be added to the head of the list only. Now, what is the procedure for adding a node at the beginning of an empty list? Let us try to add 10 to an empty linked list. Have a look at the diagram given below:
So, first of all, we will create a new node which will be inserted in the linked list. So, a memory is created for this node as shown in the figure (we have assigned a random memory address to the node.)
The second step is to insert the value into this node.
The third step is to point the head and tail variables at the newly inserted node as this node is the one and only node in the linked list. So, its starting and ending point will be the same i.e. its head and tail will point on this node only.
The fourth step is to make the next of this node point to null since it is the last node of the linked list. Also, do not forget to increase the size of the linked list by one as we have inserted an element in the list.
So, this is the simple procedure of inserting a node in an empty linked list. Now, let us move to the other situation where we will have to insert a new node to an already existing linked list.
When the Linked List is Not Empty:
Now let us say that we have the linked list as shown in the figure:
We want to insert 5 at the head of the linked list. So, let us understand the step by step procedure to do that:
The first two steps are the same where we have to create a new node and insert the value into the node.
In the third step, we point the next of the newly inserted node to the head of the existing linked list, so that it gets inserted before the current head and becomes the first element of the linked list.
Now that the element is inserted into the linked list successfully, we know that the head must always be at the first element of the linked list. So, we take head to t and now the insertion process is complete. Again, don't forget to increase the size of the linked list by 1 as a new element is inserted.
Now that we have understood the entire procedure for the addFirst() function, let us write the code for it.