Need to do Concat public Node next; public Node prev; } //...
Need to do Concat
public Node next;
public Node prev;
}
// constructor
public DSIDequeue() {
left = right = null;
N = 0;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void addLeft(double item) {
Node n = new Node(item, null,
null);
if (isEmpty()) {
left = n;
right = n;
N = 1;
}
else {
left.prev =
n;
n.next =
left;
left = n;
N++;
}
}
public void addRight(double item) {
Node n = new Node(item, null,
null);
if (isEmpty()) {
left = n;
right = n;
N = 1;
}
else {
right.next =
n;
n.prev =
right;
right = n;
N++;
}
}
public double removeLeft() {
if (N == 0) {
throw new
NoSuchElementException("The dequeue is empty");
}
double item = left.item;
left = left.next;
if (left == null) {
right =
null;
}
else {
left.prev =
null;
}
N--;
return item;
}
public double removeRight() {
if (N == 0) {
throw new
NoSuchElementException();
}
double item = right.item;
right = right.prev;
if (right == null) {
left =
null;
}
else {
right.next =
null;
}
N--;
return item;
}
/**
* concat
*
* The concat method should take the Nodes from "that"
and add them to the right
* hand side of "this" After execution, "that" should
be empty. See the tests in
* the main program.
*
* Do not use a loop or a recursive definition. This
method should create no new
* Nodes; preconditions: none ( dequeue may be
empty)
*
*/
public void concat(DSIDequeue that) {
// ToDo 5: fix this
}
public static void main(String args[]) {
concatTests();
}
////////////////////////////////////////////////////////////////////
// concat tests (and more add/remove tests)
////////////////////////////////////////////////////////////////////
public static void concatTests() {
DSIDequeue d1, d2, d3;
d1 = new DSIDequeue();
d1.concat(new DSIDequeue());
check("concat 1", d1, "[ ]");
d1.addLeft(11);
d1.concat(new DSIDequeue());
check("concat 2", d1, "[ 11
]");
d1 = new DSIDequeue();
d2 = new DSIDequeue();
d2.addLeft(11);
d1.concat(d2);
check("concat 3", d1, "[ 11
]");
d1 = new DSIDequeue();
for (int i = 10; i < 15; i++)
{
d1.addLeft(i);
checkInvariants("left", d1);
}
for (int i = 20; i < 25; i++)
{
d1.addRight(i);
checkInvariants("right", d1);
}
check("concat 4", d1, "[ 14 13 12
11 10 20 21 22 23 24 ]");
d2 = new DSIDequeue();
d1.concat(d2);
check("concat 5a", d1, "[ 14 13 12
11 10 20 21 22 23 24 ]");
check("concat 5b", d2, "[ ]");
for (int i = 30; i < 35; i++)
{
d2.addLeft(i);
checkInvariants("left", d2);
}
for (int i = 40; i < 45; i++)
{
d2.addRight(i);
checkInvariants("right", d2);
}
check("concat 6", d2, "[ 34 33 32
31 30 40 41 42 43 44 ]");
d3 = new DSIDequeue();
d2.concat(d3);
check("concat 6a", d2, "[ 34 33 32
31 30 40 41 42 43 44 ]");
check("concat 6b", d3, "[ ]");
d1.concat(d2);
check("concat 7a", d1, "[ 14 13 12
11 10 20 21 22 23 24 34 33 32 31 30 40 41 42 43 44 ]");
check("concat 7b", d2, "[
]");
for (int i = 0; i < 20; i++)
{
d1.removeLeft();
checkInvariants("left", d1);
}
System.out.println("Finished concat
tests");
}
/**
* *********************************** Utility
routines
* ***************************************
*
*/
public DSIDequeue(String s) {
String[] nums = s.split(" ");
for (int i = nums.length - 1; i
>= 0; i--) {
try {
addLeft(Double.parseDouble(nums[i]));
} catch
(NumberFormatException e) {
}
}
}
@Override
public String toString() {
DecimalFormat format = new
DecimalFormat("#.###");
StringBuilder result = new
StringBuilder("[ ");
for (Node x = left; x != null; x =
x.next) {
result.append(format.format(x.item));
result.append("
");
}
result.append("]");
return result.toString();
}
static void showError(String message) {
Trace.draw();
System.out.println(message);
// throw new Error (); // stops
execution
}
public static void checkInvariants(String message,
DSIDequeue that) {
int N = that.N;
DSIDequeue.Node left =
that.left;
DSIDequeue.Node right =
that.right;
if (N < 0) {
throw new
Error();
}
if (N == 0) {
if (left != null
|| right != null) {
showError(String.format("%s: Expected left,right
== null.", message));
}
} else {
if (left == null
|| right == null) {
showError(String.format("%s: Expected left,right
!= null.", message));
}
}
if (N > 0) {
DSIDequeue.Node
prev = null;
DSIDequeue.Node
current = left;
for (int i = 0;
i < N; i++) {
if (current == null) {
showError(String.format("%s:
Expected %d next nodes, but got less.", message, N));
}
if (current.prev != prev) {
showError(String.format("%s:
Broken prev link.", message));
}
prev = current;
current = current.next;
}
if (current !=
null) {
showError(String.format("%s: Expected %d next
nodes, but got more.", message, N));
}
DSIDequeue.Node
next = null;
current =
right;
for (int i = 0;
i < N; i++) {
if (current == null) {
showError(String.format("%s:
Expected %d prev nodes, but got less.", message, N));
}
if (current.next != next) {
showError(String.format("%s:
Broken next link.", message));
}
next = current;
current = current.prev;
}
if (current !=
null) {
showError(String.format("%s: Expected %d prev
nodes, but got more.", message, N));
}
}
}
private static void check(String message,
DSIDequeue actual, String expected) {
checkInvariants(message,
actual);
if (expected != null) {
if
(!expected.equals(actual.toString())) {
showError(message + " Expected \"" + expected +
"\", got \"" + actual + "\"");
}
}
}
private static void check(String message,
DSIDequeue actual, String expected, double dActual, double
dExpected) {
if (dExpected != dActual) {
showError(message + " Expected \"" + dExpected + "\", got \"" +
dActual + "\"");
}
check(message, actual,
expected);
}
}
Homework Answers
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. Thanks
// DSIDequeue.java
import java.text.DecimalFormat;
import java.util.NoSuchElementException;
public class DSIDequeue {
// Since Node class is missing (incomplete) from your question, I have
// created and used one myself
class Node {
public double item;
public Node next;
public Node prev;
public Node(double item, Node next, Node prev) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
private Node left, right;
private int N;
// constructor
public DSIDequeue() {
left = right = null;
N = 0;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void addLeft(double item) {
Node n = new Node(item, null, null);
if (isEmpty()) {
left = n;
right = n;
N = 1;
}
else {
left.prev = n;
n.next = left;
left = n;
N++;
}
}
public void addRight(double item) {
Node n = new Node(item, null, null);
if (isEmpty()) {
left = n;
right = n;
N = 1;
}
else {
right.next = n;
n.prev = right;
right = n;
N++;
}
}
public double removeLeft() {
if (N == 0) {
throw new NoSuchElementException("The dequeue is empty");
}
double item = left.item;
left = left.next;
if (left == null) {
right = null;
} else {
left.prev = null;
}
N--;
return item;
}
public double removeRight() {
if (N == 0) {
throw new NoSuchElementException();
}
double item = right.item;
right = right.prev;
if (right == null) {
left = null;
} else {
right.next = null;
}
N--;
return item;
}
/**
* concat
*
* The concat method should take the Nodes from "that" and add them to the
* right hand side of "this" After execution, "that" should be empty. See
* the tests in the main program.
*
* Do not use a loop or a recursive definition. This method should create no
* new Nodes; preconditions: none ( dequeue may be empty)
*
*/
public void concat(DSIDequeue that) {
// proceeding only if that is not null and has at least one element
if (that != null && that.N > 0) {
// if this queue has no elements, simply assigning that's values to
// this queue
if (N == 0) {
this.left = that.left;
this.right = that.right;
N = that.N;
} else {
// otherwise setting that.left as the next node of this.right
this.right.next = that.left;
// connecting this.right as the prev of that.left
that.left.prev = this.right;
// setting that.right as the new right node of this queue
this.right = that.right;
// adding that.N to this.N
this.N += that.N;
}
// making that empty
that.left = null;
that.right = null;
that.N = 0;
}
}
public static void main(String args[]) {
concatTests();
}
// //////////////////////////////////////////////////////////////////
// concat tests (and more add/remove tests)
// //////////////////////////////////////////////////////////////////
public static void concatTests() {
DSIDequeue d1, d2, d3;
d1 = new DSIDequeue();
d1.concat(new DSIDequeue());
check("concat 1", d1, "[ ]");
d1.addLeft(11);
d1.concat(new DSIDequeue());
check("concat 2", d1, "[ 11 ]");
d1 = new DSIDequeue();
d2 = new DSIDequeue();
d2.addLeft(11);
d1.concat(d2);
check("concat 3", d1, "[ 11 ]");
d1 = new DSIDequeue();
for (int i = 10; i < 15; i++) {
d1.addLeft(i);
checkInvariants("left", d1);
}
for (int i = 20; i < 25; i++) {
d1.addRight(i);
checkInvariants("right", d1);
}
check("concat 4", d1, "[ 14 13 12 11 10 20 21 22 23 24 ]");
d2 = new DSIDequeue();
d1.concat(d2);
check("concat 5a", d1, "[ 14 13 12 11 10 20 21 22 23 24 ]");
check("concat 5b", d2, "[ ]");
for (int i = 30; i < 35; i++) {
d2.addLeft(i);
checkInvariants("left", d2);
}
for (int i = 40; i < 45; i++) {
d2.addRight(i);
checkInvariants("right", d2);
}
check("concat 6", d2, "[ 34 33 32 31 30 40 41 42 43 44 ]");
d3 = new DSIDequeue();
d2.concat(d3);
check("concat 6a", d2, "[ 34 33 32 31 30 40 41 42 43 44 ]");
check("concat 6b", d3, "[ ]");
d1.concat(d2);
check("concat 7a", d1,
"[ 14 13 12 11 10 20 21 22 23 24 34 33 32 31 30 40 41 42 43 44 ]");
check("concat 7b", d2, "[ ]");
for (int i = 0; i < 20; i++) {
d1.removeLeft();
checkInvariants("left", d1);
}
System.out.println("Finished concat tests");
}
/**
* *********************************** Utility routines
* ***************************************
*
*/
public DSIDequeue(String s) {
String[] nums = s.split(" ");
for (int i = nums.length - 1; i >= 0; i--) {
try {
addLeft(Double.parseDouble(nums[i]));
} catch (NumberFormatException e) {
}
}
}
@Override
public String toString() {
DecimalFormat format = new DecimalFormat("#.###");
StringBuilder result = new StringBuilder("[ ");
for (Node x = left; x != null; x = x.next) {
result.append(format.format(x.item));
result.append(" ");
}
result.append("]");
return result.toString();
}
static void showError(String message) {
Trace.draw();
System.out.println(message);
// throw new Error (); // stops execution
}
public static void checkInvariants(String message, DSIDequeue that) {
int N = that.N;
DSIDequeue.Node left = that.left;
DSIDequeue.Node right = that.right;
if (N < 0) {
throw new Error();
}
if (N == 0) {
if (left != null || right != null) {
showError(String.format("%s: Expected left,right == null.",
message));
}
} else {
if (left == null || right == null) {
showError(String.format("%s: Expected left,right != null.",
message));
}
}
if (N > 0) {
DSIDequeue.Node prev = null;
DSIDequeue.Node current = left;
for (int i = 0; i < N; i++) {
if (current == null) {
showError(String.format(
"%s: Expected %d next nodes, but got less.",
message, N));
}
if (current.prev != prev) {
showError(String.format("%s: Broken prev link.", message));
}
prev = current;
current = current.next;
}
if (current != null) {
showError(String
.format("%s: Expected %d next nodes, but got more.",
message, N));
}
DSIDequeue.Node next = null;
current = right;
for (int i = 0; i < N; i++) {
if (current == null) {
showError(String.format(
"%s: Expected %d prev nodes, but got less.",
message, N));
}
if (current.next != next) {
showError(String.format("%s: Broken next link.", message));
}
next = current;
current = current.prev;
}
if (current != null) {
showError(String
.format("%s: Expected %d prev nodes, but got more.",
message, N));
}
}
}
private static void check(String message, DSIDequeue actual, String expected) {
checkInvariants(message, actual);
if (expected != null) {
if (!expected.equals(actual.toString())) {
showError(message + " Expected \"" + expected + "\", got \""
+ actual + "\"");
}
}
}
private static void check(String message, DSIDequeue actual,
String expected, double dActual, double dExpected) {
if (dExpected != dActual) {
showError(message + " Expected \"" + dExpected + "\", got \""
+ dActual + "\"");
}
check(message, actual, expected);
}
}
JAVA: * You may not add any fields to the node or list classes. * You...
JAVA:
* You may not add any fields to the node or list classes.
* You may not add any methods to the node class.
* Do not change any 'Utility' methods that I have included.
* You may NOT use any arrays or other Java classes
~ Testing purposes ~
public class DSIList {
Node
first,last; // three
instance variables
int N;
//
maintain the size of the list
static class Node...
5. Given the following definition of class Node: class Node { public int item; public Node...
5. Given the following definition of class Node: class Node { public int item; public Node next; public Node ( int i, Node n ) { item = i; next = n; }; } and the following declarations: Node list, p, q; Assume the structure starts as below. Draw the structure created by executing the following statements. Each part is independent. list 1 2 3 4 5 [2] a) p = list; q = null; while ( p != null...
I need help with todo line please public class LinkedList { private Node head; public LinkedList()...
I need help with todo line please public class LinkedList { private Node head; public LinkedList() { head = null; } public boolean isEmpty() { return head == null; } public int size() { int count = 0; Node current = head; while (current != null) { count++; current = current.getNext(); } return count; } public void add(int data) { Node newNode = new Node(data); newNode.setNext(head); head = newNode; } public void append(int data) { Node newNode = new Node(data);...
Using the following implementation of Tree class Node { public int iData; // data item (key) public...
Using the following implementation of Tree class Node { public int iData; // data item (key) public double dData; // data item public Node leftChild; // this node's left child public Node rightChild; // this node's right child public void displayNode() // display ourself { System.out.print('{'); System.out.print(iData); System.out.print(", "); System.out.print(dData); System.out.print("} "); } } // end class Node //------------------------------------------------------------------ import java.io.IOException; import java.util.Stack; public class Tree { private Node root; // first node of tree // ------------------------------------------------------------- public Tree() // constructor { root = null; }...
Consider the following Java program public class Foo i static class Node Object item; Node next:...
Consider the following Java program public class Foo i static class Node Object item; Node next: Node (Object item, Node next) this. item = item; this.next next: public static void main (String] args) ( Node dat a nu ï ï ; dat a = new Node ("hello", data): data ne Node (5, data) while (data null) String s(String) data. item; System.out.println (s)
Java: Return an array of booleans in a directed graph. Please complete the TODO section in...
Java: Return an array of booleans in a directed graph. Please complete the TODO section in the mark(int s) function import algs13.Bag; import java.util.HashSet; // See instructions below public class MyDigraph { static class Node { private String key; private Bag<Node> adj; public Node (String key) { this.key = key; this.adj = new Bag<> (); } public String toString () { return key; } public void addEdgeTo (Node n) { adj.add (n); } public Bag<Node> adj () { return adj;...
Complete the implementation of the method replace: public class SinglyLinkedList private Node head, public SinglyLinkedListo this(null) public SinglyLinkedList(Node head) [ this.head -head public Nod...
Complete the implementation of the method replace: public class SinglyLinkedList private Node head, public SinglyLinkedListo this(null) public SinglyLinkedList(Node head) [ this.head -head public Node getHeado return head public void setHead(Node head) [ head: this. head Method that creates a Node containing 'item' @param item Value to be added this.headnew Node(item, this.head) * and adds it as the first element in the list *I public void add(int item) Method that finds the node at the given index d replaces its value...
1. private Node head; private Node tail; public class Node { String name; Node next; Node...
1. private Node head; private Node tail; public class Node { String name; Node next; Node prev; } public void displayInReverse(){ //write your code here to display names in reverse } 2. public class NodeOne { String name; NodeOne next; public NodeOne(String name) { this.name = name; } } // Complete the code snippet below so that the delete method works properly public void delete(String name) { NodeOne temp = head, prev = head; while (temp != null) { if...
P1 is below package p6_linkedList; import java.util.*; public class LinkedList { public Node header; public LinkedList()...
P1 is below
package p6_linkedList;
import java.util.*;
public class LinkedList
{
public Node header;
public LinkedList()
{
header = null;
}
public final Node Search(int key)
{
Node current = header;
while (current != null && current.item != key)
{
current = current.link;
}
return current;
}
public final void Append(int newItem)
{
Node newNode = new Node(newItem);
newNode.link = header;
header = newNode;
}
public final Node Remove()
{
Node x = header;
if (header != null)
{
header...
Java Double Max Function I need help with this top problem. The bottom is the assignment...
Java Double Max Function
I need help with this top problem. The bottom is the
assignment
// return Double .NEGATIVE-INFINİTY if the linked list is empty public double max return max (first); h private static double max (Node x) f e I TODO 1.3.27 return 0; 1 package algs13; 2 import stdlib.*; 4 public class MyLinked f static class Node public Node() t 1 public double item; public Node next; 10 int N; Node first; 12 13 14 public MyLinked...
JAVA:
* You may not add any fields to the node or list classes.
* You may not add any methods to the node class.
* Do not change any 'Utility' methods that I have included.
* You may NOT use any arrays or other Java classes
~ Testing purposes ~
public class DSIList {
Node
first,last; // three
instance variables
int N;
//
maintain the size of the list
static class Node...
Consider the following Java program public class Foo i static class Node Object item; Node next: Node (Object item, Node next) this. item = item; this.next next: public static void main (String] args) ( Node dat a nu ï ï ; dat a = new Node ("hello", data): data ne Node (5, data) while (data null) String s(String) data. item; System.out.println (s)
Complete the implementation of the method replace: public class SinglyLinkedList private Node head, public SinglyLinkedListo this(null) public SinglyLinkedList(Node head) [ this.head -head public Node getHeado return head public void setHead(Node head) [ head: this. head Method that creates a Node containing 'item' @param item Value to be added this.headnew Node(item, this.head) * and adds it as the first element in the list *I public void add(int item) Method that finds the node at the given index d replaces its value...
P1 is below
package p6_linkedList;
import java.util.*;
public class LinkedList
{
public Node header;
public LinkedList()
{
header = null;
}
public final Node Search(int key)
{
Node current = header;
while (current != null && current.item != key)
{
current = current.link;
}
return current;
}
public final void Append(int newItem)
{
Node newNode = new Node(newItem);
newNode.link = header;
header = newNode;
}
public final Node Remove()
{
Node x = header;
if (header != null)
{
header...
Java Double Max Function
I need help with this top problem. The bottom is the
assignment
// return Double .NEGATIVE-INFINİTY if the linked list is empty public double max return max (first); h private static double max (Node x) f e I TODO 1.3.27 return 0; 1 package algs13; 2 import stdlib.*; 4 public class MyLinked f static class Node public Node() t 1 public double item; public Node next; 10 int N; Node first; 12 13 14 public MyLinked...
Most questions answered within 3 hours.
-
Minitab Problem: Take the Lake Hume June rainfall data and find
use the processes outlined in...
asked 2 minutes ago -
X Company is trying to decide whether to continue using old
equipment to make Product A...
asked 3 minutes ago -
IN PYTHON ONLY !! Program 2: Re-work
program #5 (WeeklyHours) from the previous assignment such that...
asked 40 minutes ago -
The average length of time between arrivals at a turnpike
toll-booth is 26 seconds. What is...
asked 2 hours ago -
(a) A piston at 6.1 atm contains a gas that occupies a volume of
3.5 L....
asked 3 hours ago -
Please answer true or false. Words
cannot be changed or added in to make it true...
asked 3 hours ago -
An empty test tube weighs 15.923 grams. Then,
MgCl2•6H2O is added into the test tube. After...
asked 3 hours ago -
Assume memory access is 10 units of time and disk access is
10000 units of time....
asked 3 hours ago -
1. Are all good samples random?
2. Magazines often report surveys giving statistics such as “63%...
asked 4 hours ago -
Under all the various types of market structures, firms
must eventually earn some economic profits for...
asked 3 hours ago -
Consider the following fitness regime for a single locus trait
with two co-dominant alleles: w11 =...
asked 4 hours ago -
A large cable company reports the following.
80% of its customers subscribe to its cable TV...
asked 4 hours ago