![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645011964295-Article_195.png\")
<\/p>\n<\/p>\n
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.<\/p>\n<\/p>\n
In this article, we are going to learn about the insertion operations in a singly linked list. <\/p>\n
There are three primary insertion operations.<\/p>\n
Let us have a look at all these Insertion operations.<\/p>\n
What should we do to insert a node at the beginning?
\nIt is pretty simple. Let us take an example to understand it. <\/p>\n
Also, keep in mind that, the new node which gets added at the front of the list, will be the new head<\/strong> of the list.<\/p>\n This is quite simple. Let the newly created node be x<\/strong> and make x \u2192 next = head<\/strong> and then make head = x<\/strong>, as explained above.<\/p>\n 1) Create the node which is to be inserted, say newnode<\/strong>. Time Complexity:<\/strong> O(1), as we are only accessing and changing the head of the list.<\/p>\n Space Complexity:<\/strong> O(1), as no extra space is being used.<\/p>\n What should we do to insert an element at the end of a linked list? So, following the above approach of insertion at the end, we will first take a pointer curr<\/strong> and using it we will traverse to the last node<\/strong> of the list. As explained above, after reaching the last node<\/strong>, we will simply make curr \u2192 next = newnode<\/strong> and newnode \u2192 next = NULL<\/strong>.<\/p>\n 1) Create the node which is to be inserted, say newnode<\/strong>. Time Complexity:<\/strong> O(N), as we have to traverse the list to reach the end of the list. In this approach, we will be given a node\u2019s address. We will have to insert the new node just after this given node.<\/p>\n As we have the address of the node, we don\u2019t have to traverse the linked list. Let take an example to understand it more clearly; suppose the given list is: 1 \u2192 2 \u2192 3, and we have the address of 2, and we want to insert a new node (say x<\/strong>) after this node 2.<\/p>\n Suppose the address of the node after which we have to insert the new node is NODE<\/strong>. So, now to insert the newnode<\/strong> just after this node, we will do the following steps.<\/p>\n 1) Create the node which is to be inserted, say NewNode<\/strong>, and the node whose address is given is prevnode<\/strong>. 4) After performing the above steps, our new node NewNode<\/strong> will get inserted after the prevnode<\/strong>. <\/p>\n Time Complexity:<\/strong> O(1), as we have the address of the node after which the new node is to be inserted.<\/p>\n Space Complexity:<\/strong> O(1), as no extra space is being used.<\/p>\n To get a clearer understanding, have a look at the dry run. Let us head on to the dry run of these methods.<\/p>\nAlgorithm<\/h3>\n
\n2) If the list is empty<\/strong>, the head<\/strong> will point to the newnode<\/strong>, and we will return.
\n3) Else, If the list is not empty<\/strong>:<\/p>\n\n
Approach (Insert at the end)<\/h3>\n
\nIt is pretty simple. Let us take an example to understand it.<\/p>\n\n
Algorithm<\/h3>\n
\n2) If the list is empty<\/strong>, make head<\/strong> point to the newnode<\/strong>, and return.
\n3) Else, if the list is not empty<\/strong>: <\/p>\n\n
\nSpace Complexity:<\/strong> O(1), as no extra space is being used.<\/p>\nApproach (Insert after a given node)<\/h3>\n
\n
\n
Algorithm<\/h3>\n
\n2) If the address of the given node is NULL<\/strong>, simply return.
\n3) Else, if address is not NULL<\/strong>: <\/p>\n\n
\n
Dry Run<\/h3>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_1-1-1.png\")
<\/p>\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_2-1-1.png\")
<\/p>\nCode Implementation<\/h3>\n\t\t\t\t\t\t