Python code that sorts books

Question

I am currently a student just starting to learn python and I need help improving my code for a school assignment. I've already written the code for the program, just need suggestions on how to improve it or make it better.

Uncle Joe started the Greenville Secondhand Bookstore in 2000. As years passed, the number of books in his store increased significantly. He can no longer keep track of their location in his store. Knowing you are from School of informatics & IT, he has approached you to develop a program (in Python) that could help him to keep track of the books.

Your program should fulfil the following requirement:

a. AddBookToFront(newBook) : This method will create a new Node with the new Book object as its data value and then add the newly created node to the front of the linked list.

b. AddBookAtPosition(newBook, n) : This method will create a new Node with the new Book object as its data value and then add the newly created node at position n of the linked list. Assume that the first node of the linked list has a position number of 0 and the second node has a position number of 1 and so on.

c. RemoveBookAtPosition(n): This method will remove the node at position n in the linked list. Assume that the first node of the linked list has a position number of 0 and the second node has a position number of 1 and so on.

d. DisplayBook(): This method will traverse the linked list from its first node to its last node and print the data value (i.e., the id, bookName and authorName of the Book object) of each node.

e. SortByAuthorName(): This method will sort the linked list by the book author’s name in ascending order.

Notes:

• You are allowed to make changes to the LinkedList and Node classes as you deemed fit.

• You are not allowed to use List for this question.

• You are not allowed to use any existing Python libraries to do sorting.

• Your solution should use objects and classes effectively.

So here is my code, I'm not too sure if I did it correctly or not so please do tell me if there are any mistakes I made or what I should do that would be better.

class Book:
 def __init__(self,id,bookName,authorName,nextNode=None):
 self.id = id
 self.bookName = bookName
 self.authorName = authorName
 self.nextNode = nextNode
 def getId(self):
 return self.id
 def getBookName(self):
 return self.bookName
 def getAuthorName(self):
 return self.authorName
 def getNextNode(self):
 return self.nextNode 
 def setNextNode(self,val):
 self.nextNode = val 
class LinkedList:
 def __init__(self,head = None):
 self.head = head
 self.size = 0
 def getSize(self):
 return self.size
 def AddBookToFront(self,newBook):
 newBook.setNextNode(self.head)
 self.head = newBook
 self.size+=1
 def DisplayBook(self):
 curr = self.head
 while curr:
 print(curr.getId(),curr.getBookName(),curr.getAuthorName()) 
 curr = curr.getNextNode()
 def RemoveBookAtPosition(self,n):
 prev = None
 curr = self.head
 curPos = 0
 while curr:
 if curPos == n:
 if prev:
 prev.setNextNode(curr.getNextNode())
 else:
 self.head = curr.getNextNode()
 self.size = self.size - 1
 return True 
 prev = curr
 curr = curr.getNextNode() 
 curPos = curPos + 1 
 return False
 def AddBookAtPosition(self,newBook,n):
 curPos = 1
 if n == 0:
 newBook.setNextNode(self.head)
 self.head = newBook
 self.size+=1
 return
 else:
 currentNode = self.head
 while currentNode.getNextNode() is not None:
 if curPos == n:
 newBook.setNextNode(currentNode.getNextNode())
 currentNode.setNextNode(newBook)
 self.size+=1
 return
 currentNode = currentNode.getNextNode()
 curPos = curPos + 1
 if curPos == n:
 newBook.setNextNode(None)
 currentNode.setNextNode(newBook)
 self.size+=1
 else:
 print("cannot add",newBook.getId(),newBook.getBookName(),"at that position")
 def SortByAuthorName(self):
 for i in range(1,self.size):
 node1 = self.head
 node2 = node1.getNextNode()
 while node2 is not None:
 if node1.authorName > node2.authorName:
 temp = node1.id
 temp2 = node1.bookName
 temp3 = node1.authorName
 node1.id = node2.id
 node1.bookName = node2.bookName
 node1.authorName = node2.authorName
 node2.id = temp
 node2.bookName = temp2
 node2.authorName = temp3
 node1 = node1.getNextNode()
 node2 = node2.getNextNode() 
