Lecture 185:-Inserting in a Sorted Linked List

 

Inserting elements in a sorted order in a linked list involves finding the appropriate position for the new element and then inserting it in that position while maintaining the sorted order. Here's how you can implement the insertion in a sorted linked list:

 

pythonCopy code

class Node:    def __init__(self, data):        self.data = data        self.next = None class SortedLinkedList:    def __init__(self):        self.head = None    def insert(self, data):        new_node = Node(data)        # If the list is empty or the data is less than the head's data,        # insert the new node at the beginning        if not self.head or data < self.head.data:            new_node.next = self.head            self.head = new_node        else:            current = self.head            while current.next and current.next.data < data:                current = current.next            new_node.next = current.next            current.next = new_node    def display(self):        current = self.head        while current:            print(current.data, end=" -> ")            current = current.next        print("None") # Example usage: if __name__ == "__main__":    sorted_linked_list = SortedLinkedList()    # Insert elements to create the sorted linked list    sorted_linked_list.insert(3)    sorted_linked_list.insert(7)    sorted_linked_list.insert(1)    sorted_linked_list.insert(9)    # Display the sorted linked list    print("Sorted Linked List:")    sorted_linked_list.display()

In this example, we define the Node and SortedLinkedList classes. The SortedLinkedList class has an insert method that inserts elements in a sorted order. We then create a sorted linked list object and use the insert method to add elements (3, 7, 1, and 9) to create the sorted linked list. Finally, we display the created sorted linked list.

The output will be:

rustCopy code

Sorted Linked List: 1 -> 3 -> 7 -> 9 -> None

The linked list is created with elements inserted in a sorted order, resulting in the sorted order 1 -> 3 -> 7 -> 9.