Sorted Linked List in Python

Question

I'm having a bit of trouble figuring out how to sort a Singly Linked list in Python. I've figured out how to create a linked list and push data onto it but how do I push it in a sorted format (not sorting after all the data is pushed onto it) or just sorting it in any way?

Objective

Create a sorted singly linked list of numbers based upon user input. Program logic: Ask for a number, add that number to the list in sorted position, print the list. Repeat until they enter -1 for the number.

Current Code

#!/usr/bin/env python

class node:
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node


class linked_list:
    def __init__(self):
        self.cur_node = None

    def add_node(self, data):
        new_node = node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node #  set the current node to the new one.

    def list_print(self):
        node = self.cur_node # cant point to ll!
        while node:
            print(node.data)
            node = node.next


def main():
  ll = linked_list()

  num=int(input("Enter a num to push onto the list, -1 to stop: "))
  while num!=-1:
    data=num
    ll.add_node(data)
    num=int(input("Enter a num to push onto the list, -1 to stop: "))

  print("\n")
  ll.list_print()
main()

I'm really stuck here. Thank you in advance for any help!

Answer 1

This should do it:

class Node:
  def __init__(self):
    self.data = None
    self.next = None

class LinkedList:
  def __init__(self):
    self.head = None

  def addNode(self, data):
    curr = self.head
    if curr is None:
      n = Node()
      n.data = data
      self.head = n
      return

    if curr.data > data:
      n = Node()
      n.data = data
      n.next = curr
      self.head = n
      return

    while curr.next is not None:
      if curr.next.data > data:
        break
      curr = curr.next
    n = Node()
    n.data = data
    n.next = curr.next
    curr.next = n
    return

  def __str__(self):
    data = []
    curr = self.head
    while curr is not None:
      data.append(curr.data)
      curr = curr.next
    return "[%s]" %(', '.join(str(i) for i in data))

  def __repr__(self):
    return self.__str__()

def main():
  ll = LinkedList()
  num = int(input("Enter a number: "))
  while num != -1:
    ll.addNode(num)
    num = int(input("Enter a number: "))
  c = ll.head
  while c is not None:
    print(c.data)
    c = c.next

Gives

>>> main()
Enter a number: 5
Enter a number: 3
Enter a number: 2
Enter a number: 4
Enter a number: 1
Enter a number: -1
1
2
3
4
5

Answer 2

class Node:
    def __init__(self, data):
        self.data = int(data)
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None    

    def asc_ordered_list(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        temp = self.head
        if temp.data > data:
            new_node.next = temp
            self.head = new_node
            return

        while temp.next:
            if temp.next.data > data:
                break
            temp = temp.next

        new_node.next = temp.next
        temp.next = new_node

    def desc_ordered_list(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        temp = self.head
        if data > temp.data:
            new_node.next = temp
            self.head = new_node
            return

        while temp.next:
             if temp.data > data and temp.next.data < data:
                 break
             temp = temp.next

        new_node.next = temp.next
        temp.next = new_node

    def display_list(self):
        temp = self.head
        while temp is not None:
            print("data = {0}".format(temp.data))
            temp = temp.next

if __name__ == "__main__":
    llist = LinkedList()
    llist.desc_ordered_list(8)
    llist.desc_ordered_list(3)
    llist.desc_ordered_list(1)
    llist.desc_ordered_list(4)
    llist.desc_ordered_list(5)
    llist.desc_ordered_list(7)
    llist.desc_ordered_list(6)
    llist.desc_ordered_list(2) 
    llist.display_list()