Question

Write an implementation similar to the Priority Queue method (from chapter 26) to the linked list...

Write an implementation similar to the Priority Queue method (from chapter 26) to the linked list using node. (from chapter 24). Your code should utilize the selectionsort method from attached and create another method call selectionsort in linkedlist class. To demonstrate the usage of the selection sort method, you should manually create a link list of random integer (say of 5 numbers), and you need to demonstrate the use the selection sort to sorted the link list. Please submit your code and screenshots of your result by the due dates

class LinkedList:
    def __init__(self):
        self.length = 0
        self.head = None
    def add_first(self, cargo):
        node = Node(cargo)
        node.next = self.head
        self.head = node
        self.length += 1
    def print_backward(self):
        print("[", end=" ")
        if self.head is not None:
            self.head.print_backward()


class Node:
    def __init__(self, cargo=None, next=None):
        self.cargo = cargo
        self.next  = next

    def __str__(self):
        return str(self.cargo)

    def print_backward(self):
        if self.next is not None:
            tail = self.next
            tail.print_backward()
class LinkedList:
    def __init__(self):
        self.length = 0
        self.head = None

    def print_backward(self):
        print("[", end=" ")
        if self.head is not None:
            self.head.print_backward()

    def __str__(self):
        #need to complete here
        
    def add_first(self, cargo):
        node = Node(cargo)
        node.next = self.head
        self.head = node
        self.length += 1

    def selectionsort(self):
       #adjust the code below to make it work
       for i in range(0, len(self.items)):
           positionOfMin=i
           for j in range(i+1,len(self.items)):
               if self.items[j]

I'm almost done can you help modify the selection sort and write a def __str__

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

Note: Please maintain proper code spacing (indentation), just copy the code part and paste it in your compiler/IDE directly, no modifications required. Also, you cannot directly use the selection sort method using indexing, because we are not dealing with an array, but a linked list, it cannot be accessed using indices unless we implement __getitem__ and __setitem__ methods. But there is another way to implement the selection sort without indicing, which I did below. The algorithm is same, only the implementation is different.

#code

class Node:
    def __init__(self, cargo=None, next=None):
        self.cargo = cargo
        self.next = next

    def __str__(self):
        return str(self.cargo)

    # there was errors in this method, fixed it
    def print_backward(self):
        if self.next is not None:
            self.next.print_backward()
            print(", ", end="")
        print(self.cargo, end="")


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

    # completed this method also
    def print_backward(self):
        print("[", end="")
        if self.head is not None:
            self.head.print_backward()
        print("]")

    def __str__(self):
        data = '['
        # taking reference to head node
        node = self.head
        # looping until the last node
        while node != None:
            # appending cargo of current node to data
            data += str(node.cargo)
            # if there is a next node, appending ", "
            if node.next != None:
                data += ", "
            # advancing to next node
            node = node.next
        # closing "] and returning string
        data += "]"
        return data

    def add_first(self, cargo):
        node = Node(cargo)
        node.next = self.head
        self.head = node
        self.length += 1

    def selectionsort(self):
        # taking a reference to head node
        node = self.head
        # looping for length number of times (i=0 to length-1)
        for i in range(self.length):
            # storing this node as node with min value
            min_node = node
            # also storing as current node under check
            current = node
            # looping for length-i times
            for j in range(self.length - i):
                # if cargo of current node is less than that of min_node
                if current.cargo < min_node.cargo:
                    # setting current as new min_node
                    min_node = current
                # advancing to next node
                current = current.next
            # swapping cargo values of node and min_node
            temp = node.cargo
            node.cargo = min_node.cargo
            min_node.cargo = temp
            # advancing to next node
            node = node.next


# code for testing
import random

# creating a linked list
l = LinkedList()
# adding 10 random numbers to the list
for i in range(10):
    l.add_first(random.randint(1, 50))
# printing the list
print(l)
# sorting contents
l.selectionsort()
# printing the sorted list
print(l)

#output (random)

[3, 29, 25, 9, 47, 27, 3, 16, 31, 47]
[3, 3, 9, 16, 25, 27, 29, 31, 47, 47]

