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

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/