//I have made utility functions
getMin(),getMax(),deleteNode()
class Node{
char item;
Node next;
Node(char c){
item=c;
next=null;
}
}
class InsertSort{
public static void main(String[] args){
Node
head=initializeList("ilovedata");
System.out.println("\n List Before
selectionSort_acs");
printList(head);
head=selectionSort_asc(head);
System.out.println("\n List After
selectionSort_asc");
printList(head);
// Expected answer: -> a -> a
-> d -> e -> i -> l -> o -> t -> v
head=initializeList("ilovedata");
System.out.println("\n List Before
selectionSort_decs");
printList(head);
head=selectionSort_desc(head);
System.out.println("\n List After
selectionSort_desc");
printList(head);
// Excepted answer: -> v -> t
-> o -> l -> i -> e -> d -> a -> a
}
public static Node selectionSort_asc(Node head){
Node
result=null,min,cur=null;
//INSERTED CODE HERE
//firstly initialize result
if(head!=null){
min=getMin(head);
result=min;
head=deleteNode(head,min);
}
//then insert the nodes one by
one
for(cur=result;head!=null;cur=cur.next){
min=getMin(head);
cur.next=min;
head=deleteNode(head,min);
}
if(cur!=null)
cur.next=null;
return result;
}
public static Node selectionSort_desc(Node
head){
Node
result=null,max,cur=null;
//INSERTED CODE HERE
//firstly initialize result
if(head!=null){
max=getMax(head);
result=max;
head=deleteNode(head,max);
}
//then insert the nodes one by
one
for(cur=result;head!=null;cur=cur.next){
max=getMax(head);
cur.next=max;
head=deleteNode(head,max);
}
if(cur!=null)
cur.next=null;
return result;
}
//Method to find node having minimum value of
item
public static Node getMin(Node head){
//find the node with minimum value of item and return
it
Node min=head;
for(Node
cur=head;cur!=null;cur=cur.next){
if(min.item>cur.item){
min=cur;
}
}
return min;
}
//Method to find node having maximum value of
item
public static Node getMax(Node head){
//find the node with maximum value of item and return
it
Node max=head;
for(Node
cur=head;cur!=null;cur=cur.next){
if(max.item<cur.item){
max=cur;
}
}
return max;
}
//Method to delete the node
public static Node deleteNode(Node head,Node x){
//if x is null return head without deleting
if(x==null){
return head;
}
//if the first node is to be deleted then return
head.next first node will be automatically deleted
if(x==head){
return head.next;
}
//otherwise traverse get the node
to be deleted remove it from between and come out of the loop
for(Node
cur=head;cur.next!=null;cur=cur.next){
if(cur.next==x){
cur.next=cur.next.next; //cur.next
will have value of cur.next.next cur.next will not be accessable
then
break;
}
}
return head;
}
// Mehthod that takes a string and insert its
characters into a linked list
public static Node initializeList(String str){
Node head=new
Node(str.charAt(0)),cur;
int i;
for(cur=head,i=1;i<str.length();i++,cur=cur.next){
cur.next=new
Node(str.charAt(i));
}
return head;
}
//Method for printing linked list
public static void printList(Node head){
Node cur=head;
if(head==null)
System.out.print("<Empty>");
for(;cur!=null;cur=cur.next){
System.out.print("-> "+cur.item+" ");
}
}
}
Soukaina Filali Boubrahimi CSc 2720 Data Structures: Lab 8 Due Date: Sunday 31t Mar, 201911:59pm ...
Problem 1 Given a linked list of integers, write a function getUnique that removes all duplicates elements in the linked list and returns the new linked list of unique elements (The order does not matter). Example: Input: 1-»2->3->1-2 Output: 1->2->3 public class Node f int iterm Node next; Node(int d) t item = d; next-null; ) import java.util.ArrayList; public class ExtraLab public static void main (String[] args)t PROBLEM 1 System.out.println("PROBLEM 1"); Node head new Node(1); head.next-new Node (2); head.next.next-new Node(3);...
BELOW IS THE CODE I ALREADY HAVE Linked List - Delete Modify Lab 5 and include the method to delete a node from the Linked List. In summary: 1) Add the method Delete 2) Method call to delete, with a number that IS in the list 3) Method call to delete, with a number that is NOT in the list - Be sure to include comments - Use meaningful identifier names (constants where appropriate) import java.io.*; 1/ Java program to...
Working in C++, Complete the code. // Lab 9 code /* Insert leading comments with your name and the date. Describe the purpose of the code. Also, list each pointer and describe how it is used to enable the selection sort for the linked list structure. */ /* Insert code as described by the comments. */ /* Add comments to each line of code that uses a pointer, describing how it is being used. */ #include <iostream> using namespace std;...
Modify listlink.java program (non generic) by adding the following methods: public void insertsorted(x); // Inert x in a sorted list. public void deletex(x); //Search for x in the sorted list, if found, delete it from the sorted list. Assume you have a data file p2.txt with the following contents: 8 4 15 23 12 36 5 36 42 3 5 14 4 and your java program is in xxxxx.java file, where xxxxx is the first 5 characters of your last...
Writing a method retainAll for Circular Doubly-Linked List: I am working on an assignment creating a Circular Doubly Linked List and am having serious trouble creating a method retainAll. Here's the code, and my attempt. Initialization: public class CDoublyLinkedList { private class Node { private Object data; //Assume data implemented Comparable private Node next, prev; private Node(Object data, Node pref, Node next) { this.data = data; ...
CSCI-2467 Lab 11 – Refactor LinkedList Application to use Generics Background The code consists of three files that implement and use a simple linked list. The code was written in early Java-style using the Object class in order to allow the linked list to be a list of objects of any type. While the code works, it is not type-safe. Refactor the code to use Java Generics. You will need to change the Main class to create a linked list...
C++ Create a class that implements a sorted, doubly-linked list: Start with a copy of the sortedList class. Call your new class doublyLinkedList. Convert the baseline code into a doubly linkedlist, and thoroughly test all existing operations (make sure to check all edge conditions), and then implement the new operations below. The class should have the following additional class methods: • A reverse method: this method will reverse the order of the doubly linked list. This method takes no parameters,...
In this assignment you are to utilize the Node data structure provided on Blackboard. In this assignmet you are to write a main program that implements two methods and a main method as their driver. So, only main and two methods with it. Note: You may not use any of the LinkedList class provided on Blackboard, you may use the methods in it as a guide (you should actually look at them) but you cannot use any of the methods...
In Python 3 Write a LinkedList class that has recursive implementations of the display, remove, contains, insert, and normal_list methods. You may use default arguments and/or helper functions. The file must be named: LinkedList.py Here is what I have for my code so far. The methods I need the recursive implementations for will be bolded: class Node: """ Represents a node in a linked list (parent class) """ def __init__(self, data): self.data = data self.next = None class LinkedList: """...
Data Structures - Singly Linked Lists You will add a method swapNodes to SinglyLinkedList class (below). This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapNodes method. You may need to traverse the list. package linkedlists; public class SinglyLinkedList<E> implements Cloneable { // ---------------- nested Node class...