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__
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]
Write an implementation similar to the Priority Queue method (from chapter 26) to the linked list...
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 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, 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 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, 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 # 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 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 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 __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 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...