# Linked List Insertion – Linked List Tutorial Series #2

0
39

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:

1. Insert at start
2. Insert at end
3. 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
1. Update the next of new node to current node.
2. Update head pointer to point to the new node.

Here’s the code to insert a node at start:

 # 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

view raw
InsertAtFront.py
hosted with ❤ by GitHub

##### 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
1. update new node’s pointer to null
2. update last node’s pointer to new node.

Here is the code to insert a node at the end of a Linked list:

 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

view raw
InsertAtEnd.py
hosted with ❤ by GitHub

##### 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
1. If we need to add a node at position 3, we will stop at position 2 – which we also call as position node.
2. 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:

 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

view raw
InsertAtPosition.py
hosted with ❤ by GitHub

Now let us see the executable code of insertion of Linked list where we can call all the three functions discussed above.

##### 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.

5 1 vote
Article Rating
Subscribe
Notify of

This site uses Akismet to reduce spam. Learn how your comment data is processed.