Thursday, July 18, 2024
HomeData StructuresLinked List Insertion - Linked List Tutorial Series #2

Linked List Insertion – Linked List Tutorial Series #2

-

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

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

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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

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

LATEST POSTS

Single Number | Leetcode 136 | 100 Days of Code Day 9

Welcome to Day 9 of Coderefer's 100 Days of code where we will be solving problems from Coderefer DSA sheet each day and today we...

3 Sum | Leetcode #15 | 100 Days of Code Day 10

Today we are going to solve 3 Sum - our first Medium Level Array problem from Coderefer DSA Sheet. If you are new to this...

Best Time to Buy and Sell Stock – Day 7 | 100 Days of Code

Welcome to Day 7 of 100 Days of Code where today we solve yet another most frequently asked easy array problem called - Best Time...

Contains Duplicate – Day 8 | 100 Days of Code

Welcome to Day 8 of 100 Days of Code and today we are going to solve yet another easy-level problem - Contains Duplicate as part...

Follow us

1,358FansLike
10FollowersFollow
397SubscribersSubscribe

Most Popular