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
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 = NoneBeginning: 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 = newNodeOur 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 = newNodeLet’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 3rd position of the list)
By following these steps of inputs which are given by the user the final output is generated.