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.
Agenda
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # insertion of new node at front of linked list | |
| def insert_at_front(head, data): | |
| # creating new node to be inserted | |
| new_node = Node(data) | |
| new_node.next = head # pointing the new node's next to head | |
| head = new_node # making the new node as head | |
| return head |
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def insert_at_end(head, data): | |
| new_node = Node(data) | |
| current = head | |
| while current.next: # traversing till the last node | |
| current = current.next | |
| # change the next of last node | |
| current.next = new_node | |
| return head |
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def insert_at_pos(head, data, position): | |
| # edge case: check if pos is 0 | |
| new_node = Node(data) | |
| if position is 0: | |
| new_node.next = head | |
| head = new_node | |
| return head | |
| pos = 0 | |
| new_node = Node(data) | |
| curr_node = head | |
| # iterating till the position is reached | |
| while curr_node.next and pos < position – 1: | |
| pos += 1 | |
| curr_node = curr_node.next | |
| # making new node's next as current node's next | |
| new_node.next = curr_node.next | |
| # making current node's next point to new node | |
| curr_node.next = new_node | |
| return head |
Now let us see the executable code of insertion of Linked list where we can call all the three functions discussed above.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Node: | |
| def __init__(self, data=None): | |
| self.data = data | |
| self.next = None | |
| class SinglyLinkedList: | |
| def __init__(self): | |
| self.head = None | |
| # insertion of new node at front of linked list | |
| def insert_at_front(head, data): | |
| # creating new node to be inserted | |
| new_node = Node(data) | |
| new_node.next = head # pointing the new node's next to head | |
| head = new_node # making the new node as head | |
| return head | |
| def insert_at_end(head, data): | |
| new_node = Node(data) | |
| current = head | |
| while current.next: # traversing till the last node | |
| current = current.next | |
| # change the next of last node | |
| current.next = new_node | |
| return head | |
| def insert_at_pos(head, data, position): | |
| # edge case: check if pos is 0 | |
| new_node = Node(data) | |
| if position is 0: | |
| new_node.next = head | |
| head = new_node | |
| return head | |
| pos = 0 | |
| new_node = Node(data) | |
| curr_node = head | |
| # iterating till the position is reached | |
| while curr_node.next and pos < position – 1: | |
| pos += 1 | |
| curr_node = curr_node.next | |
| # making new node's next as current node's next | |
| new_node.next = curr_node.next | |
| # making current node's next point to new node | |
| curr_node.next = new_node | |
| return head | |
| if __name__ == '__main__': | |
| head = None | |
| head = insert_at_front(head, 1) | |
| head = insert_at_front(head, 2) | |
| head = insert_at_end(head, 3) | |
| head = insert_at_end(head, 4) | |
| head = insert_at_pos(head, 12, 1) | |
| while head: | |
| print('{}'.format(head.data), end=" ") | |
| head = head.next |
Time Complexity
We might need to insert a node at the end in worst case. Hence time complexity is O(n).
Space Complexity
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.
