управлять дубликатами при вставке в связанный список

Question

Я написал алгоритм для вставки в связанный список объектов курса, отсортированных по их number переменной-члену. Это работает хорошо, за исключением случаев, когда я пытаюсь вставить дубликаты, например, два экземпляра 2420. Вывод списка __str__ в настоящее время выглядит следующим образом:

cs1400 Introduction to Programming Grade:3.6 Credit Hours: 4 
cs1410 C++ Programming Grade:2.6 Credit Hours: 4 
cs2420 Introduction to Data Structures Grade:3.2 Credit Hours: 4 
cs2810 Computer Architecture Grade:3.8 Credit Hours: 3 

, и вот мой код для метода вставки

def insert(self, course=None):
        """Insert the specified Course in Course Number ascending order.""" 
        def insert_helper(cursor, course):

            if course is None:
                return

            if course.number <= self.head.number: # start of the list
                self.head = course
                return

            if cursor.next is None or course.number <= cursor.next.number: # 
                course.next = cursor.next
                cursor.next = course
                return

            insert_helper(cursor.next, course)


        if self.head is None:
            self.head = course
            return
        cursor = self.head
        insert_helper(cursor, course)

Трюк охватывает мои мысли вокруг фреймов рекурсии. Я надеюсь, что скоро это получится лучше.

Answer 1

Я не считаю, что дублированные номера курсов сами по себе являются проблемой.

Здесь в вашей программе есть ошибка:

            if course.number <= self.head.number: # start of the list
                self.head = course
                return

Если вы когда-либо выполняли последние две строки в этом фрагменте кода ваш список становится одноэлементным списком, содержащим course и ничего больше.

Сравните это со следующим оператором if, где, если условие истинно, вы выполняете

                course.next = cursor.next

Вам нужно установить course.next на что-то в обоих местах.

Также обратите внимание, что если course.number <= self.head.number не верно во время первого вызова insert_helper, оно не будет истинным ни в одном из рекурсивные вызовы либо. Возможно, было бы лучше обработать этот случай до первого вызова этой функции.