TheLazy.Dev
Portfolio GitHub

Blog

beginners |python |algorithms |programming

Insertion in a Sorted Linked List Using Python

hurayraiit

Abu Hurayra

Posted on September 2, 2021

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.')
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

This is how the output looks:

output

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()
Enter fullscreen mode Exit fullscreen mode

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/
💖 💪 🙅 🚩
hurayraiit
Abu Hurayra

Posted on September 2, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

104. Depth of Binary Tree
beginners 104. Depth of Binary Tree

March 3, 2022

Insertion in a Sorted Linked List Using Python
beginners Insertion in a Sorted Linked List Using Python

September 2, 2021