Insertion in a sorted linked list can have 3 outcomes:

- If the given data is the
**smallest**then it will be inserted at the beginning. - If the data is the
**biggest**then it will be inserted at the end of the list. - 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
if self.head is None:
self.head = new_node
```

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

```
# If the data is smaller than the head
elif self.head.data >= new_node.data:
new_node.next = self.head
self.head = new_node
```

## 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
current = self.head
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 self.head is None:
self.head = new_node
# If the data is smaller than the head
elif self.head.data >= new_node.data:
new_node.next = self.head
self.head = new_node
else:
# Locate the node before the insertion point
current = self.head
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):
temp = self.head
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 = LinkedList()
LL.printList()
LL.insert(10)
LL.insert(12)
LL.insert(8)
LL.insert(11)
LL.insert(10)
LL.printList()
```

## This is how the output looks:

## The complete program:

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def printList(self):
temp = self.head
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 self.head is None:
self.head = new_node
# If the data is smaller than the head
elif self.head.data >= new_node.data:
new_node.next = self.head
self.head = new_node
else:
# Locate the node before the insertion point
current = self.head
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
LL = LinkedList()
# 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()
```

### Thank you for reading the article. ðŸ˜„

References:

## Discussion (0)