Сортировка связанного списка, который содержит две данные в узле

Question

class Node :
    def __init__(self, newData=None, newArtist=None, nextNode=None):
        self.data = newData
        self.artist = newArtist
        self.next  = nextNode

    def getData(self):
        return self.data

    def setData(self, newData):
        self.data = newData

    def getArtist(self):
        return self.artist

    def setArtist(self, newArtist):
        self.artist = newArtist

    def getNext(self):
        return self.next

    def setNext(self, newNode):
        self.next = newNode

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

    def next(self, newNode, newData=None, newArtist=None):
        self.head = newNode
        self.data = newData
        self.artist = newArtist

    def printAll(self):
        i = 1
        if self.head:
            node = self.head
            if node.data:
                print('1: {} - {}'.format(node.getData(), node.getArtist()))
                i += 1
            while node.getNext():
                node = node.getNext()
                if node.data:
                    print('{}: {} - {}'.format(i, node.getData(), node.getArtist()))
                    i += 1

Song1 = Node("Silent Night", "John")
Song2 = Node("Last Christmas", "Andy")
Song3 = Node("Jingle Bells", "Mary")
Song4 = Node("Joy to the World", "Brad")

music_collection = LinkedList()
music_collection.next(Song1)
Song1.setNext(Song2)
Song2.setNext(Song3)
Song3.setNext(Song4)
music_collection.printAll()

Вместо этого теперь я хотел бы знать, можно ли отсортировать имя исполнителя в порядке убывания. Пожалуйста, не стесняйтесь добавлять другие методы, которые могут помочь с моим пониманием. (например, deleteNode, insertNode и т. д.)

Токовый выход:

1: Silent Night - John
2: Last Christmas - Andy
3: Jingle Bells - Mary
4: Joy to the World - Brad

Вывод отсортирован по имени исполнителя в порядке убывания:

1: Jingle Bells - Mary
2: Silent Night - John
3: Joy to the World - Brad
4: Last Christmas - Andy

Answer 1

Решение 1: Ваше решение

Я добавил метод delete в класс Node, а также добавил индекс к методу printAll:

class Node:
    def __init__(self, newData=None, newArtist=None, nextNode=None):
        self.data = newData
        self.artist = newArtist
        self.next = nextNode

    def getData(self):
        return self.data

    def setData(self, newData):
        self.data = newData

    def getArtist(self):
        return self.artist

    def setArtist(self, newArtist):
        self.artist = newArtist

    def getNext(self):
        return self.next

    def setNext(self, newNode):
        self.next = newNode

    def delete(self):
        self.data = None
        self.artist = None

    def __str__(self):
        return "%s (%s)" % (self.data, self.artist)


class LinkedList:
    def __init__(self, newData=None, newArtist=None):
        self.head = None
        self.data = newData
        self.artist = newArtist

    def next(self, newNode, newData=None, newArtist=None):
        self.head = newNode
        self.data = newData
        self.artist = newArtist

    def delete(self, node):
        if self.head:
            n = self.head
            if n == node:
                n.delete()
                return
            while n.getNext():
                n = n.getNext()
                if n == node:
                    n.delete()
                    return

    def printAll(self):
        i = 1
        if self.head:
            node = self.head
            if node.data:
                print('1: {} - {}'.format(node.getData(), node.getArtist()))
                i += 1
            while node.getNext():
                node = node.getNext()
                if node.data:
                    print('{}: {} - {}'.format(i, node.getData(), node.getArtist()))
                    i += 1


Song1 = Node("Silent Night", "John")
Song2 = Node("Last Christmas", "Andy")
Song3 = Node("Jingle Bells", "Mary")

music_collection = LinkedList()
music_collection.next(Song1)
Song1.setNext(Song2)
Song2.setNext(Song3)
music_collection.printAll()

music_collection.delete(Song3)
music_collection.printAll()

Итак, у меня есть следующие данные:

1: Silent Night - John
2: Last Christmas - Andy
3: Jingle Bells - Mary

При удалении последней песни:

1: Silent Night - John
2: Last Christmas - Andy

Решение 2: Более простое решение:

Просто пример, посмотрите на это:

import operator

class Node(object):
    def __init__(self, name, artist):
        self.name = name
        self.artist = artist


class LinkedList(object):
    def __init__(self):
        self.list = []

    def set_next(self, node):
        self.list.append(node)

    def print(self):
        for i, node in enumerate(self.list):
            print('{}: {} - {}'.format(i+1, node.name, node.artist))

    def delete(self, node):
        self.list.remove(node)

    def sort(self, sort_by, descending=False):
        self.list.sort(key=operator.attrgetter(sort_by), reverse=descending)


Song1 = Node("Silent Night", "John")
Song2 = Node("Last Christmas", "Andy")
Song3 = Node("Jingle Bells", "Mary")
music_collection = LinkedList()
music_collection.set_next(Song1)
music_collection.set_next(Song2)
music_collection.set_next(Song3)

music_collection.sort('artist', descending=True)
music_collection.print()

У меня на выходе:

1: Jingle Bells - Mary
2: Silent Night - John
3: Last Christmas - Andy

Answer 2

В целом, я думаю, что ваша реализация довольно сложная. Например, я не понимаю, почему необходимо вызывать метод LinkedList __init__ с какими-либо параметрами. Также я бы порекомендовал вам переименовать функцию next, так как она может быть перепутана с функцией с тем же именем протокола итератора. Возможно, вы захотите изучить более элегантные решения.

При этом попробуйте этот фрагмент кода в качестве функции printAll:

def printAll(self):
    pointer = self.head
    idx = 1

    while pointer is not None:
        print(f'{idx}: {pointer.data} - {pointer.artist}')
        pointer = pointer.next
        idx += 1