I need help with this Java program. There are starter codes too. Thanks Listlter
ID: 3701997 • Letter: I
Question
I need help with this Java program. There are starter codes too. Thanks
Listlteratorlnterface.java:
package list;
public interface ListIteratorInterface<E>
{
boolean hasNext();
boolean hasPrevious();
E next() throws Exception;
E previous() throws Exception;
void add(E data);
void remove() throws Exception;
void set(E data) throws Exception;
}
List.java:
package list;
public class List<E>
{
private Node first;
private Node last;
private int length;
private class Node
{
public E data;
public Node next;
public Node prev;
}
/**
* A generic inner ListIterator class that implements the
* ListIteratorInterface. It is used as a cursor to traverse the list.
*/
private class ListIterator implements ListIteratorInterface<E>
{
private Node position; // the node on the left of the iterator
private Node previousPosition; // the previous iterator position
private boolean isAfterNext;
private boolean isAfterPrevious;
/**
* Constructs an iterator at the beginning of the linked list.
*/
public ListIterator()
{
position = null;
previousPosition = null;
isAfterNext = false;
isAfterPrevious = false;
}
/**
* Returns true if there is a node on the right of the iterator;
* otherwise, returns false.
*/
public boolean hasNext()
{
if (position == null)
return first != null;
else
return position.next != null;
}
/**
* Returns true if there is a node on the left of the iterator;
* otherwise, returns false.
*/
public boolean hasPrevious()
{
// Implement this method
}
/**
* Resets the iterator's previousPosition to its current position,
* resets the iterator's current position to the node on the right
* of its current position (moves the iterator, in the forward
* direction, past the node on the right), and returns the data
* value in the node that the iterator just passed over.
* Throws an exception if the iterator is at the end of the list.
*/
public E next() throws Exception
{
if (!hasNext())
throw new Exception("Called at the end of the list");
previousPosition = position; // Remember for remove.
if (position == null)
position = first;
else
position = position.next;
isAfterNext = true;
return position.data;
}
/**
* Resets the iterator's previousPosition to its current position,
* resets the iterator's current position to the node on the left
* of its current position (moves the iterator, in the backward
* direction, past the node on the left), and returns the data
* value in the node that the iterator just passed over.
* Throws an exception if the iterator is at the beginning of the
* list.
*/
public E previous() throws Exception
{
// Implement this method
}
/**
* Inserts a new node on the left of the iterator and resets
* the iterator position to this inserted node.
*/
public void add(E data)
{
if (position == null)
{
addFirst(data);
position = first;
}
else if(position.next == null)
{
addLast(data);
position = last;
}
else
{
Node newNode = new Node();
newNode.data = data;
newNode.next = position.next;
position.next.prev = newNode;
newNode.prev = position;
position.next = newNode;
position = newNode;
length++;
}
isAfterNext = false;
isAfterPrevious = false;
}
/**
* Removes the last node passed over by the iterator in a call to
* either next or previous.
* Throws an exception if remove is not called immediately after a
* call to either next or previous.
*/
public void remove() throws Exception
{
// Implement this method
}
/**
* Replaces the data value in the node on the left of the iterator
* with the input data value.
* Throws an exception if the node on the left of the iterator is
* null.
*/
public void set(E data) throws Exception
{
if (position == null)
throw new Exception("set call on a null node");
position.data = data;
}
}
// Constructs an empty linked list.
public List()
{
first = null;
last = null;
length = 0;
}
/**
* Returns the number of elements in the linked list.
*/
public int size()
{
return length;
}
/**
* Adds a new node at the beginning of the linked list.
*/
public void addFirst(E data)
{
Node newNode = new Node();
newNode.data = data;
if(length == 0)
{
first = newNode;
last = newNode;
}
else
{
newNode.next = first;
first.prev = newNode;
first = newNode;
}
length++;
}
/**
* Adds a new node at the end of the linked list.
*/
public void addLast(E data)
{
// Implement this method
}
/**
* Removes the first node in the linked list and returns this node's
* data value.
* Throws an exception if the list is empty.
*/
public E removeFirst() throws Exception
{
if(length == 0)
throw new Exception("Non-empty list expected");
E data = first.data;
if(length == 1)
{
first = null;
last = null;
}
else
{
first = first.next;
first.prev = null;
}
length--;
return data;
}
/**
* Removes the last node in the linked list and returns this node's
* data value.
* Throws an exception if the list is empty.
*/
public E removeLast() throws Exception
{
// Implement this method
}
/**
* Returns the data value in the first node of the linked list.
* Throws an exception if the list is empty.
*/
public E getFirst() throws Exception
{
if (first == null)
throw new Exception("Non-empty list expected");
return first.data;
}
/**
* Returns an iterator for iterating through the linked list.
*/
public ListIterator listIterator()
{
return new ListIterator();
}
/**
* @return a string representation of the elements of the linked list
* in the format [e0, e1, ..., en-2, en-1], where each ei is a data
* value in the list and e0 is the data value in the first node
* and en-1 is the data value in the last node. It returns [] if this
* list is empty.
*/
public String toString()
{
String string = "[";
if(length > 0)
{
Node node = first;
string += node.data;
while(node != last)
{
node = node.next;
string += ", " + node.data;
}
}
string += "]";
return string;
}
}
ListDemo.java:
package list;
public class ListDemo
{
public static void main(String[] args)
{
try
{
List<String> list = new List();
list.addLast("Juliet");
System.out.println("Juliet added to list");
list.addLast("Bob");
System.out.println("Bob added to list");
list.addFirst("Tom");
System.out.println("Tom added to list");
list.addFirst("Mary");
System.out.println("Mary added to list");
System.out.println("list = " + list);
System.out.println(list.removeFirst() + " removed from list");
System.out.println(list.removeLast() + " removed from list");
System.out.println("list = " + list);
// | in the comments indicates the iterator position
ListIteratorInterface<String> iterator = list.listIterator(); // |TJ
System.out.println("Iterator is at beginning of list");
iterator.add("Diana"); // D|TJ
System.out.println("Diana added to list");
System.out.println("list = " + list);
System.out.println("Iterator passed " + iterator.next()); // DT|J
System.out.println("Iterator passed " + iterator.next()); // DTJ|
iterator.add("Harry"); // DTJH|
System.out.println("Harry added to list");
System.out.println("list = " + list);
iterator = list.listIterator(); // |DTJH
System.out.println("Iterator moved to beginning of list");
System.out.println("Iterator passed " + iterator.next()); // D|TJH
System.out.println("Iterator passed " + iterator.next()); // DT|JH
// Add more nodes after second node
iterator.add("Nina"); // DTN|JH
System.out.println("Nina added to list");
iterator.add("Romeo"); //DTNR|JH
System.out.println("Romeo added to list");
System.out.println("list = " + list);
String name = iterator.next();
System.out.println("Iterator passed " + name); // DTNRJ|H
// Remove last traversed element
iterator.remove(); // DTNR|H
System.out.println(name + " removed from list");
System.out.println("list = " + list);
System.out.println("Iterator passed " + iterator.previous());//DTN|RH
System.out.println("Iterator passed " + iterator.previous());//DT|NRH
name = iterator.previous();
System.out.println("Iterator passed " + name); // D|TNRH
// Remove last traversed element
iterator.remove(); // D|NRH
System.out.println(name + " removed from list");
System.out.println("list = " + list);
iterator = list.listIterator(); // |DNRH
System.out.println("Iterator moved to beginning of list");
System.out.println();
// Print all elements backward and forward
System.out.println("Forward version of list:");
while (iterator.hasNext())
System.out.println(iterator.next());
System.out.println();
System.out.println("Backward version of list:");
while (iterator.hasPrevious())
System.out.println(iterator.previous());
System.out.println();
System.out.println("Iterator is at beginning of list"); // |DNRH
System.out.println("Iterator passed " + iterator.next()); // D|NRH
iterator.add("Sara"); // DS|NRH
System.out.println("Sara added to list");
System.out.println("list = " + list);
System.out.println("Try to remove Sara from list: ");
iterator.remove();
}
catch(Exception e)
{
System.out.println(e);
}
}
}
Explanation / Answer
package com.chegg.ds;
public class List<E>
{
private Node first;
private Node last;
private int length;
private class Node
{
public E data;
public Node next;
public Node prev;
}
/**
* A generic inner ListIterator class that implements the
* ListIteratorInterface. It is used as a cursor to traverse the list.
*/
private class ListIterator implements ListIteratorInterface<E>
{
private Node position; // the node on the left of the iterator
private Node previousPosition; // the previous iterator position
private boolean isAfterNext;
private boolean isAfterPrevious;
/**
* Constructs an iterator at the beginning of the linked list.
*/
public ListIterator()
{
position = null;
previousPosition = null;
isAfterNext = false;
isAfterPrevious = false;
}
/**
* Returns true if there is a node on the right of the iterator;
* otherwise, returns false.
*/
public boolean hasNext()
{
if (position == null)
return first != null;
else
return position.next != null;
}
/**
* Returns true if there is a node on the left of the iterator;
* otherwise, returns false.
*/
public boolean hasPrevious()
{
// Implement this method
if (previousPosition == null)
return first != null;
else
return previousPosition.next != null;
}
/**
* Resets the iterator's previousPosition to its current position,
* resets the iterator's current position to the node on the right
* of its current position (moves the iterator, in the forward
* direction, past the node on the right), and returns the data
* value in the node that the iterator just passed over.
* Throws an exception if the iterator is at the end of the list.
*/
public E next() throws Exception
{
if (!hasNext())
throw new Exception("Called at the end of the list");
previousPosition = position; // Remember for remove.
if (position == null)
position = first;
else
position = position.next;
isAfterNext = true;
return position.data;
}
/**
* Resets the iterator's previousPosition to its current position,
* resets the iterator's current position to the node on the left
* of its current position (moves the iterator, in the backward
* direction, past the node on the left), and returns the data
* value in the node that the iterator just passed over.
* Throws an exception if the iterator is at the beginning of the
* list.
*/
public E previous() throws Exception
{
// Implement this method
if (!hasPrevious())
throw new Exception("Called at the begining of the list");
previousPosition = position; // Remember for remove.
if (previousPosition == null)
previousPosition = last;
else
position = position.prev;
isAfterPrevious = true;
return position.data;
}
/**
* Inserts a new node on the left of the iterator and resets
* the iterator position to this inserted node.
*/
public void add(E data)
{
if (position == null)
{
addFirst(data);
position = first;
}
else if(position.next == null)
{
addLast(data);
position = last;
}
else
{
Node newNode = new Node();
newNode.data = data;
newNode.next = position.next;
position.next.prev = newNode;
newNode.prev = position;
position.next = newNode;
position = newNode;
length++;
}
isAfterNext = false;
isAfterPrevious = false;
}
/**
* Removes the last node passed over by the iterator in a call to
* either next or previous.
* Throws an exception if remove is not called immediately after a
* call to either next or previous.
*/
public void remove() throws Exception
{
// Implement this method
}
/**
* Replaces the data value in the node on the left of the iterator
* with the input data value.
* Throws an exception if the node on the left of the iterator is
* null.
*/
public void set(E data) throws Exception
{
if (position == null)
throw new Exception("set call on a null node");
position.data = data;
}
}
// Constructs an empty linked list.
public List()
{
first = null;
last = null;
length = 0;
}
/**
* Returns the number of elements in the linked list.
*/
public int size()
{
return length;
}
/**
* Adds a new node at the beginning of the linked list.
*/
public void addFirst(E data)
{
Node newNode = new Node();
newNode.data = data;
if(length == 0)
{
first = newNode;
last = newNode;
}
else
{
newNode.next = first;
first.prev = newNode;
first = newNode;
}
length++;
}
/**
* Adds a new node at the end of the linked list.
*/
public void addLast(E data)
{
// Implement this method
Node newNode = new Node();
newNode.data = data;
if(first==null && last==null) {
first = newNode;
first.next = last;
length++;
}else {
if(last!=null) {
last.next = newNode;
newNode.prev = last;
last = newNode;
length++;
}else {
last = newNode;
last.prev = first;
first.next = last;
}
}
}
/**
* Removes the first node in the linked list and returns this node's
* data value.
* Throws an exception if the list is empty.
*/
public E removeFirst() throws Exception
{
if(length == 0)
throw new Exception("Non-empty list expected");
E data = first.data;
if(length == 1)
{
first = null;
last = null;
}
else
{
first = first.next;
first.prev = null;
}
length--;
return data;
}
/**
* Removes the last node in the linked list and returns this node's
* data value.
* Throws an exception if the list is empty.
*/
public E removeLast() throws Exception
{
// Implement this method
if(last==null)
return null;
Node toRemove = last;
last = last.prev;
length--;
return toRemove.data;
}
/**
* Returns the data value in the first node of the linked list.
* Throws an exception if the list is empty.
*/
public E getFirst() throws Exception
{
if (first == null)
throw new Exception("Non-empty list expected");
return first.data;
}
/**
* Returns an iterator for iterating through the linked list.
*/
public ListIterator listIterator()
{
return new ListIterator();
}
/**
* @return a string representation of the elements of the linked list
* in the format [e0, e1, ..., en-2, en-1], where each ei is a data
* value in the list and e0 is the data value in the first node
* and en-1 is the data value in the last node. It returns [] if this
* list is empty.
*/
public String toString()
{
String string = "[";
if(length > 0)
{
Node node = first;
string += node.data;
while(node != last)
{
node = node.next;
string += ", " + node.data;
}
}
string += "]";
return string;
}
}
===================================================
Juliet added to list
Bob added to list
Tom added to list
Mary added to list
list = [Mary, Tom, Juliet, Bob]
Mary removed from list
Bob removed from list
list = [Tom, Juliet]
Iterator is at beginning of list
Diana added to list
list = [Diana, Tom, Juliet]
Iterator passed Tom
Iterator passed Juliet
Harry added to list
list = [Diana, Tom, Juliet]
Iterator moved to beginning of list
Iterator passed Diana
Iterator passed Tom
Nina added to list
Romeo added to list
list = [Diana, Tom, Nina, Romeo, Juliet]
Iterator passed Juliet
Juliet removed from list
list = [Diana, Tom, Nina, Romeo, Juliet]
Iterator passed Romeo
Iterator passed Nina
Iterator passed Tom
Tom removed from list
list = [Diana, Tom, Nina, Romeo, Juliet]
Iterator moved to beginning of list
Forward version of list:
Diana
Tom
Nina
Romeo
Juliet
Harry
Bob
Backward version of list:
Harry
Iterator is at beginning of list
Iterator passed Bob
Sara added to list
list = [Diana, Tom, Nina, Romeo, Juliet, Sara]
Try to remove Sara from list: