Please take a look at the code I\'ve written for the concat method. I am trying
ID: 3837362 • Letter: P
Question
Please take a look at the code I've written for the concat method. I am trying to figure out why it won't pass the final test. I receive these error notes:
concat: Broken prev link.
concat: Expected 10 prev nodes, but got more.
Expected "[ ]", got "[ 34 33 32 31 30 40 41 42 43 44 ]"
public class MyDeque {
Node first = null;
Node last = null;
int N = 0;
static class Node {
public Node() { }
public double item;
public Node next;
public Node prev;
}
public MyDeque () { };
public boolean isEmpty () { return N == 0; }
public int size () { return N; }
/* The concat method should take the Nodes from "that" and add them to "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;
* therefore it should not call pushLeft or pushRight.
*/
public void concat (MyDeque that) {
// TODO
if (this.isEmpty()) {
this.first = that.first;
this.last = that.last;
}
else if (that.isEmpty()) {
that.first = null;
that.last = null;
that.N = 0;
}
else {
if (!that.isEmpty()) {
this.last.next = that.first;
that.first.prev = this.last;
this.last = that.last;
}
} N = N + that.N;
}
//Tests given for the concat method
d1 = new MyDeque ();
d1.concat (new MyDeque ());
check ("concat", d1, "[ ]");
d1.pushLeft (11);
d1.concat (new MyDeque ());
check ("concat", d1, "[ 11 ]");
d1 = new MyDeque ();
d2 = new MyDeque ();
d2.pushLeft (11);
d1.concat (d2);
check ("concat", d1, "[ 11 ]");
d1 = new MyDeque ();
for (int i = 10; i < 15; i++) { d1.pushLeft (i); checkInvariants ("left", d1); }
for (int i = 20; i < 25; i++) { d1.pushRight (i); checkInvariants ("right", d1); }
check ("concat", d1, "[ 14 13 12 11 10 20 21 22 23 24 ]");
d2 = new MyDeque ();
d1.concat (d2);
check ("concat", d1, "[ 14 13 12 11 10 20 21 22 23 24 ]");
check ("concat", d2, "[ ]");
for (int i = 30; i < 35; i++) { d2.pushLeft (i); checkInvariants ("left", d2); }
for (int i = 40; i < 45; i++) { d2.pushRight (i); checkInvariants ("right", d2); }
check ("concat", d2, "[ 34 33 32 31 30 40 41 42 43 44 ]");
d3 = new MyDeque ();
d2.concat (d3);
check ("concat", d2, "[ 34 33 32 31 30 40 41 42 43 44 ]");
check ("concat", d3, "[ ]");
d1.concat (d2);
check ("concat", d1, "[ 14 13 12 11 10 20 21 22 23 24 34 33 32 31 30 40 41 42 43 44 ]");
check ("concat", d2, "[ ]");
for (int i = 0; i < 20; i++) { d1.popLeft (); checkInvariants ("left", d1); }
Explanation / Answer
Please find my implementation.
Please let me know in case of any issue.
public void concat1 (MyDeque that) {
// TODO
if (this.isEmpty()) {
this.first = that.first;
this.last = that.last;
}
else if (that.isEmpty()) {
that.first = null;
that.last = null;
that.N = 0;
}
else {
this.last.next = that.first;
that.first.prev = this.last;
this.last = that.last;
N = N + that.N;
}
}