Please not copy and paste and try to run both of the codes after programming. Th
ID: 3747192 • Letter: P
Question
Please not copy and paste and try to run both of the codes after programming. The code only need 4 of the methods. Thank you.
/* DList1.java */
/**
* A DList1 is a mutable doubly-linked list. (No sentinel, not
* circularly linked.)
*/
public class DList1 {
/**
* head references the first node.
* tail references the last node.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
protected DListNode1 head;
protected DListNode1 tail;
protected long size;
/* DList1 invariants:
* 1) head.prev == null.
* 2) tail.next == null.
* 3) For any DListNode1 x in a DList, if x.next == y and x.next != null,
* then y.prev == x.
* 4) For any DListNode1 x in a DList, if x.prev == y and x.prev != null,
* then y.next == x.
* 5) The tail can be accessed from the head by a sequence of "next"
* references.
* 6) size is the number of DListNode1s that can be accessed from the
* head by a sequence of "next" references.
*/
/**
* DList1() constructor for an empty DList1.
*/
public DList1() {
head = null;
tail = null;
size = 0;
}
/**
* DList1() constructor for a one-node DList1.
*/
public DList1(int a) {
head = new DListNode1();
tail = head;
head.item = a;
size = 1;
}
/**
* DList1() constructor for a two-node DList1.
*/
public DList1(int a, int b) {
head = new DListNode1();
head.item = a;
tail = new DListNode1();
tail.item = b;
head.next = tail;
tail.prev = head;
size = 2;
}
/**
* insertFront() inserts an item at the front of a DList1.
*/
public void insertFront(int i) {
// Your solution here.
}
/**
* removeFront() removes the first item (and node) from a DList1. If the
* list is empty, do nothing.
*/
public void removeFront() {
// Your solution here.
}
/**
* toString() returns a String representation of this DList.
*
* DO NOT CHANGE THIS METHOD.
*
* @return a String representation of this DList.
*/
public String toString() {
String result = "[ ";
DListNode1 current = head;
while (current != null) {
result = result + current.item + " ";
current = current.next;
}
return result + "]";
}
public static void main(String[] args) {
// DO NOT CHANGE THE FOLLOWING CODE.
DList1 l = new DList1();
System.out.println("### TESTING insertFront ### Empty list is " + l);
l.insertFront(9);
System.out.println(" Inserting 9 at front. List with 9 is " + l);
if (l.head == null) {
System.out.println("head is null.");
} else {
if (l.head.item != 9) {
System.out.println("head.item is wrong.");
}
if (l.head.prev != null) {
System.out.println("head.prev is wrong.");
}
}
if (l.tail == null) {
System.out.println("tail is null.");
} else {
if (l.tail.item != 9) {
System.out.println("tail.item is wrong.");
}
if (l.tail.next != null) {
System.out.println("tail.next is wrong.");
}
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.insertFront(8);
System.out.println(" Inserting 8 at front. List with 8 and 9 is " + l);
if (l.head == null) {
System.out.println("head is null.");
} else {
if (l.head.item != 8) {
System.out.println("head.item is wrong.");
}
if (l.head.prev != null) {
System.out.println("head.prev is wrong.");
}
if (l.head.next != l.tail) {
System.out.println("head.next is wrong.");
}
}
if (l.tail == null) {
System.out.println("tail is null.");
} else {
if (l.tail.item != 9) {
System.out.println("tail.item is wrong.");
}
if (l.tail.next != null) {
System.out.println("tail.next is wrong.");
}
if (l.tail.prev != l.head) {
System.out.println("tail.prev is wrong.");
}
}
if (l.size != 2) {
System.out.println("size is wrong.");
}
l = new DList1(1, 2);
System.out.println(" ### TESTING removeFront ### List with 1 and 2 is "
+ l);
l.removeFront();
System.out.println(" Removing front node. List with 2 is " + l);
if (l.head.item != 2) {
System.out.println("head.item is wrong.");
}
if (l.head.prev != null) {
System.out.println("head.prev is wrong.");
}
if (l.tail.item != 2) {
System.out.println("tail.item is wrong.");
}
if (l.tail.next != null) {
System.out.println("tail.next is wrong.");
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Removing front node. Empty list is " + l);
if (l.head != null) {
System.out.println("head is wrong.");
}
if (l.tail != null) {
System.out.println("tail is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Removing front node. Empty list is " + l);
if (l.head != null) {
System.out.println("head is wrong.");
}
if (l.tail != null) {
System.out.println("tail is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
}
}
/* DList2.java */
/**
* A DList2 is a mutable doubly-linked list. Its implementation is
* circularly-linked and employs a sentinel (dummy) node at the head
* of the list.
*/
public class DList2 {
/**
* head references the sentinel node.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
protected DListNode2 head;
protected long size;
/* DList2 invariants:
* 1) head != null.
* 2) For any DListNode2 x in a DList2, x.next != null.
* 3) For any DListNode2 x in a DList2, x.prev != null.
* 4) For any DListNode2 x in a DList2, if x.next == y, then y.prev == x.
* 5) For any DListNode2 x in a DList2, if x.prev == y, then y.next == x.
* 6) size is the number of DListNode2s, NOT COUNTING the sentinel
* (denoted by "head"), that can be accessed from the sentinel by
* a sequence of "next" references.
*/
/**
* DList2() constructor for an empty DList2.
*/
public DList2() {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = head;
head.prev = head;
size = 0;
}
/**
* DList2() constructor for a one-node DList2.
*/
public DList2(int a) {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = new DListNode2();
head.next.item = a;
head.prev = head.next;
head.next.prev = head;
head.prev.next = head;
size = 1;
}
/**
* DList2() constructor for a two-node DList2.
*/
public DList2(int a, int b) {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = new DListNode2();
head.next.item = a;
head.prev = new DListNode2();
head.prev.item = b;
head.next.prev = head;
head.next.next = head.prev;
head.prev.next = head;
head.prev.prev = head.next;
size = 2;
}
/**
* insertFront() inserts an item at the front of a DList2.
*/
public void insertFront(int i) {
// Your solution here.
}
/**
* removeFront() removes the first item (and first non-sentinel node) from
* a DList2. If the list is empty, do nothing.
*/
public void removeFront() {
// Your solution here.
}
/**
* toString() returns a String representation of this DList.
*
* DO NOT CHANGE THIS METHOD.
*
* @return a String representation of this DList.
*/
public String toString() {
String result = "[ ";
DListNode2 current = head.next;
while (current != head) {
result = result + current.item + " ";
current = current.next;
}
return result + "]";
}
public static void main(String[] args) {
// DO NOT CHANGE THE FOLLOWING CODE.
DList2 l = new DList2();
System.out.println("### TESTING insertFront ### Empty list is " + l);
l.insertFront(9);
System.out.println(" Inserting 9 at front. List with 9 is " + l);
if (l.head.next.item != 9) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 9) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.insertFront(8);
System.out.println(" Inserting 8 at front. List with 8 and 9 is " + l);
if (l.head.next.item != 8) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 9) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.head.next.next != l.head.prev) {
System.out.println("l.head.next.next != l.head.prev.");
}
if (l.head.prev.prev != l.head.next) {
System.out.println("l.head.prev.prev != l.head.next.");
}
if (l.size != 2) {
System.out.println("size is wrong.");
}
l = new DList2(1, 2);
System.out.println(" ### TESTING removeFront ### List with 1 and 2 is "
+ l);
l.removeFront();
System.out.println(" List with 2 is " + l);
if (l.head.next.item != 2) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 2) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Empty list is " + l);
if (l.head.next != l.head) {
System.out.println("head.next is wrong.");
}
if (l.head.prev != l.head) {
System.out.println("head.prev is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Empty list is " + l);
if (l.head.next != l.head) {
System.out.println("head.next is wrong.");
}
if (l.head.prev != l.head) {
System.out.println("head.prev is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
}
}
two different types of doubly-linked list. The DListl class does not use a sentinel, whereas the DLst2 class does. The DL1stI class is not circularly linked, but the DLst2 class is (through the sentinel). Compile DListl.java and DList2.java (using "javac -g DListl.java DList2.java".) Your task is to implement two insertFront ) and two removeFront ) methods--one of each for each list class. insertFront() and removeFront () insert or remove an item at the beginning of a list. Make sure your implementations work for empty lists, one-node lists, and larger lists. The main() methods of DList1 and DList2 nclude test code, which you can run with "java DListl" and "java DList2". Part I insertFront in DList1 Write a method called DList1.insertFront () that inserts an int at the front of "this" DList1. Part II removeFront in DListl Write a method called DList1.removeFront node) from "this" DListl that removes the first item (and Part III: insertFront in DLst2 Write a method called DList2.insertFront that inserts an int at the front of "this" DList2. Your code should NOT use any "if" statements or conditionals. Part IV: removeFront in DList2 Write a method called DList2.removeFront that removes the first item (and non-sentinel node) from "this" DList2. Your code should not require separate branches for the one-node case and the more-than-one-node case. (You will need one "if", to handle the zero-node case.) Check-off Run the DListl and DList2 test code. DListl.insertFront () DList 1 . remove Front ( ) . DList2.insertFront () .Explanation / Answer
Completed the implementations of DList1 and DList2 as needed, now passing all the tests. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
/* DList1.java */
/**
* A DList1 is a mutable doubly-linked list. (No sentinel, not circularly
* linked.)
*/
public class DList1 {
/**
* head references the first node. tail references the last node.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
protected DListNode1 head;
protected DListNode1 tail;
protected long size;
/*
* DList1 invariants: 1) head.prev == null. 2) tail.next == null. 3) For any
* DListNode1 x in a DList, if x.next == y and x.next != null, then y.prev
* == x. 4) For any DListNode1 x in a DList, if x.prev == y and x.prev !=
* null, then y.next == x. 5) The tail can be accessed from the head by a
* sequence of "next" references. 6) size is the number of DListNode1s that
* can be accessed from the head by a sequence of "next" references.
*/
/**
* DList1() constructor for an empty DList1.
*/
public DList1() {
head = null;
tail = null;
size = 0;
}
/**
* DList1() constructor for a one-node DList1.
*/
public DList1(int a) {
head = new DListNode1();
tail = head;
head.item = a;
size = 1;
}
/**
* DList1() constructor for a two-node DList1.
*/
public DList1(int a, int b) {
head = new DListNode1();
head.item = a;
tail = new DListNode1();
tail.item = b;
head.next = tail;
tail.prev = head;
size = 2;
}
/**
* insertFront() inserts an item at the front of a DList1.
*/
public void insertFront(int i) {
// creating a DlistNode1 object using i
DListNode1 node = new DListNode1(i);
if (head == null) {
// adding as first node
head = node;
tail = head;
} else {
// making head node as the next of new node
node.next = head;
// making new node as prev of current head node
head.prev = node;
// making new node as the new head node
head = node;
}
size++; // incrementing size
}
/**
* removeFront() removes the first item (and node) from a DList1. If the
* list is empty, do nothing.
*/
public void removeFront() {
if (head != null) {
//pointing head to next node
head = head.next;
//updating current head's prev to null
if (head != null) {
head.prev = null;
} else {
//list is now empty
tail = null;
}
size--; //decrementing size
}
}
/**
* toString() returns a String representation of this DList.
*
* DO NOT CHANGE THIS METHOD.
*
* @return a String representation of this DList.
*/
public String toString() {
String result = "[ ";
DListNode1 current = head;
while (current != null) {
result = result + current.item + " ";
current = current.next;
}
return result + "]";
}
public static void main(String[] args) {
// DO NOT CHANGE THE FOLLOWING CODE.
DList1 l = new DList1();
System.out.println("### TESTING insertFront ### Empty list is " + l);
l.insertFront(9);
System.out.println(" Inserting 9 at front. List with 9 is " + l);
if (l.head == null) {
System.out.println("head is null.");
} else {
if (l.head.item != 9) {
System.out.println("head.item is wrong.");
}
if (l.head.prev != null) {
System.out.println("head.prev is wrong.");
}
}
if (l.tail == null) {
System.out.println("tail is null.");
} else {
if (l.tail.item != 9) {
System.out.println("tail.item is wrong.");
}
if (l.tail.next != null) {
System.out.println("tail.next is wrong.");
}
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.insertFront(8);
System.out
.println(" Inserting 8 at front. List with 8 and 9 is " + l);
if (l.head == null) {
System.out.println("head is null.");
} else {
if (l.head.item != 8) {
System.out.println("head.item is wrong.");
}
if (l.head.prev != null) {
System.out.println("head.prev is wrong.");
}
if (l.head.next != l.tail) {
System.out.println("head.next is wrong.");
}
}
if (l.tail == null) {
System.out.println("tail is null.");
} else {
if (l.tail.item != 9) {
System.out.println("tail.item is wrong.");
}
if (l.tail.next != null) {
System.out.println("tail.next is wrong.");
}
if (l.tail.prev != l.head) {
System.out.println("tail.prev is wrong.");
}
}
if (l.size != 2) {
System.out.println("size is wrong.");
}
l = new DList1(1, 2);
System.out
.println(" ### TESTING removeFront ### List with 1 and 2 is "
+ l);
l.removeFront();
System.out.println(" Removing front node. List with 2 is " + l);
if (l.head.item != 2) {
System.out.println("head.item is wrong.");
}
if (l.head.prev != null) {
System.out.println("head.prev is wrong.");
}
if (l.tail.item != 2) {
System.out.println("tail.item is wrong.");
}
if (l.tail.next != null) {
System.out.println("tail.next is wrong.");
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Removing front node. Empty list is " + l);
if (l.head != null) {
System.out.println("head is wrong.");
}
if (l.tail != null) {
System.out.println("tail is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Removing front node. Empty list is " + l);
if (l.head != null) {
System.out.println("head is wrong.");
}
if (l.tail != null) {
System.out.println("tail is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
}
}
/* DList2.java */
/**
* A DList2 is a mutable doubly-linked list. Its implementation is
* circularly-linked and employs a sentinel (dummy) node at the head of the
* list.
*/
public class DList2 {
/**
* head references the sentinel node.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
protected DListNode2 head;
protected long size;
/*
* DList2 invariants: 1) head != null. 2) For any DListNode2 x in a DList2,
* x.next != null. 3) For any DListNode2 x in a DList2, x.prev != null. 4)
* For any DListNode2 x in a DList2, if x.next == y, then y.prev == x. 5)
* For any DListNode2 x in a DList2, if x.prev == y, then y.next == x. 6)
* size is the number of DListNode2s, NOT COUNTING the sentinel (denoted by
* "head"), that can be accessed from the sentinel by a sequence of "next"
* references.
*/
/**
* DList2() constructor for an empty DList2.
*/
public DList2() {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = head;
head.prev = head;
size = 0;
}
/**
* DList2() constructor for a one-node DList2.
*/
public DList2(int a) {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = new DListNode2();
head.next.item = a;
head.prev = head.next;
head.next.prev = head;
head.prev.next = head;
size = 1;
}
/**
* DList2() constructor for a two-node DList2.
*/
public DList2(int a, int b) {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = new DListNode2();
head.next.item = a;
head.prev = new DListNode2();
head.prev.item = b;
head.next.prev = head;
head.next.next = head.prev;
head.prev.next = head;
head.prev.prev = head.next;
size = 2;
}
/**
* insertFront() inserts an item at the front of a DList2.
*/
public void insertFront(int i) {
// creating a new node
DListNode2 node = new DListNode2(i);
if (head.next == null) {
// adding as the first node
head.next = node;
node.next = head;
node.prev = head;
} else {
// adding between head and current first node
node.next = head.next;
head.next.prev = node;
head.next = node;
node.prev = head;
}
size++; // incrementing size
}
/**
* removeFront() removes the first item (and first non-sentinel node) from a
* DList2. If the list is empty, do nothing.
*/
public void removeFront() {
// checking if list is not empty
if (size > 0) {
// pointing first node to next of first node
head.next = head.next.next;
// adjusting the previous of current first node
head.next.prev = head;
size--; // decrementing size
}
}
/**
* toString() returns a String representation of this DList.
*
* DO NOT CHANGE THIS METHOD.
*
* @return a String representation of this DList.
*/
public String toString() {
String result = "[ ";
DListNode2 current = head.next;
while (current != head) {
result = result + current.item + " ";
current = current.next;
}
return result + "]";
}
public static void main(String[] args) {
// DO NOT CHANGE THE FOLLOWING CODE.
DList2 l = new DList2();
System.out.println("### TESTING insertFront ### Empty list is " + l);
l.insertFront(9);
System.out.println(" Inserting 9 at front. List with 9 is " + l);
if (l.head.next.item != 9) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 9) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.insertFront(8);
System.out
.println(" Inserting 8 at front. List with 8 and 9 is " + l);
if (l.head.next.item != 8) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 9) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.head.next.next != l.head.prev) {
System.out.println("l.head.next.next != l.head.prev.");
}
if (l.head.prev.prev != l.head.next) {
System.out.println("l.head.prev.prev != l.head.next.");
}
if (l.size != 2) {
System.out.println("size is wrong.");
}
l = new DList2(1, 2);
System.out
.println(" ### TESTING removeFront ### List with 1 and 2 is "
+ l);
l.removeFront();
System.out.println(" List with 2 is " + l);
if (l.head.next.item != 2) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 2) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Empty list is " + l);
if (l.head.next != l.head) {
System.out.println("head.next is wrong.");
}
if (l.head.prev != l.head) {
System.out.println("head.prev is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Empty list is " + l);
if (l.head.next != l.head) {
System.out.println("head.next is wrong.");
}
if (l.head.prev != l.head) {
System.out.println("head.prev is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
}
}
/*OUTPUT (DList1)*/
### TESTING insertFront ###
Empty list is [ ]
Inserting 9 at front.
List with 9 is [ 9 ]
Inserting 8 at front.
List with 8 and 9 is [ 8 9 ]
### TESTING removeFront ###
List with 1 and 2 is [ 1 2 ]
Removing front node.
List with 2 is [ 2 ]
Removing front node.
Empty list is [ ]
Removing front node.
Empty list is [ ]
/*OUTPUT (DList2)*/
### TESTING insertFront ###
Empty list is [ ]
Inserting 9 at front.
List with 9 is [ 9 ]
Inserting 8 at front.
List with 8 and 9 is [ 8 9 ]
### TESTING removeFront ###
List with 1 and 2 is [ 1 2 ]
List with 2 is [ 2 ]
Empty list is [ ]
Empty list is [ ]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.