Python program to insert a node in linked list

Python program to insert a node at beginning, at the end, and at the given location of singly linked list

In this tutorial, we are going to learn the python program to create a singly linked list and add a node at the beginning, at the end, and at the given location of the singly linked list.

Problem Statement

Our program will add an element at the beginning, at the end, and at the given location of the linked list.

For example:

Case1: If the user inputs the elements of the linked list as 1 and wants to add it at the beginning of linked list 2,3,4,5.

         The output should be 12345.

Case2: If the user inputs the elements of the linked list as 7 and wants to add it at the end of linked list 2,3,4,5.

           The output should be 23457.

Case3: If the user inputs the elements of the linked list as 4 and wants to add it after element 6 of linked list 2,3,6,5.

The output should be 23647.

What is a Linked List?

A linked list is the collection of elements that are connected via the memory address of successor elements. It is an unordered collection of data that is connected via links. Each data elements have another block that contains the address of the next elements of the linked list.

Creation Of Linked List

Python linked list traversal

The singly linked list is a linear records shape wherein every element of the listing incorporates a pointer which factors to the following detail inside the listing. Each element within the singly connected list is referred to as a node. Each node has two components: data and next pointer, which factors the following node within the listing. The first node of the list is the head, and the closing node of the list is called a tail. The last node of the list contains a pointer to the null. Each node in the list can be linearly accessed with the help of traversing through the list from head to tail. The linked list is created using the node class. We create a node object and another class to use this node object.

Insertion at the beginning of linked list           

In this case, the new list is added at the beginning of the linked list.

Inserting a new element at the beginning of the linked list involves some logic:-

i. Create a new node of the linked list.

ii. Change the head pointer to the newly created node.

iii. Make the node pointer, points to its next node that is the node where the head pointer is previously pointing.

Let’s look at the program snippet to insert an element at the beginning of the linked list

Our Logic to insert the node at beginning

  • Our program will take elements input from the user.
  • Store the elements inputs by the user in linked list format(Linked list creation)
  • Add the input element at the given location.
  • Apply the algorithm and print the final linked list elements.

Algorithm to insert the node in singly linked list

Step 1: Start

Step 2: create function push_first(), push_last(), and push_at_location().

Step 3: ask the user about which operation he/she wants.

Step 4: if(push at first):

i.Take input ‘element’ from the user.

ii. Call function Push_first(self, element).

   elif( push at ‘k’ position):

i. Take 2 inputs from the user one is the element to add and the position of the element.

ii. Call function push_at_location(self, element, position)

elif( push at last):

i. Take input ‘element’ from the user.

ii. Call function Push_last(self, element).

Step5: print the linked list

Step6: Stop

Insertion of node at the given position of linked list  

In this method, a newly created node is added at the position specified by the user.

Logic to add an element at given location:-

i. Create a new node with given element.

ii. Traverse the node to one previous to the insert location specified by the user and check if it is null or not.

iii. If it is not null, assign next of new node as next of previous node and next of previous node as new node.

iv. If the input location is null, then the position does not exist.

Let’s look on the program to insert an element at the given location of linked list.

Insertion at the end of linked list  

In this case, the new list is added at the end of the linked list.

Inserting a new element at the end of the linked list involves some logic

i. Create a new node of the linked list.

ii. Traverse to the last element of the list.

iii. Link the next pointer of the last node to the newly created list and the next pointer of the newly created list to Null.

Let’s look at the program to insert an element at the last of the linked list.

Let’s code the above algorithm in the python programming language.

Python Program to create and transverse singly linked list

Output 1:

Explanations

The linked list creation in this example is shown with steps:

  • Head–>5  (insert 5 at the first position of the list)
  • Head–>4–>5 (insert 4 at the first position of the list)
  • Head–>4–>5–>1 (insert 1 at last position of the list)
  • Head–>4–>5–>19–>1 (insert 19 at 3rd position of the list)

By following these steps of inputs which are given by the user the final output is generated.

Output 2:

Explanations

The linked list creation in this example is shown with steps:

  • Head–>91  (insert 91 at the first position of the list)
  • Head–>81–>91 (insert 81 at the first position of the list)
  • Head–>71–>81–>91 (insert 71 at the first position of the list)
  • Head–>71–>81–>91–>3 (insert 3 at last position of the list)
  • Head–>71–>45–>81–>91–>3 (insert 45 at 2nd position of the list)

By following these steps of inputs which are given by the user the final output is generated.