JAVA HELP THANK YOU! Getting Started --------------- The files in the lab2 direc
ID: 3836804 • Letter: J
Question
JAVA HELP THANK YOU!
Getting Started
---------------
The files in the lab2 directory contain classes for two different types of
doubly-linked list. The DList1 class does not use a sentinel, whereas the
DList2 class does. The DList1 class is not circularly linked, but the DList2
class is (through the sentinel). Compile DList1.java and DList2.java (using
"javac -g DList1.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 include test code, which you can run
with "java DList1" and "java DList2".
Part I: insertFront in DList1 (1 point)
----------------------------------------
Write a method called DList1.insertFront() that inserts an int at the front of
"this" DList1.
Part II: removeFront in DList1 (1 point)
-----------------------------------------
Write a method called DList1.removeFront() that removes the first item (and
node) from "this" DList1.
Part III: insertFront in DList2 (1 point)
------------------------------------------
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 (2 points)
------------------------------------------
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 DList1 and DList2 test code.
1 point: DList1.insertFront().
1 point: DList1.removeFront().
1 point: DList2.insertFront().
1 point: DList2.removeFront().
===================
/* 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.");
}
}
}
=================
/* DListNode1.java */
/**
* A DListNode1 is a node in a DList1 (doubly-linked list).
*/
public class DListNode1 {
/**
* item references the item stored in the current node.
* prev references the previous node in the DList.
* next references the next node in the DList.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
public int item;
public DListNode1 prev;
public DListNode1 next;
/**
* DListNode1() constructor.
*/
DListNode1() {
item = 0;
prev = null;
next = null;
}
DListNode1(int i) {
item = i;
prev = null;
next = null;
}
}
============
/* DListNode2.java */
/**
* A DListNode2 is a node in a DList2 (doubly-linked list).
*/
public class DListNode2 {
/**
* item references the item stored in the current node.
* prev references the previous node in the DList.
* next references the next node in the DList.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
public int item;
public DListNode2 prev;
public DListNode2 next;
/**
* DListNode2() constructor.
*/
DListNode2() {
item = 0;
prev = null;
next = null;
}
DListNode2(int i) {
item = i;
prev = null;
next = null;
}
}
Explanation / Answer
//Insert the following code in the insertFront method of DList1.java class::
public void insertFront(int i)
{
if(size == 0)
{
DListNode1 temp = new DListNode1();
head = temp;
tail = temp;
head.item = i;
}
else
{
DListNode1 temp = new DListNode1();
temp.item = i;
temp.next = head;
head.prev = temp;
head = temp;
}
size = size+1;
}
--------------------------------------------------------------------------
//Insert the following code in the removeFront method of the DList1.java class::
public void removeFront()
{
if(size !=0)
{
if(size > 1)
{
head = head.next;
head.prev = null;
}
else
{
head = null;
tail = null;
}
size = size -1;
}
}
-----------------------------------------------------------------------------------------------------------------
//Insert the following code in the insertFront() method of DList2.java class::
public void insertFront(int i)
{
if(size == 0)
{
DListNode2 temp = new DListNode2();
head.next = temp;
temp.prev = head;
head.prev = temp;
temp.next = head;
temp.item = i;
size = size+1;
}
else
{
DListNode2 temp = new DListNode2();
temp.next = head.next;
head.next.prev = temp;
head.next = temp;
temp.prev = head;
temp.item = i;
size = size +1;
}
}
--------------------------------------------------------------------------------------------------------------------------------
//Insert the following code in the removeFront() method of DList2.java class::
public void removeFront()
{
if(size!=0)
{
if(size==1)
{
head.next = head;
head.prev = head;
size = size -1;
}
else
{
DListNode2 temp = head.next;
head.next = temp.next;
temp.next.prev = head;
size = size-1;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.