Pythonを使ったソートされたリンクリストの挿入


ソートされたリンクリストの挿入には3つの結果があります.
  • 与えられたデータが最小であるならば、それは始めに挿入されます.
  • データが最大の場合は、リストの最後に挿入されます.
  • さもなければ、それは与えられたデータより大きい次のノード・データがあるところで挿入されます.

  • ステップ1 :データを持つ新しいノードを作成する
        def insert(self, data):
            new_node = Node(data)
    

    ステップ2 :リンクされたリストが空であるならば、頭でノードを挿入してください
            # If the linked list is empty
            if self.head is None:
                self.head = new_node
    

    ステップ3:データが頭より小さいならば、始めにそれを挿入してください
            # If the data is smaller than the head
            elif self.head.data >= new_node.data:
                new_node.next = self.head
                self.head = new_node
    

    ステップ4 :指定されたノードより小さいノードであるノードを見つけ、ノードを挿入します.
                # 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
    

    これはINSERT関数がどのように見えるかです.
        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
    

    ステップ5 :リンクされたリストを印刷するためにPrintメソッドを書きます.
        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.')
    

    出力をテストするコードを書きます.
    if __name__=='__main__':
        LL = LinkedList()
        LL.printList()
    
        LL.insert(10)
        LL.insert(12)
        LL.insert(8)
        LL.insert(11)
        LL.insert(10)
    
    
        LL.printList()
    

    出力は以下のようになります.


    完全なプログラム
    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()
    
    

    その記事を読んでくれてありがとう.😄
    参考文献
  • https://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/
  • https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/