Python Forum
I Can't Get This Sorting Function In This LinkedList Code To Work
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
I Can't Get This Sorting Function In This LinkedList Code To Work
#1
Hi everyone, I am new here and the question that I am posting here is part of my School Assignment For Data And Algorithms.

This Is The Question For The Assignment

Uncle Tom started his Secondhand Bookstore in 2000. Over The Years, the amount of books in his store increased significantly. He Has asked you to develop A Program In Python To assist him in managing his book inventory.

Your program should fulfill 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.
• You are to write your own script to test your solutions.

Current Completion Status:
I have completed all the objectives except the sortByAuthorName objective that I have tried to code but am still unable to get the code to run.

My Current Completed Code
class Node:                                                                     
     def __init__(self, val, next_ref):                                         
         self.val = val;                                                        
         self.next = next_ref;    
head= None;                                                                                  
class LinkedList:                                                             
    def AddBookToFront(val):
        global head;
        new_node = Node(val, None)
        new_node.next = head
        head = new_node

    # inserts new node at specific position in singly linked list.
    def AddBookAtPosition(val, position):                                                 
        global head;                                                          
        current_node = head;                                                        
        while(position > 1):                                                        
            position -= 1;                                                          
            current_node = current_node.next;                                       
        temp_next = current_node.next;                                              
        node = Node(val, temp_next);                                                
        current_node.next = node;                                                               
                
    # prints singly linked list values.                                                                    
    def DisplayBook():                                                               
        global head;                                                          
        print("Single linked list");                                                
        current_node = head;                                                        
        print ("head -->",);                                                          
        while(current_node is not None):                                            
            print (current_node.val, "-->",);                                         
            current_node = current_node.next;                                       
        print ("End");               
                                              
    def RemoveBookAtPosition(position):
        global head;
        # If linked list is empty
        if head == None:
            return

        # Store head node
        temp = head

        # If head needs to be removed
        if position == 0:
            head = temp.next
            temp = None
            return

        # Find previous node of the node to be deleted
        for i in range(position -1 ):
            temp = temp.next
            if temp is None:
                break

        # If position is more than number of nodes
        if temp is None:
            return
        if temp.next is None:
            return

        # Node temp.next is the node to be deleted
        # store pointer to the next of node to be deleted
        next = temp.next.next

        # Unlink the node from linked list
        temp.next = None

        temp.next = next

    def mergeLists(l1, l2):
        temp = None
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        if l1.data <= l2.data:
            temp = l1
            temp.next = mergeLists(l1.next, l2)
        else:
            temp = l2
            temp.next = mergeLists(l1, l2.next)
        return temp

    # Defining function which will sort the linked list using mergeSort
    def mergeSort():
        global head;
        if head is None or head.next is None:
            return head
        l1, l2 = divideList(head)
        l1 = mergeSort(l1)
        l2 = mergeSort(l2)
        head = mergeLists(l1, l2)
        return head

    # Defining function which will divide a linked list into two equal linked lists
    def divideList():
        global head;
        slow = head                     # slow is a pointer to reach the mid of linked list
        fast = head                     # fast is a pointer to reach the end of the linked list
        if fast:
            fast = fast.next            
        while fast:
            fast = fast.next            # fast is incremented twice while slow is incremented once per loop
            if fast:
                fast = fast.next
                slow = slow.next
        mid = slow.next
        slow.next = None
        return head, mid

ll=LinkedList    
ll.AddBookToFront(10);
ll.AddBookToFront(20);
ll.DisplayBook();                                                                                                                           
ll.AddBookToFront(30);                                                         
ll.DisplayBook();                                                               
ll.AddBookAtPosition(45, 2);                                                         
print ("After insert node at 2");                                             
ll.DisplayBook();                                                               
ll.RemoveBookAtPosition(2)                                                        
print ("After removal of node @ 2nd position");                                           
ll.DisplayBook();   
ll.mergeSort()                    
Output Log:

Single linked list
head -->
20 -->
10 -->
End
Single linked list
head -->
30 -->
20 -->
10 -->
End
After insert node at 2
Single linked list
head -->
30 -->
20 -->
45 -->
10 -->
End
After removal of node @ 2nd position
Single linked list
head -->
30 -->
20 -->
10 -->
End
Traceback (most recent call last):
File "C:\Users\TP_baseline\Desktop\DSAG\ProjecTest4.py", line 124, in <module>
ll.mergeSort()
File "C:\Users\TP_baseline\Desktop\DSAG\ProjecTest4.py", line 90, in mergeSort
l1, l2 = divideList(head)
NameError: name 'divideList' is not defined

I have been trying to fix this issue for the whole day but to no avail. Any guidance or advise to guide me to rectifying this error would be greatly appreciated.
Reply
#2
First of all, you're doing your class kind of wrong. Every class method has a self argument with which you reference variables and methods within that class.

So instead of:
head = None
class Linked:
   def foo():
      global head
      head = Node()
You should have this:

class Linked:
   def __init__(self):  
      """This is the class constructor.  You can initialize "member variables" here.
      """
      self.head = None

   def AddBookToFront(self, val):
      # you can reference head with self.head
      tmp = self.head
      self.head = Node()
      self.head.next = tmp
Then to reference other methods within the same class, you also use self:
class Linked:
   def __init__(self):  
      """This is the class constructor.  You can initialize "member variables" here.
      """
      self.head = None

   def mergeSort(self):
      # do stuff...
      self.divideList(self.head)
In any event you can't call divideList because it's part of the LinkedList class. It might work if you call LinkedList.divideList(head) but you should really consider making the other changes I mentioned because that's the correct way to write classes in Python.

Edited to add:

You don't create class instances ("instantiate") a class with ll = LinkedList; that just creates an alias or another way to refer to LinkedList.

You create a class instance with: ll = LinkedList() which invokes the constructor.
Reply
#3
(Jan-09-2018, 12:58 PM)mpd Wrote: First of all, you're doing your class kind of wrong. Every class method has a self argument with which you reference variables and methods within that class.

So instead of:
head = None
class Linked:
   def foo():
      global head
      head = Node()
You should have this:

class Linked:
   def __init__(self):  
      """This is the class constructor.  You can initialize "member variables" here.
      """
      self.head = None

   def AddBookToFront(self, val):
      # you can reference head with self.head
      tmp = self.head
      self.head = Node()
      self.head.next = tmp
Then to reference other methods within the same class, you also use self:
class Linked:
   def __init__(self):  
      """This is the class constructor.  You can initialize "member variables" here.
      """
      self.head = None

   def mergeSort(self):
      # do stuff...
      self.divideList(self.head)
In any event you can't call divideList because it's part of the LinkedList class. It might work if you call LinkedList.divideList(head) but you should really consider making the other changes I mentioned because that's the correct way to write classes in Python.

Edited to add:

You don't create class instances ("instantiate") a class with ll = LinkedList; that just creates an alias or another way to refer to LinkedList.

You create a class instance with: ll = LinkedList() which invokes the constructor.

Thanks MPD, still trying to figure my way through Python. Would you mind if I PM you my rectified code after I have it rectified ?
Thanks A Million
Jay
Reply
#4
Quote:Would you mind if I PM you my rectified code after I have it rectified ?
If the code works, you don't have to do anything. If you're still having problems you should keep posting in this thread.
Reply
#5
Hi Everyone, Just An Update Here, I have followed the First Answer By MPD and corrected my code and this is the corrected code as per my understanding from MPD's answer..
class Node:                                                                     
     def __init__(self, val):                                         
         self.val = val;                                                        
         self.next = None;                                                                               
class LinkedList:   
    def __init__(self):
        self.head = None

    def AddBookToFront(self,val):
             # 1 & 2: Allocate the Node &
        #        Put in the data
        new_node = Node(val)
             
        # 3. Make next of new Node as head
        new_node.next = self.head
             
        # 4. Move the head to point to new Node 
        self.head = new_node

    # inserts new node at specific position in singly linked list.
    def AddBookAtPosition(self, val, position):                                                                                                          
        current_node = self.head;                                                        
        while(position > 1):                                                        
            position -= 1;                                                          
            current_node = current_node.next;                                       
        temp_next = current_node.next;                                              
        node = Node(val, temp_next);                                                
        current_node.next = node;                                                               
                
    # prints singly linked list values.                                                                    
    def DisplayBook(self):                                                                                                                        
        print("Single linked list");                                                
        current_node = self.head;                                                        
        print ("head -->",);                                                          
        while(current_node is not None):                                            
            print (current_node.val, "-->",);                                         
            current_node = current_node.next;                                       
        print ("End");               
                                              
    def RemoveBookAtPosition(self,position):
        # If linked list is empty
        if self.head == None:
            return

        # Store head node
        temp = self.head

        # If head needs to be removed
        if position == 0:
            self.head = temp.next
            temp = None
            return

        # Find previous node of the node to be deleted
        for i in range(position -1 ):
            temp = temp.next
            if temp is None:
                break

        # If position is more than number of nodes
        if temp is None:
            return
        if temp.next is None:
            return

        # Node temp.next is the node to be deleted
        # store pointer to the next of node to be deleted
        next = temp.next.next

        # Unlink the node from linked list
        temp.next = None

        temp.next = next

    def mergeLists(l1, l2):
        temp = None
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        if l1.data <= l2.data:
            temp = l1
            temp.next = mergeLists(l1.next, l2)
        else:
            temp = l2
            temp.next = mergeLists(l1, l2.next)
        return temp

    # Defining function which will sort the linked list using mergeSort
    def mergeSort(self):
        if self.head is None or self.head.next is None:
            return head
        l1, l2 = self.divideList(self.head)
        l1 = mergeSort(l1)
        l2 = mergeSort(l2)
        head = mergeLists(l1, l2)
        return head

    # Defining function which will divide a linked list into two equal linked lists
    def divideList(self):
        slow = self.head                     # slow is a pointer to reach the mid of linked list
        fast = self.head                     # fast is a pointer to reach the end of the linked list
        if fast:
            fast = fast.next            
        while fast:
            fast = fast.next            # fast is incremented twice while slow is incremented once per loop
            if fast:
                fast = fast.next
                slow = slow.next
        mid = slow.next
        slow.next = None
        return head, mid

ll=LinkedList()    
ll.AddBookToFront(10);
ll.AddBookToFront(20);
ll.DisplayBook();                                                                                                                           
ll.AddBookToFront(30);                                                         
ll.DisplayBook();      
ll.AddBookAtPosition(45,2)                                                                                                                 
print ("After insert node at 2");                                             
ll.DisplayBook();                                                               
ll.RemoveBookAtPosition(2)                                                        
print ("After removal of node @ 2nd position");                                           
ll.DisplayBook();   
ll.mergeSort(ll.head)                    
The Areas Of Code That Are Showing Up As Errors Are
 def AddBookAtPosition(self, val, position):                                                                                                          
        current_node = self.head;                                                        
        while(position > 1):                                                        
            position -= 1;                                                          
            current_node = current_node.next;                                       
        temp_next = current_node.next;                                              
        node = Node(val, temp_next);                                                
        current_node.next = node;         
And
def mergeLists(l1, l2):
        temp = None
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        if l1.data <= l2.data:
            temp = l1
            temp.next = mergeLists(l1.next, l2)
        else:
            temp = l2
            temp.next = mergeLists(l1, l2.next)
        return temp

    # Defining function which will sort the linked list using mergeSort
    def mergeSort(self):
        if self.head is None or self.head.next is None:
            return head
        l1, l2 = self.divideList(self.head)
        l1 = mergeSort(l1)
        l2 = mergeSort(l2)
        head = mergeLists(l1, l2)
        return head

    # Defining function which will divide a linked list into two equal linked lists
    def divideList(self):
        slow = self.head                     # slow is a pointer to reach the mid of linked list
        fast = self.head                     # fast is a pointer to reach the end of the linked list
        if fast:
            fast = fast.next            
        while fast:
            fast = fast.next            # fast is incremented twice while slow is incremented once per loop
            if fast:
                fast = fast.next
                slow = slow.next
        mid = slow.next
        slow.next = None
        return head, mid
