Question

How to build sorted linear (singly) linked list and insert new items in sorted order with Python

Answer 1

class Node:
    def __init__(self, n):
        self.n = n
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def insert_sorted(self, new_node):
        if self.head is None:
            new_node.next = self.head
            self.head = new_node
        elif self.head.n >= new_node.n:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            while current.next is not None and current.next.n < new_node.n:
                    current = current.next
 
            new_node.next = current.next
            current.next = new_node
 
    def print_linked_list(self):
        tmp = self.head
        while tmp:
            print(tmp.n)
            tmp = tmp.next
 
 
linkedlist = LinkedList()
 
new_node = Node(13)
linkedlist.insert_sorted(new_node)
 
new_node = Node(10)
linkedlist.insert_sorted(new_node)
 
new_node = Node(5)
linkedlist.insert_sorted(new_node)
 
new_node = Node(2)
linkedlist.insert_sorted(new_node)
 
new_node = Node(3)
linkedlist.insert_sorted(new_node)
 
new_node = Node(1)
linkedlist.insert_sorted(new_node)
 
new_node = Node(8)
linkedlist.insert_sorted(new_node)
 
linkedlist.print_linked_list()
 
 
 
'''
run:
 
1
2
3
5
8
10
13
 
'''

 

70+ SQL courses for beginners and professionals

Answer 2

class Node:
    def __init__(self, n):
        self.n = n
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def insert_sorted(self, data):
        new_node = Node(data)
        
        if self.head is None:
            new_node.next = self.head
            self.head = new_node
        elif self.head.n >= new_node.n:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            while current.next is not None and current.next.n < new_node.n:
                    current = current.next
 
            new_node.next = current.next
            current.next = new_node
 
    def print_linked_list(self):
        tmp = self.head
        while tmp:
            print(tmp.n)
            tmp = tmp.next
 
 
linkedlist = LinkedList()
 
linkedlist.insert_sorted(13)
linkedlist.insert_sorted(10)
linkedlist.insert_sorted(5)
linkedlist.insert_sorted(2)
linkedlist.insert_sorted(3)
linkedlist.insert_sorted(1)
linkedlist.insert_sorted(8)
 
linkedlist.print_linked_list()
 
 
 
'''
run:
 
1
2
3
5
8
10
13
 
'''

 

70+ SQL courses for beginners and professionals