Add a comment
Know the answer?
Add Answer to:
Write an implementation similar to the Priority Queue method (from chapter 26) to the linked list...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Python question. i have to start from an empty linked list, using the method addNodeEnd() to...

    Python question. i have to start from an empty linked list, using the method addNodeEnd() to add the nodes containing the values (3*i+5)%17, where i is from 0 to 10. Then print the values of all the nodes in this linked list to the screen. This is the code that i created right here and i need help checking if i made any mistakes thanks! The code is below: class Node: def __init__(self, data): self.data = data self.next = None...

  • Python 3: Write a LinkedList method named contains, that takes a value as a parameter and...

    Python 3: Write a LinkedList method named contains, that takes a value as a parameter and returns True if that value is in the linked list, but returns False otherwise. class Node: """ Represents a node in a linked list """ def __init__(self, data): self.data = data self.next = None class LinkedList: """ A linked list implementation of the List ADT """ def __init__(self): self.head = None def add(self, val): """ Adds a node containing val to the linked list...

  • Python 3: Python 3: Write a LinkedList class that has recursive implementations of the add, display,...

    Python 3: Python 3: Write a LinkedList class that has recursive implementations of the add, display, remove methods. You may use default arguments and/or helper functions. class Node: """ Represents a node in a linked list """ def __init__(self, data): self.data = data self.next = None class LinkedList: """ A linked list implementation of the List ADT """ def __init__(self): self.head = None def add(self, val): """ Adds a node containing val to the linked list """ if self.head is...

  • from __future__ import annotations from typing import Any, Optional class _Node: """A node in a linked...

    from __future__ import annotations from typing import Any, Optional class _Node: """A node in a linked list. Note that this is considered a "private class", one which is only meant to be used in this module by the LinkedList class, but not by client code. === Attributes === item: The data stored in this node. next: The next node in the list, or None if there are no more nodes. """ item: Any next: Optional[_Node] def __init__(self, item: Any) ->...

  • PYTHON: Conan is writing a module to contain different implementations of trees. After his first tree,...

    PYTHON: Conan is writing a module to contain different implementations of trees. After his first tree, the BinaryTreeclass, he wrote test code and is having problems understanding the error. Locate his problem and explain how you would fix it. class Node(object): def __init__(self, data=None): self.data = data def __str__(self): return "NODE: " + str(self.data)    class Tree(object): def __init__(self): self.root_node = None self.size = 0    def __len__(self): return self.size    def add(self, data): raise NotImplementedError("Add method not implemented.")    def inorder_traversal(self): raise NotImplementedError("inorder_traversal...

  • # Declaring Node class class Node: def __init__(self, node_address): self.address = node_address self.next = None #...

    # Declaring Node class class Node: def __init__(self, node_address): self.address = node_address self.next = None # Creating empty list forwarding_list = Node() # Recurssive Method for add address def addAddress(node): if node.address == old_address: # Address is same if node.next == None: # Next is None node.next = Node(new_address) # Add Next print("Added") # Addedd else: # Next is not none print("Entry already exists") elif node.next != None: # Check Next Node addAddress(node.next, old_address, new_address) def addEntry(forwarding_list):# Method for add...

  • PYTHON -------------------------------------------------------- class LinkedList:    def __init__(self):        self.__head = None        self.__tail = None   

    PYTHON -------------------------------------------------------- class LinkedList:    def __init__(self):        self.__head = None        self.__tail = None        self.__size = 0    # Return the head element in the list    def getFirst(self):        if self.__size == 0:            return None        else:            return self.__head.element        # Return the last element in the list    def getLast(self):        if self.__size == 0:            return None        else:            return self.__tail.element    # Add an element to the beginning of the list    def addFirst(self, e):        newNode = Node(e) # Create a new node        newNode.next = self.__head # link...

  • I'm trying to sort a list of students from a text file in python(3.7) with three separate sorting functions (Bubble, selection, insert) I'm not sure to why as its not working I'm going to...

    I'm trying to sort a list of students from a text file in python(3.7) with three separate sorting functions (Bubble, selection, insert) I'm not sure to why as its not working I'm going to guess its because I'm not using the swap function I built. Every time I run it though I get an error that says the following Traceback (most recent call last): File "C:/Users/tkoto/Desktop/SearchAndSortLab.py", line 146, in <module> main() File "C:/Users/tkoto/Desktop/SearchAndSortLab.py", line 122, in main studentArray.gpaSort() File "C:/Users/tkoto/Desktop/SearchAndSortLab.py",...

  • class Node(object): def __init__(self, data, next=None): self.data = data self.next = next class List(object):    def...

    class Node(object): def __init__(self, data, next=None): self.data = data self.next = next class List(object):    def __init__(self): self.head = None self.tail = None Implement the following functions for Linked List in Python and use the constructors above : Copy(lList) Builds and returns a copy of list ItemAt(List,i) Returns the data item at position i in list Pop(List,i=0) Remove item at position i in list. If i is not specified, it removes the first item in list Count(List,x) Returns the number...

  • urgent , and what is the big-O? Write a Priority Queue method, end_of_path(path), that is given...

    urgent , and what is the big-O? Write a Priority Queue method, end_of_path(path), that is given a string, path, as input, which represents the path from the root to the node of interest, and if there is a node at the end of that path, the method returns the value at that node, otherwise returns None. path is a string containing just "L"s and "R"s, representing left child and right child. So, given a priority queue represented by the list...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT