PLEASE HELP The Lab Java Files: List.java specifies the interface for a list usi

Question

PLEASE HELP

The Lab

Java Files:

List.java specifies the interface for a list using Generics and includes the printBackwards method.

DoublyLinkedListTest.java is a set of tests that test your implementation of the DoublyLinkedList.

DoublyLinkedList.java is a partially completed implementation of the List interface using doubly-

linked lists.

When you examine DoublyLinkedList.java, you will notice several methods that are not complete (with a comment //TODO), so they only compile, but are lacking a proper implementation. You will implement all methods, and test them using functions that you will add to DoublyLinkedListTest.java main function.

Step 1. Print an empty list.

Implement the print method in the DoublyLinkedList class. You should start from the head, and traverse by the next references.

Within the main DoublyLinkedListTest.java, finish the function called testPrintEmptyListForward that:

creates a DoublyLinkedList object

calls print on the empty DoublyLinkedList.

Run your main method and make sure it does not crash. Step 2. Print an empty list backwards.

Implement the printBackwards method in the DoublyLinkedList class. You should start from the tail and traverse by the previous references.

Within the main DoublyLinkedListTest.java, finish the function called testPrintEmptyListForward that:

creates a DoublyLinkedList object

calls printBackwards on the empty DoublyLinkedList.

Run your main method and make sure it does not crash. Step 3. Get from the doubly-linked list

The get method has an integer parameter that is the position in the list. position start from 0 for the first element. You should return the T data (not the Node) at that position. If the position does not exist, you should return null.

Begin by handling the cases where you should return null.
After you are sure the position is valid, write a loop that only traverse as far as the position parameter. Again,

you should return the T data (not the Node) at that position.

Within the main DoublyLinkedListTest.java, write a function called testEmptyGet that works en empty list. Of course, it should return null no matter what position you pass as an argument, since the list is empty.

Step 4a. Prepend to the doubly-linked list: drawing and pseudocode

Draw on paper what it will look like to add a new generic object to the beginning of a doubly-linked list. You should draw three examples:

What happens when you prepend to an empty doubly-linked list?

What happens when you prepend to a doubly-linked list with one item in it?

What happens when you prepend to a doubly-linked list with three items in it?

For each example:

Draw the original doubly-linked list, including (a) the head of the doubly-linked list, (b) the tail of the doubly-linked list, (c) the number of elements, (d) every node in the doubly-linked list, each with the data, next and previous.

Draw the new Node that needs to be created for the new generic object under your original doubly- linked list. Be sure to draw the data, next and previous fields in the Node.

Draw the new arrows necessary for the new doubly-linked list after appending the new Node. Number each of these arrows. Each new arrow will require an assignment in your Java code.

Double-check that the instance variables (the head, tail and the number of elements) are set correctly. If they aren't, you'll need to modify them.

Step 4b. Prepend to the doubly-linked list: Java code.

Implement the addFirst method in the DoublyLinkedList class. The addFirst method adds a new generic object to the start of the doubly linked list.

If you implement addFirst correctly, you should be able to get the output of
testPrependAndGet correct by uncommenting it in the main function. If passed, uncommenttestPrependForwards and testPrependBackwards one at a time, to see if you get the list printed in the right order. If not, (or if you get NullPointerException), it is likely that you have corrupted your previous

references.

Step 5a. Append to the doubly-linked list: drawing and pseudocode.

Draw on paper what it will look like to append a new generic object to a doubly-linked list. You should draw three examples:

What happens when you append to an empty doubly-linked list?

What happens when you append to a doubly-linked list with one item in it?

What happens when you append to a doubly-linked list with three items in it?

Step 5b. Append to the doubly-linked list: Java code.

Now implement the addLast method. Be sure your code will handle all three situations that you drew in the previous example.
Same way as in 5, uncomment testAddLastAndGet(), testAddLastForwards(), testAddLastBackwards()one at a time, and verify you get the right output.

Step 6. Implement getLength and isEmpty.

Write the getLength() and isEmpty() methods. Since these don't modify the doubly-linked list, they should be very similar to the same methods in the linked list seen in class. Uncomment testIsEmpty() and testGetLength() to verify your code.

Step 7a. Remove from the doubly-linked list: drawing.

First draw on paper what it will look like to remove an object in a doubly-linked list. You will need to search

the entire doubly-linked list for the item you want to version of that item. You should draw five examples least one example):

