Linked List Insertion – Linked List Tutorial Series #2

0
39
linked list insertion featured logo

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.

Linked List Introduction

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.

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.

5 1 vote
Article Rating
Subscribe
Notify of
guest

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

0 Comments
Inline Feedbacks
View all comments