Insertion in a Sorted Linked List Using Python
Tags: beginners, python, algorithms, programming
Published: 2021-09-02 12:19:09

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

```python
    def insert(self, data):
        new_node = Node(data)
```
---
## Step 2: If the linked list is empty then insert the node at the head

```python
        # 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

```python
        # 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.

```python
            # 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:

```python
    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:

```python
    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:

```python
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:

![output](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4fzftjniwezooo4f8u9g.png)

---

## The complete program:

```python
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. :smile:
---

References:
1. https://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/
2. https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/