Error Indications
When I try To Use The AddBoookToPosition command I get this error message...
Error:
Traceback (most recent call last): File "C:\Users\TP_baseline\Desktop\DSAG\ProjecTest4.py", line 120, in <module> ll.AddBookAtPosition(45,2) TypeError: AddBookAtPosition() takes 2 positional arguments but 3 were given
When I try to run the sorting system
Error:
Traceback (most recent call last): File "C:\Users\TP_baseline\Desktop\DSAG\ProjecTest4.py", line 126, in <module> ll.mergeSort(ll.head) TypeError: mergeSort() takes 1 positional argument but 2 were given
My Code Output Is
Output:
Single linked list head --> 20 --> 10 --> End Single linked list head --> 30 --> 20 --> 10 --> End After insert node at 2 Single linked list head --> 30 --> 20 --> 10 --> End After removal of node @ 2nd position Single linked list head --> 30 --> 20 --> End Traceback (most recent call last): File "C:\Users\TP_baseline\Desktop\DSAG\ProjecTest4.py", line 126, in <module> ll.mergeSort(ll.head) TypeError: mergeSort() takes 1 positional argument but 2 were given
Thanks In Advance For Any Guidance For Me To Solve The Problem
Reply
#6
Don't end your lines with semi-colons and look at how you're instantiating the Node in AddBookToPosition

Also, your mergeLists methods should also be made into class methods.
Reply
#7
def AddBookAtPosition(self, val, position):                                                                                                          
        current_node = self.head                                                      
        while(position > 1):                                                        
            position -= 1                                                          
            current_node = current_node.next                                      
        temp_next = current_node.next                                             
        node = Node(val, temp_next)                                               
        current_node.next = node 
Is this code correct for the AddBookTo Position Code ?
Also is there a mistake with the instantiating of the AddBookToPosition ?
Thanks Again
Jay
Reply
#8
What version of python are you running and on which OS?

I don't know why it's complaining about AddBookToPosition it looks correct. When I copy/pasted your code and ran it in Python 2 and 3, I got this error:

Error:
Traceback (most recent call last): File "foo.py", line 120, in <module> ll.AddBookAtPosition(45,2) File "foo.py", line 27, in AddBookAtPosition node = Node(val, temp_next); TypeError: __init__() takes exactly 2 arguments (3 given)
Reply
#9
Hi MPD, I am using Python 3.6 on Windows 10
Reply
#10
I get the same error on Windows as Linux:
Error:
Traceback (most recent call last): File "foo.py", line 120, in <module> ll.AddBookAtPosition(45,2) File "foo.py", line 27, in AddBookAtPosition node = Node(val, temp_next); TypeError: __init__() takes 2 positional arguments but 3 were given
Look at how you've defined the __init__ method in Node and then how you're invoking it (i.e., creating a new Node object) at line 27 in AddBookAtPosition.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  my simple code wont work! help! simon12323121 2 1,990 Sep-05-2021, 09:06 AM
Last Post: naughtyCat
  My code does not work as expected (pygame) rohes_kaugummi 1 1,532 Aug-26-2021, 03:13 PM
Last Post: deanhystad
  I wrote a code but it does not work out as expected chinitayao226 2 1,835 Sep-23-2020, 09:14 PM
Last Post: SnowwyWolf
  A program for backing up documents (doesnt work(code is inside)) Richard_SS 4 3,364 Jun-05-2019, 03:47 PM
Last Post: heiner55
  CODE for Bubble sorting an unsorted list of 5 numbers. SIJAN 1 2,255 Dec-19-2018, 06:22 PM
Last Post: ichabod801
  Why doesn't this print function work? wlsa 3 3,357 Jun-15-2018, 04:01 PM
Last Post: woooee
  Need help with getting this voting eligiblity code to work Beastly 1 2,490 Aug-16-2017, 03:46 PM
Last Post: ichabod801
  Write a function sorting(L)? MoIbrahim 11 8,151 Apr-22-2017, 11:45 AM
Last Post: idontreallywolf
  Why can't this code work. sexualpanda 2 3,380 Feb-06-2017, 04:03 PM
Last Post: ichabod801

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020