manage duplicates when inserting into a linked list

134
February 09, 2020, at 08:50 AM

I wrote an algorithm for inserting into a linked list of Course objects sorted by their number member variable. It works well, except when I try to insert duplicates, like two instances of 2420 for example. The list __str__ output currently looks like this:

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 

and here is my code for the insert method

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)

The trick is wrapping my mind around the recursion frames. I hope to get a better hang of this soon.

Answer 1

I don't believe duplicated course numbers are the problem, per se.

There is an error in your program here:

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

If you ever execute the last two lines in this code snippet, your list becomes a singleton list containing course and nothing else.

Compare this to the next if statement, where if the condition is true then you execute

                course.next = cursor.next

You need to set course.next to something in both places.

Also notice that if course.number <= self.head.number is not true during the first call to insert_helper, it won't be true on any of the recursive calls either. It might have been better to handle this case before the first call to that function.

READ ALSO
Initializing python Defaultdict

Initializing python Defaultdict

Is there a way to initialize a dict the following way:

167
Django include templates in markdown

Django include templates in markdown

I have Django templates written in MarkdownI'd like to implement template tag to include rendered markdown

151
How can I authorise an installation of an Electron application?

How can I authorise an installation of an Electron application?

If you needed to do some kind of an authorization mechanism to an Electron application, what libraries/frameworks would you use for it?

126
How to start launch puppeteer before using it

How to start launch puppeteer before using it

I am currently working on a web-scraping project and need to reduce waiting time to as little as possibleSince I am making a restful API I want to launch puppeteer before someone makes a request

160