myLinkedList = LinkedList()
nodeA = Book("#1","cool","Isaac")
nodeB = Book("#2","amazing","Alfred")
nodeC = Book("#3","hello","John")
nodeD = Book("#4","why","Chase")
nodeE = Book("#5","good","Mary")
nodeF = Book("#6","hahaha","Radin")
myLinkedList.AddBookToFront(nodeA)
myLinkedList.AddBookToFront(nodeB)
myLinkedList.AddBookToFront(nodeC)
myLinkedList.AddBookAtPosition(nodeD,1)
myLinkedList.AddBookAtPosition(nodeE,1)
myLinkedList.AddBookAtPosition(nodeF,1)
myLinkedList.RemoveBookAtPosition(2)
myLinkedList.RemoveBookAtPosition(2)
myLinkedList.DisplayBook()
myLinkedList.SortByAuthorName()
print(myLinkedList.getSize())
myLinkedList.DisplayBook()

• Bailey Parker: I'm a little concerned that a professor expects method names like AddBookToFront that are so not PEP8 (addBookToFront is infuriatingly java, but no one should capitalize method names, this isn't golang).
• Raimund Krämer: @BaileyParker method and property names are capitalized by convention in C#. But I agree that no one should capitalize method names in Python (and Java).
• Brōtsyorfuzthrāx: Your code could use some comments to help those who analyze it to orient themselves better.

Answer 1

It looks good and readable IMHO. For brownie points, you could:

• modify the structure a bit. Not every LinkedList will contain books. Similarly, not every Node in a LinkedList will have an AuthorName. You could define 4 separate classes : Node, Book, LinkedList, and Bookstore(LinkedList).

• define a data attribute for Node.

• define __str__ for Node, which just delegates to data.__str__.

• define __str__ for Book, which joins id, bookName and authorName.

• run autopep8 to fix a few minor formatting problems (e.g. self.size+=1 -> self.size += 1).

• add a delimiter to DisplayBook() between id, bookName and authorName. If the names have spaces, you wouldn't know what the name of the book is.

• write tests, for example to check that the LinkedList has a correct length or that DisplayBook() displays the names in correct order. You'd be allowed to use Python lists and sorted() inside the tests. DisplayBook() only prints information and doesn't return anything, so you might have to redirect stdout.

• move the examples at the end to main() and check if you're importing the file as a library or running the script. See here.

• suggest better method names to your teacher. Python classes are CamelCase but methods are snake_case. Also DisplayBook seems to suggest that it displays one single book. It could be called display_books.

• define a generator for LinkedList, which would iterate over every Node. You might not be allowed to use it in your answer, it would make it much easier to use your library, though.

Answer 2

A little late here as I just got back in front of a non-mobile device, so let me try to add some new points:

