Insertion in linked list Python program: At Beginning, End and Given Location

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:

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

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.

class Node:
	def __init__(self, data=None):
		self.data = data
		self.next = None

class LinkedList:
	 def __init__(self):
		self.head = None
		self.head = None

Beginning: Insertion at the 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

def pushFirst(self, newElement):
		#create new node and assign new data
		newNode=Node(newElement)
		#make next node as new node
		newNode.next = self.head
		#make new node as head
		self.head = newNode

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.

At given position: Insertion of node 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.

def pushAtLocation(self, newElement, position):
    # Create a new node with the new element
    newNode = Node(newElement)

    if position < 1:
        print("Position should be greater than or equal to 1")
        return

    if position == 1:
        # Insert at the beginning
        newNode.next = self.head
        self.head = newNode
    else:
        # Traverse to the node before the desired position
        temp = self.head
        for i in range(1, position - 1):
            if temp is not None:
                temp = temp.next
            else:
                break

        if temp is not None:
            newNode.next = temp.next
            temp.next = newNode
        else:
            print("Position out of bounds")

End: Insertion in the 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.

def pushLast(self, newElement):
    # Create a new node with the new data
    newNode = Node(newElement)

    # Check if the linked list is empty
    if self.head is None:
        self.head = newNode
    else:
        # Traverse to the last node
        temp = self.head
        while temp.next is not None:
            temp = temp.next
        # Change the next of last node to new node
        temp.next = newNode

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

Python Program to create, insert and traverse singly linked list

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None

    def pushFirst(self, newElement):
        newNode = Node(newElement)
        newNode.next = self.head
        self.head = newNode

    def pushAtLocation(self, newElement, position):
        newNode = Node(newElement)
        if position < 1:
            print("Position should be >= 1")
        elif position == 1:
            newNode.next = self.head
            self.head = newNode
        else:
            temp = self.head
            for i in range(1, position - 1):
                if temp is not None:
                    temp = temp.next
                else:
                    break

            if temp is not None:
                newNode.next = temp.next
                temp.next = newNode
            else:
                print("Position out of bounds")

    def pushLast(self, newElement):
        newNode = Node(newElement)
        if self.head is None:
            self.head = newNode
        else:
            temp = self.head
            while temp.next is not None:
                temp = temp.next
            temp.next = newNode

    def display(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("None")


# ---------------- MAIN PROGRAM ----------------
s = LinkedList()

while True:
    print("\nMenu:")
    print("1. Insert at the beginning")
    print("2. Insert at a specific position")
    print("3. Insert at the end")
    print("4. Display linked list")
    print("5. Exit")

    choice = input("Enter your choice (1-5): ")

    if choice == '1':
        data = int(input("Enter data to insert at beginning: "))
        s.pushFirst(data)

    elif choice == '2':
        data = int(input("Enter data to insert: "))
        pos = int(input("Enter position to insert at (1-based index): "))
        s.pushAtLocation(data, pos)

    elif choice == '3':
        data = int(input("Enter data to insert at end: "))
        s.pushLast(data)

    elif choice == '4':
        print("The linked list is:")
        s.display()

    elif choice == '5':
        print("Exiting program.")
        break

    else:
        print("Invalid choice. Please select between 1-5.")

Output

Menu:
1. Insert at the beginning
2. Insert at a specific position
3. Insert at the end
4. Display linked list
5. Exit
Enter your choice (1-5): 1
Enter data to insert at beginning: 4

Menu:
1. Insert at the beginning
2. Insert at a specific position
3. Insert at the end
4. Display linked list
5. Exit
Enter your choice (1-5): 1
Enter data to insert at beginning: 4

Menu:
1. Insert at the beginning
2. Insert at a specific position
3. Insert at the end
4. Display linked list
5. Exit
Enter your choice (1-5): 4
The linked list is:
4 -> 4 -> None

Menu:
1. Insert at the beginning
2. Insert at a specific position
3. Insert at the end
4. Display linked list
5. Exit
Enter your choice (1-5): 

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 3^rd position of the list)

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