Assuming you have a doubly-linked list with item in the doubly-linked list?

Assuming you have a doubly-linked list with middle item in the doubly-linked list?

Assuming you have a doubly-linked list with item in the doubly-linked list?

Assuming you have a doubly-linked list with item?

Assuming you have a doubly-linked list with from the doubly-linked list?

Go through the same four-step process as in Step 4a.

remove. If the item is found, you should remove the first (again, have each person in your group should draw at

three items in it, what happens when you remove the first three items in it, what happens when you remove the three items in it, what happens when you remove the last three items in it, what happens if you do not find the

one item in it, what happens when you remove that item

Step 7b. Remove from the doubly-linked list: Java code.

Now implement the remove method. Be sure your code will handle all four situations that you drew in the previous example.

Then you can run the following tests:

§ testRemoveFromEmptyList();
§ testRemoveFromListWithOneElementNegative();
§ testRemoveFromListWithOneElementPositive();
§ testRemoveFromListWithTwoElementNegative();
§ testRemoveFromListWithTwoElementPositive();
§ testRemoveFromListWithThreeElementNegative(); § testRemoveFromListWithThreeElementPositive();

and see if they pass the tests properly.

Step8: Iterator for DoublyLinkList

Add an iterator class definition for the DoublyLinkList. Follow the example of the slides. Then finish the testIterator method that create a list, obtain an iterator, and then uses it to print the content of the list.

----------------------------------------------------------------------------------------------------------------------------

HERE's files that given:

--------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------

Explanation / Answer

Given below is the code for the question.
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
Please do rate the answer if it was helpful. Thank you

DoublyLinkedList.java
---------------------

import java.util.Iterator;

public class DoublyLinkedList<T> implements List<T>, Iterable<T> {
private Node head, tail;
private int numberOfElements;

public DoublyLinkedList() {
head = null;
tail = null;
numberOfElements = 0;
}

@Override
public void addLast(T item) {
Node n = new Node(item);
if(head == null)
head = tail = n;
else
{
n.previous = tail;
tail.next = n;
tail = n;
}
numberOfElements++;
}

@Override
public void addFirst(T item) {
Node n = new Node(item, head, null);

if(head == null)
head = tail = n;
else
head.previous = n;

head = n;
numberOfElements++;
}

@Override
public T get(int position) {
if(position < 0 || position >= numberOfElements)
return null;
Node curr = head;
for(int i = 0; i < position; i++)
curr = curr.next;
return curr.data;
}

@Override
public void print() {
System.out.print("[");

if(numberOfElements > 0)
{
Node curr = head;
System.out.print(curr.data);
curr = curr.next;
while(curr != null)
{
System.out.print(", " + curr.data);
curr = curr.next;
}
}
System.out.print("]");
System.out.println();
}

@Override
public void printBackwards() {
System.out.print("[");

if(numberOfElements > 0)
{
Node curr = tail;
System.out.print(curr.data);
curr = curr.previous;
while(curr != null)
{
System.out.print(", " + curr.data);
curr = curr.previous;
}
}
System.out.print("]");
System.out.println();
}

@Override
public boolean remove(T item) {
Node curr = head;
while(curr != null)
{
if(curr.data.equals(item))
break;
curr = curr.next;
}

if(curr == null)
return false;

if(curr == head)
{
head = curr.next;

if(head != null) //set the new head's prevous to null
head.previous = null;
else //now the list is empty
tail = null;
}
else
{
Node prev = curr.previous;
prev.next = curr.next;
if(curr != tail)
curr.next.previous = prev;
else
tail = prev;
}
numberOfElements--;
return true;
}

@Override
public boolean isEmpty() {
return head == null;
}

@Override
public int getLength() {
return numberOfElements;

}

/**
* Inner class representing a node in the linked list
*/

private class Node
{
private T data;
private Node next, previous;

private Node(T data) {
this(data,null,null);
}

private Node (T data, Node next, Node prev) {
this.data = data;
this.next = next;
this.previous = prev;
}
}

public class DLLIterator implements Iterator<T>
{
Node curr;
public DLLIterator() {
curr = head;
}
@Override
public boolean hasNext() {
return curr != null;
}

@Override
public T next() {
T val = curr.data;
curr = curr.next;
return val;
}
}
@Override
public Iterator<T> iterator() {
return new DLLIterator();
}

}

DoublyLinkedListTest.java
--------------------------
import java.util.Iterator;

public class DoublyLinkedListTest {

public static void main(String[] args) {

// Comment only the test functions you want to run

testPrintEmptyListForward();
testPrintEmptyListBackward();
testEmptyGet();
testAddFirstAndGet();
testAddFirstForwards();
testAddFirstBackwards();
testAddLastAndGet();
testAddLastForwards();
testAddLastBackwards();
testIsEmpty();
testGetLength();
testRemoveFromEmptyList();
testRemoveFromListWithOneElementNegative();
testRemoveFromListWithOneElementPositive();
testRemoveFromListWithTwoElementNegative();
testRemoveFromListWithTwoElementPositive();
testRemoveFromListWithThreeElementNegative();
testRemoveFromListWithThreeElementPositive();
testIterator();

}

public static void testPrintEmptyListForward() {
List list = new DoublyLinkedList();
System.out.print("Printing empty list forward: ");
list.print();
}
public static void testPrintEmptyListBackward() {
List list = new DoublyLinkedList();
System.out.print("Printing empty list backward: ");
list.printBackwards();
}

public static void testEmptyGet() {
List list = new DoublyLinkedList();
System.out.println("The fifth element data in an empty list is " + list.get(5));
}
public static void testAddFirstAndGet () {
List list = new DoublyLinkedList();

// now add several items to the List
list.addFirst("Apple");
list.addFirst("Banana");
list.addFirst("Cherry");
list.addFirst("Donut");
list.addFirst("Donut");
list.addFirst("End");

System.out.println("The sixth element should be Apple, and it is: " + list.get(5));
System.out.println("The fifth element should be Banana, and it is: " + list.get(4));
System.out.println("The fourth element should be Cherry, and it is: " + list.get(3));
System.out.println("The second element should be Donut, and it is: " + list.get(1));
System.out.println("The first element should be End, and it is: " + list.get(0));

}

public static void testAddFirstForwards() {
System.out.println("");
System.out.println("-------------- testAppendForwards ------------:");
List list = new DoublyLinkedList();

// now add several items to the List
list.addFirst("Apple");
list.addFirst("Banana");
list.addFirst("Cherry");
list.addFirst("Donut");
list.addFirst("Donut");
list.addFirst("End");

System.out.println("You should get the list elements in this order: End, Donut, Donut, Cherry, Banana, Apple");
list.print();
System.out.println("--------- End of testAppendForwards -----------:");
}

public static void testAddFirstBackwards() {
System.out.println("");
System.out.println("-------------- testAppendBackwards ------------:");
List list = new DoublyLinkedList();

// now add several items to the List
list.addFirst("Apple");
list.addFirst("Banana");
list.addFirst("Cherry");
list.addFirst("Donut");
list.addFirst("Donut");
list.addFirst("End");

System.out.println("You should get the list elements in this order: Apple, Banana, Cherry, Donut, Donut, End");
list.printBackwards();
System.out.println("--------- End of testAppendBackwards -----------:");
}

public static void testIsEmpty() {
System.out.println("");
System.out.println("-------------- testIsEmpty ------------:");
List list = new DoublyLinkedList();
System.out.println("isEmpty() should return true, and it is returning " + list.isEmpty());
list.addFirst("One");
System.out.println("isEmpty() should return false, and it is returning " + list.isEmpty());
System.out.println("--------- End of testIsEmpty -----------:");
}

public static void testGetLength() {
System.out.println("");
System.out.println("-------------- testGetLength ------------:");
List list = new DoublyLinkedList();
System.out.println("getLength() should return 0, and it is returning " + list.getLength());

// now add several items to the List
list.addFirst("Apple");
System.out.println("getLength() should return 1, and it is returning " + list.getLength());

list.addLast("Banana");
System.out.println("getLength() should return 2, and it is returning " + list.getLength());

list.addFirst("Cherry");
System.out.println("getLength() should return 3, and it is returning " + list.getLength());
System.out.println("--------- End of testGetLength -----------:");

}

public static void testRemoveFromEmptyList() {

System.out.println("");
System.out.println("-------------- testRemoveFromEmptyList ------------:");
List list = new DoublyLinkedList();
System.out.println("Nothing to remove from an empty list, to remove() should return false, and it returns " +list.remove("something"));
System.out.println("-------------- testRemoveFromEmptyList ------------:");
}
public static void testRemoveFromListWithOneElementNegative() {

System.out.println("");
System.out.println("-------------- testRemoveFromListWithOneElementNegative ------------:");
List list = new DoublyLinkedList();
list.addFirst("Apple");
System.out.println("remove() should return false, and it returns " +list.remove("something"));
System.out.println("-------------- testRemoveFromListWithOneElementNegative ------------:");
}
public static void testRemoveFromListWithTwoElementNegative() {

System.out.println("");
System.out.println("-------------- testRemoveFromListWithTwoElementNegative ------------:");
List list = new DoublyLinkedList();
list.addFirst("Apple");
list.addFirst("Cherry");
System.out.println("remove() should return false, and it returns " +list.remove("something"));
System.out.println("-------------- testRemoveFromListWithTwoElementNegative ------------:");
}
public static void testRemoveFromListWithTwoElementPositive() {

System.out.println("");
System.out.println("-------------- testRemoveFromListWithTwoElementPositive ------------:");
List list = new DoublyLinkedList();
list.addFirst("Apple");
list.addFirst("Cherry");
System.out.println("remove() should return true, and it returns " +list.remove("Cherry"));
System.out.println("You should get the list elements in this order: Apple");
list.print();
System.out.println("-------------- testRemoveFromListWithTwoElementPositive ------------:");
}

public static void testRemoveFromListWithOneElementPositive() {

System.out.println("");
System.out.println("-------------- testRemoveFromListWithOneElementPositive ------------:");
List list = new DoublyLinkedList();
list.addFirst("Apple");
System.out.println("remove() should return true, and it returns " +list.remove("Apple"));
System.out.println("You should get an empty list");
list.print();
System.out.println("-------------- testRemoveFromListWithOneElementPositive ------------:");
}

public static void testRemoveFromListWithThreeElementPositive() {

System.out.println("");
System.out.println("-------------- testRemoveFromListWithThreeElementPositive ------------:");
List list = new DoublyLinkedList();
list.addLast("Apple");
list.addLast("Cherry");
list.addLast("Banana");
System.out.println("remove() should return true , and it returns " +list.remove("Cherry"));
System.out.println("You should get the list elements in this order: Apple, Banana");
list.print();
System.out.println("-------------- testRemoveFromListWithThreeElementPositive ------------:");
}
public static void testRemoveFromListWithThreeElementNegative() {

System.out.println("");
System.out.println("-------------- testRemoveFromListWithThreeElementNegative ------------:");
List list = new DoublyLinkedList();
list.addLast("Apple");
list.addLast("Cherry");
list.addLast("Banana");
System.out.println("remove() should return false, and it returns " +list.remove("something"));
System.out.println("You should get the list elements in this order: Apple, Cherry, Banana");
list.print();
System.out.println("-------------- testRemoveFromListWithThreeElementNegative ------------:");
}

public static void testAddLastAndGet () {
List list = new DoublyLinkedList();

// now add several items to the List
list.addLast("Apple");
list.addLast("Banana");
list.addLast("Cherry");
list.addLast("Donut");
list.addLast("Donut");
list.addLast("End");

System.out.println("The sixth element should be End, and it is: " + list.get(5));
System.out.println("The fifth element should be Donut, and it is: " + list.get(4));
System.out.println("The fourth element should be Donut, and it is: " + list.get(3));
System.out.println("The second element should be Banana, and it is: " + list.get(1));
System.out.println("The first element should be Apple, and it is: " + list.get(0));

}

public static void testAddLastForwards() {
System.out.println("");
System.out.println("-------------- testAddLastForwards ------------:");
List list = new DoublyLinkedList();

// now add several items to the List
list.addLast("Apple");
list.addLast("Banana");
list.addLast("Cherry");
list.addLast("Donut");
list.addLast("Donut");
list.addLast("End");

System.out.println("You should get the list elements in this order: Apple, Banana, Cherry, Donut, Donut, End");
list.print();
System.out.println("--------- End of testAddLastForwards -----------:");
}

public static void testAddLastBackwards() {
System.out.println("");
System.out.println("-------------- testAddLastBackwards ------------:");
List list = new DoublyLinkedList();

// now add several items to the List
list.addLast("Apple");
list.addLast("Banana");
list.addLast("Cherry");
list.addLast("Donut");
list.addLast("Donut");
list.addLast("End");

System.out.println("You should get the list elements in this order: End, Donut, Donut, Cherry, Banana, Apple");
list.printBackwards();
System.out.println("--------- End of testAddLastBackwards -----------:");
}

public static void testIterator() {

System.out.println("");
System.out.println("-------------- testIterator ------------:");
List list = new DoublyLinkedList();
list.addLast("Apple");
list.addLast("Cherry");
list.addLast("Banana");

//TODO  
// ADD code to obtain iterator object, then uses it to iterate through the list and print its data.
Iterator<String> iter = ((DoublyLinkedList<String>) list).iterator();
while(iter.hasNext())
System.out.println(iter.next());
System.out.println("-------------- testIterator ------------:");
}

}

output
-------
Printing empty list forward: []
Printing empty list backward: []
The fifth element data in an empty list is null
The sixth element should be Apple, and it is: Apple
The fifth element should be Banana, and it is: Banana
The fourth element should be Cherry, and it is: Cherry
The second element should be Donut, and it is: Donut
The first element should be End, and it is: End

-------------- testAppendForwards ------------:
You should get the list elements in this order: End, Donut, Donut, Cherry, Banana, Apple
[End, Donut, Donut, Cherry, Banana, Apple]
--------- End of testAppendForwards -----------:

-------------- testAppendBackwards ------------:
You should get the list elements in this order: Apple, Banana, Cherry, Donut, Donut, End
[Apple, Banana, Cherry, Donut, Donut, End]
--------- End of testAppendBackwards -----------:
The sixth element should be End, and it is: End
The fifth element should be Donut, and it is: Donut
The fourth element should be Donut, and it is: Donut
The second element should be Banana, and it is: Banana
The first element should be Apple, and it is: Apple

-------------- testAddLastForwards ------------:
You should get the list elements in this order: Apple, Banana, Cherry, Donut, Donut, End
[Apple, Banana, Cherry, Donut, Donut, End]
--------- End of testAddLastForwards -----------:

-------------- testAddLastBackwards ------------:
You should get the list elements in this order: End, Donut, Donut, Cherry, Banana, Apple
[End, Donut, Donut, Cherry, Banana, Apple]
--------- End of testAddLastBackwards -----------:

-------------- testIsEmpty ------------:
isEmpty() should return true, and it is returning true
isEmpty() should return false, and it is returning false
--------- End of testIsEmpty -----------:

-------------- testGetLength ------------:
getLength() should return 0, and it is returning 0
getLength() should return 1, and it is returning 1
getLength() should return 2, and it is returning 2
getLength() should return 3, and it is returning 3
--------- End of testGetLength -----------:

-------------- testRemoveFromEmptyList ------------:
Nothing to remove from an empty list, to remove() should return false, and it returns false
-------------- testRemoveFromEmptyList ------------:

-------------- testRemoveFromListWithOneElementNegative ------------:
remove() should return false, and it returns false
-------------- testRemoveFromListWithOneElementNegative ------------:

-------------- testRemoveFromListWithOneElementPositive ------------:
remove() should return true, and it returns true
You should get an empty list
[]
-------------- testRemoveFromListWithOneElementPositive ------------:

-------------- testRemoveFromListWithTwoElementNegative ------------:
remove() should return false, and it returns false
-------------- testRemoveFromListWithTwoElementNegative ------------:

-------------- testRemoveFromListWithTwoElementPositive ------------:
remove() should return true, and it returns true
You should get the list elements in this order: Apple
[Apple]
-------------- testRemoveFromListWithTwoElementPositive ------------:

-------------- testRemoveFromListWithThreeElementNegative ------------:
remove() should return false, and it returns false
You should get the list elements in this order: Apple, Cherry, Banana
[Apple, Cherry, Banana]
-------------- testRemoveFromListWithThreeElementNegative ------------:

-------------- testRemoveFromListWithThreeElementPositive ------------:
remove() should return true , and it returns true
You should get the list elements in this order: Apple, Banana
[Apple, Banana]
-------------- testRemoveFromListWithThreeElementPositive ------------:

-------------- testIterator ------------:
Apple
Cherry
Banana
-------------- testIterator ------------:

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.