Most importantly (with the caveat that I'm super pedantic), the format of this assignment concerns me. I'd be weary of a professor that assigns something like this. Assuming you copied the instructions verbatim, it seems like this person would struggle with identifying pythonic patterns. And this will only be to your detriment. Names like AddBookToFront are definitely not pythonic. One thing to strive for is consistency. It will only bite you in the future if you learn this contrived way and then start doing "real Python" and realize that everyone else does it differently. In short, I'd hate to see some of the bad habits that this kind of assignment forces on you hurt you in your future Python endeavors. So with that said, here's a list of things that you can't change for this assignment, but you should know:

• In Python we prefer method and variable names that are snake_case, class names that are CapitalizedCamelCase, and constants that are UPPER_SNAKE_CASE because this is what is recommended by PEP8. There are tools that can help lint your code for PEP8 conformity, which should help in keeping your code clean, readable, and following good practices
• The assignment mentions a new Book object, but doesn't really specify it. Is it provided? Do you have to make it? Overall, the assignment feels underspecified.
• AddBookToFront and AddBookAtPosition are not pythonic. Since we strive for consistency, look to how list does it. AddBookToFront would be bookstore.insert(book, 0) (where 0 is the index at which you want to insert it). AddBookAtPosition would be bookstore.insert(book, position).
• RemoveBookAtPosition would not be a method. list has a remove method which removes by value (ex. [1,'a',3].remove('a') gives [1,3]). For removing at an index, we would define the __getitem__ and __delitem__ methods. These allow you to use brackets to index into any class you write: bookstore[1] (gives the second book), del bookstore[10] (deletes the 11th book)
• SortByAuthorName is also pretty unpythonic (although perhaps in some domains it could work). Again looking at list, the general approach is a sort() method. To change what is sorted by we have a key parameter which is a function that returns the value to be sorted on: bookstore.sort(key=lambda book: book.authorName) (this sorts the bookstore by authorName)
• DisplayBook should be DisplayBooks
• bookName in Book is redundant. It should just be name.
• This professor has not addressed edge cases at all. This is something you should be thinking critically about from the beginning. For example, what happens if you try to remove a book at position 100 in a list with only 2 books? (The pythonic approach would be to raise IndexError)

With those pedantics out of the way, you should next consider reusability. Say you had already implemented a linked list. Then you receive this assignment. You implement it and get a 100% back. You're happy that all of your code worked. Now the next assignment comes out and the professor adds the following stipulation: "Uncle Joe is now selling second hand movies. Can you deliver a solution in python that handles both his bookkeeping and movie-keeping needs?" If you had implemented the first assignment as you shared with us, you'd have to copy and paste and rewrite a lot of code. Potentially while doing this you could make a change that breaks your code and do poorly on that assignment.

Since you already had a working LinkedList, is there anything you could do to make life easier for your future self? Yes! You already have a class with a single responsibility that properly handles al of the operations you expect: LinkedList. So why change it (and possibly break it)? Instead, you should look to create a new class, say Bookstore, which uses your LinkedList to perform that operations you need on it. Additionally, this requires that your Node stores a Book instead of doubling as a node and a book. This is good, though, because then you separate what it means to be a linked list node and what it means to be a book. This makes reasoning about and testing code much easier. In this way you never modify your LinkedList or Node, so (assuming they are correct) your only errors can come from misusing it. With the API I described above, your bookstore could look like this:

class Bookstore:
 def __init__(self):
 self._books = LinkedList()
 def AddBookToFront(self, book):
 self._books.insert(book, 0)
 def AddBookAtPosition(self, book, position):
 self._books.insert(book, position)
 def RemoveBookAtPosition(self, position):
 del self._books[position]
 def SortByAuthorName(self):
 self._books.sort(key=lambda book: book.authorName)

This is much more manageable code. Additionally, as a consequence of conforming to the list API, you can replace LinkedList with a list at any time (this could be useful for testing, when you just care about asserting the correctness of Bookstore's behavior). This is likely what your professor means by "Your solution should use objects and classes effectively."

Another benefit of separating Node and Book is you avoid the error-prone copying you do in SortByAuthorName to swap two books. If they are separate, swapping two nodes is as easy as node_one.value, node_two.value = node_two.value, node_one.value.

One neat Python trick (that it sounds like you can use) is namedtuples. They are great for value objects--objects who are immutable and are defined by their values. Book is a great example of this. It is defined by its values id, name, author_name:

from collections import namedtuple
Book = namedtuple('Book', ('id', 'name', 'author_name'))

Now let's focus on just the LinkedList part of this assignment.

First, I'd say your Node class doesn't need getters and setters for the value and next node. node.value, node.next, and node.next = another_node are fine.

One thing that should be clear from re-reading your code is you have to special case the head pointer. This makes for a lot more code (and a lot more opportunities to make mistakes). One trick that I like is having the head always be an empty Node. You never include this node in the size of the list or when iterating through the list, but it makes things a lot easier. It works like this:

class LinkedList:
 def __init__(self):
 self._head = Node(None) # value = None, next = None

The advantage here is say you want to remove some arbitrary node from your list. In a normal linked list, you have to be careful that if you remove the head that you update the head pointer. With the above trick, the head node is always there (and can't be deleted), so you never have to special case things for the head. For a normal linked list, removing the head would be something like:

if node is self._head:
 self._head = self._head.next
else:
 previous_node.next = node.next

With this trick it's one line:

previous_node.next = node.next

This trick makes it such that every node that you care about (we can ignore the first empty node) always has a previous_node. So, you don't have to treat any of the nodes specially.

As you've probably noticed in insert and __del__, there's a lot of complexity in traversing and modifying a linked list. As a result it's very easy to make a mistake. If we think back to what we did before (use an already working LinkedList to build our Bookstore without worrying about breaking the LinkedList), we can do something similar here. Both of these functions have the same first step: find the node and previous node at a certain position. If you wrote a helper method _get_node_at(self, position), you could simplify these two (and prevent any errors from copying and pasting that code between the two). Assuming _get_node_at returns a tuple (previous_node, node) where node is the positionth node and previous node is the one before it, your insert and remove become super simple:

def insert(value, position):
 # Create a new node
 new_node = Node(value)
 # Find the nodes that will be before and after it
 previous_node, node = self._get_node_at(position)
 # Stitch it into the list
 previous_node.next = new_node
 new_node.next = node
def __del__(self, position):
 # Find the node to remove and the node before it
 previous_node, node = self._get_node_at(position)
 # Remove node by stitching the list around it
 previous_node.next = node.next

Note that there is an edge case here that you must consider. insert(x, len(linked_list)) should insert at the end so _get_node_at needs to return a good previous_node and node for that. But del linked_list[len(linked_list)] is not valid. I'll leave it to you to sort out how to handle that.

General comments:

• Use """Docstrings.""" at the beginning of every method to document what it does.
• Use white space to make concepts clearer. Just like we write in paragraphs, you should structure you code into logical, coherent blocks that each achieve a singular goal
• Spaces after commas!
• Use f strings: ex. print(f'cannot add {book.id} {book.name} at that position') (or format strings if you're not using Python 3.6)
• Look into unittest to see how you can write automated tests for your code
• In python we rarely use temp variables. Instead we exchange values using tuples. Ex. to flip a and b, we do a, b = b, a
• When writing a library for others to use, you shouldn't have any code like what you have at the very bottom (the test code), because it produces side effects. You should only run that code if someone directly runs your script with python3 bookstore.py (instead of import bookstore). To do this we create a main function and only call it when __name__ == '__main__':

Example:

def main():
 bookstore = Bookstore()
 bookstore.AddBookToFront(Book(123, 'Fire and Fury', 'Michael Wolff'))
 # ... etc ...
if __name__ == '__main__':
 main()

And one final note:

I can see your deleted StackOverflow question where you copy and pasted that entire problem and asked for a solution. It seems like another student in your class had a similar idea. That was 13 hours ago. You posted this question 6 hours ago. I hope you realized that cheating is only going to hurt you in the future. You won't learn and you'll struggle with harder concepts in the future. I hope you came about the solution honestly. If that is the case and you did this all on your own in 7 hours, then you really don't need to cheat. Sure, your solution has lots of room for improvement and a few small bugs, but it was a fantastic attempt.

So in summary. Very nice job. Hopefully some of the above is helpful to you. And do enjoy your continuing Python adventures!

• Eric Duminil: Good, solid answer!
• Baldrickk: This is what I wish all my answers across all of SE could be like... Detailed but concise, and really digging to the heart of the answer. It makes me feel bad about some of my code too...

Answer 3

• Make your LinkedList more generic, so you can use it for every type. Then subtype it, making a subclass LinkedBookList.
• Move the logic to print the fields of a Book to the subclass LinkedBookList. The LinkedList shouldn't know about it.
• Don't make the Book a node. Make a Node type and have it hold the Book. (This is actually a part of the task, which you didn't quite get right; maybe you misunderstood it as the Node holding the Book's data, but the Node holds the Book as data.)

• Eric Duminil: Well spotted for the last point!
• Ash Chia: Thanks for pointing out the last point! yeah I didn't really understand that part thanks for clearing things up for me :)