## DEV Community 👩‍💻👨‍💻

Abu Hurayra

Posted on • Updated on

# Insertion in a Sorted Linked List Using Python

Insertion in a sorted linked list can have 3 outcomes:

1. If the given data is the smallest then it will be inserted at the beginning.
2. If the data is the biggest then it will be inserted at the end of the list.
3. Otherwise it will be inserted where the next node data bigger than the given data.

## Step 1: Create a new node with the data

``````    def insert(self, data):
new_node = Node(data)
``````

## Step 2: If the linked list is empty then insert the node at the head

``````        # If the linked list is empty
``````

## Step 3: If the data is smaller than the head, insert it at the beginning

``````        # If the data is smaller than the head
``````

## Step 4: Locate the node that is the biggest node smaller than the given node and insert the node after it.

``````            # Locate the node before the insertion point
while current.next and new_node.data > current.next.data:
current = current.next

# Insertion
new_node.next = current.next
current.next = new_node
``````

## This is how the insert function will look:

``````    def insert(self, data):
new_node = Node(data)

# If the linked list is empty

# If the data is smaller than the head

else:
# Locate the node before the insertion point
while current.next and new_node.data > current.next.data:
current = current.next

# Insertion
new_node.next = current.next
current.next = new_node
``````

## Step 5: Write a print method to print the linked list:

``````    def printList(self):
if not temp:
print('List is empty.')
return
else:
print('Start:', end=' ')
while temp:
print(temp.data, end=' -> ')
temp = temp.next
print('end.')
``````

## Write some code to test the output:

``````if __name__=='__main__':
LL.printList()

LL.insert(10)
LL.insert(12)
LL.insert(8)
LL.insert(11)
LL.insert(10)

LL.printList()
``````

## The complete program:

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

def __init__(self):

def printList(self):
if not temp:
print('List is empty.')
return
else:
print('Start:', end=' ')
while temp:
print(temp.data, end=' -> ')
temp = temp.next
print('end.')

def insert(self, data):
new_node = Node(data)

# If the linked list is empty

# If the data is smaller than the head

else:
# Locate the node before the insertion point
while current.next and new_node.data > current.next.data:
current = current.next

# Insertion
new_node.next = current.next
current.next = new_node

if __name__=='__main__':
# Create an object
# Print Empty List
LL.printList()
# Insert some nodes
LL.insert(10)
LL.insert(12)
LL.insert(8)
LL.insert(11)
LL.insert(10)
# Print the list
LL.printList()

``````

References: