Linked List Insertion, unlike array or list insertion, is not pretty straight forward. In this article, we will discuss about Singly Linked List insertion. Usually if the statement is given as Linked List, we usually will assume as Singly Linked List.
This article will be continuation of our previous article on Linked List Introduction and creation. Here is the link if you want to follow along this series.
Table of Contents
Once we reach the end of the article, we should be able to insert a node in Linked list at any given position.
Insertion of a Linked List
We may be asked to insert a node in linked list at three different places:
- Insert at start
- Insert at end
- Insert at a given position
Let us discuss one by one along with the coding.
1. Insert a node at start
Insert at start is the simplest of the three – only one pointer needs to be modified to achieve insertion of node at start of Linked List.
Steps to insert
- Update the next of new node to current node.
- Update head pointer to point to the new node.
Here’s the code to insert a node at start:
2. Insert a node at the end
To insert a node at the end, we are required to modify 2 pointers. Let us see the steps to insert a node at end.
Steps to insert at end
- update new node’s pointer to null
- update last node’s pointer to new node.
Here is the code to insert a node at the end of a Linked list:
3. Insert a node at a given position
Here also we need to modify two pointers to insert a node at a given position.
Steps to insert node at a position
- If we need to add a node at position 3, we will stop at position 2 – which we also call as position node.
- New node points to the current node at position 3 and position node points to the new node.
Here is the code to insert a node at a given position:
Now let us see the executable code of insertion of Linked list where we can call all the three functions discussed above.
We might need to insert a node at the end in worst case. Hence time complexity is O(n).
O(1) for creating a temp variable.
In the next article, we will discuss about Linked list deletion. Subscribe to our newsletter to be the first to receive mail about latest updates.