Iterators and Linked List removal Specifically, you must take the existing code
ID: 3587779 • Letter: I
Question
Iterators and Linked List removal
Specifically, you must take the existing code for Linked Lists, and make it implement the iterator method of the java.lang.Iterable<E> interface. In implementing your iterator, you may make use of the code in LinkedListIterator. However, that code does not provide an implementation for the remove method, so you must provide that implementation.
You must also add to the Linked List class the two remove methods specified by the List interface, and implement them correctly. You also need to provide a size method, as specified by the List interface.
You are welcome to adapt the remove code from the book.
Finally, you must provide a driver program (in a separate class) that gives the user the possibility to exercise each of the methods of both the LinkedList and the iterator classes. This could be similar to your address book class in assignment 4. Your driver program should create a linked list of strings, and allow operations on that linked list.
Specifically, the user must be able to:
add a string at the end of the list: boolean add(E value)
add a string at an arbitrary position in the list: void add(int index, E value)
remove a string at an arbitrary position in the list: E remove(int index)
remove a given string from the list: boolean remove(Object o)
create an iterator
call hasNext, next, and remove on the iterator, showing the results of each call
Your driver program should correctly handle any exceptions thrown by any of these methods, print an appropriate message, and continue operation.
Sample interaction
If using prompts and commands, your program could behave as follows. The parts your program prints are in this font, the user input is in this font.
Starting program, list is empty.
enter one of: add, remove, iterator, quit. add
enter string to add. Hello World
enter position for string (-1 to add at end). 99
The list is empty.
enter one of: add, remove, iterator, quit. add
enter string to add. Foo
enter position for string (-1 to add at end). -1
The list has one element.
enter one of: add, remove, iterator, quit. iterator
enter one of: hasNext, next, remove, quit. hasNext
enter one of: hasNext, next, remove, quit. next
enter one of: hasNext, next, remove, quit. remove
enter one of: hasNext, next, remove, quit. remove
enter one of: hasNext, next, remove, quit. hasNext
enter one of: hasNext, next, remove, quit. quit
The list is empty.
enter one of: add, remove, iterator, quit. remove
enter one of: position, object. object
enter string to remove. Foo
The list is empty.
enter one of: add, remove, iterator, quit. quit
=============================================
public class LinkedList<E> {
private static class LinkedNode<T> {
private T item;
private LinkedNode<T> next;
/**
* constructor to build a node with no successor
* @param the value to be stored by this node
*/
private LinkedNode(T value) {
item = value;
next = null;
}
/**
* constructor to build a node with specified (maybe null) successor
* @param the value to be stored by this node
* @param the next field for this node
*/
private LinkedNode(T value, LinkedNode<T> reference) {
item = value;
next = reference;
}
}
// end of the LinkedNode definition
// this is the start of the linked list. If the list is empty, it is null
protected LinkedNode<E> head;
// this is the end of the linked list. If the list is empty, it is null
protected LinkedNode<E> tail;
protected int size;
// there are some relationships between the class variables. This
// method checks that these relationships always hold. Any
// property that always holds is called an invariant.
// the property may not hold in the middle of a method,
// so only call this at the beginning or end of a public method.
/**
* checks assertion
* @throws java.lang.AssertionError if the assertion is not true
*/
private void verify(boolean mustBeTrue) {
if (! mustBeTrue) {
throw new java.lang.AssertionError("assertion error");
}
}
/**
* checks class invariants
* @throws java.lang.AssertionError if the invariant is violated
*/
private void checkInvariants() {
// uncomment the next line to skip the checks:
// return;
// either head and tail are both null, or neither is null.
// size is zero if and only if they are null, and otherwise is positive
verify((head == null) == (tail == null));
verify((size == 0) == (head == null));
verify(size >= 0);
// if the list only has one element, head should be the same as tail
// (and also if the list has no elements), otherwise they should differ
verify((head == tail) == (size <= 1));
// a non-null tail variable should always have a null "next" field
verify((tail == null) || (tail.next == null));
// check to make sure size is the same as the length of the list.
// this code takes O(n), so comment it out if performance is important
int measuredSize = 0;
LinkedNode<E> node = head;
// if visitedLast is null, the list is empty, and tail should also be null
LinkedNode<E> visitedLast = null;
while (node != null) {
visitedLast = node;
node = node.next;
measuredSize++;
}
verify(measuredSize == size);
// also make sure "last" really is the last node in the linked list
verify(visitedLast == tail);
}
/**
* initializes an empty linked list
*/
public LinkedList() {
head = null;
tail = null;
size = 0;
// one of the constructor's jobs is to make sure that the invariants hold.
checkInvariants();
}
// these private (helper) methods simplify implementation of
// the public "add" methods
// the helper methods never modify "size", the public methods
// take care of that, so the invariants probably do not hold at the end of
// a helper methods
/**
* adds at the head of the list
* @param the value to be added
*/
private void addAtFront(E value) {
head = new LinkedNode<E>(value, head);
if (tail == null) {
tail = head;
}
}
/**
* adds at the tail of the list. Assumes (and checks) that tail is not null
* @param the value to be added
* @throws RuntimeException
*/
private void addAtEnd(E value) {
if (tail == null) {
throw new RuntimeException ("invalid call to addAtEnd, tail is null");
}
LinkedNode<E> newNode = new LinkedNode<E>(value);
tail.next = newNode;
tail = newNode;
}
/**
* adds a value to the list after the given node
* @param the node after which the new value is added
* @param the value to be added
*/
private void addAfter(LinkedNode<E> reference, E value) {
LinkedNode<E> newNode = new LinkedNode<E>(value, reference.next);
reference.next = newNode;
if (reference == tail) { // if added at end, update tail value
tail = newNode;
}
}
/**
* adds a value to the end of the list
* @param the value to be added
* @return true (the add always succeeds)
*/
public boolean add(E value) {
checkInvariants(); // useful for debugging
if (head != null) {
addAtEnd (value);
} else {
addAtFront (value);
}
size++;
checkInvariants(); // invariants valid at start, are they still valid?
// i.e., did this method break the invariants?
return true;
}
/**
* returns the node at the requested position, may take time O(n)
* @param the position of the requested node, 0 for the head node
* @return the requested node
* @throws NullPointerException if the index is larger than the linked list
*/
private LinkedNode<E> nodeAtPosition(int index) {
verify (index >= 0);
LinkedNode<E> result = head;
while (index > 0) {
result = result.next;
index--;
}
verify (result != null);
return result;
}
/**
* adds a value to the list, in the given position
* @param the position at which to add: 0 to add at the start
* @param the value to be added
* @throws IndexOutOfBoundsException if the index is less than 0
* or greater than the number of elements in the linked list
*/
public void add(int index, E value) {
checkInvariants();
if ((index < 0) || (index > size)) {
String badIndex =
new String ("index " + index + " must be between 0 and " + size);
throw new IndexOutOfBoundsException(badIndex);
}
if (index == 0) {
addAtFront (value);
} else {
addAfter (nodeAtPosition (index - 1), value);
}
size++;
checkInvariants();
}
/**
* concatenates the elements of the linked list, separated by " ==> "
* @return the string representation of the list
*/
public String toString() {
checkInvariants();
LinkedNode<E> node = head;
StringBuffer result = new StringBuffer();
while (node != null) {
result.append (node.item.toString());
node = node.next;
if (node != null) {
result.append (" ==> ");
}
}
checkInvariants(); // make sure we didn't break anything
return result.toString();
}
/**
* unit test method -- basic testing of the functionality
* @param required, ignored
*/
public static void main (String [] arguments) {
LinkedList<String> ll = new LinkedList<String>();
System.out.println (ll);
ll.add ("foo");
System.out.println (ll);
ll.add (1, "bar");
System.out.println (ll);
ll.add ("baz");
System.out.println (ll);
ll.add (0, "hello");
System.out.println (ll);
ll.add (1, "world");
System.out.println (ll);
}
private class LinkedListIterator implements java.util.Iterator<E> {
private LinkedNode<E> current;
private LinkedListIterator() {
current = head; // head is declared in the enclosing class
}
public boolean hasNext() {
return (current != null);
}
public E next() {
if (hasNext()) {
E result = current.item;
current = current.next; // may be null
return result;
} // no next element
throw new java.util.NoSuchElementException("linked list.next");
}
public void remove() {
throw new UnsupportedOperationException
("Linked list iterator remove not supported");
}
}
}
Explanation / Answer
import java.util.lang;
public class LinkedList<E> {
private static class LinkedNode<T> {
private T item;
private LinkedNode<T> next;
/**
* constructor to build a node with no successor
* @param the value to be stored by this node
*/
private LinkedNode(T value) {
item = value;
next = null;
}
/**
* constructor to build a node with specified (maybe null) successor
* @param the value to be stored by this node
* @param the next field for this node
*/
private LinkedNode(T value, LinkedNode<T> reference) {
item = value;
next = reference;
}
}
// end of the LinkedNode definition
// this is the start of the linked list. If the list is empty, it is null
protected LinkedNode<E> head;
// this is the end of the linked list. If the list is empty, it is null
protected LinkedNode<E> tail;
protected int size;
// there are some relationships between the class variables. This
// method checks that these relationships always hold. Any
// property that always holds is called an invariant.
// the property may not hold in the middle of a method,
// so only call this at the beginning or end of a public method.
/**
* checks assertion
* @throws java.lang.AssertionError if the assertion is not true
*/
private void verify(boolean mustBeTrue) {
if (! mustBeTrue) {
throw new java.lang.AssertionError("assertion error");
}
}
/**
* checks class invariants
* @throws java.lang.AssertionError if the invariant is violated
*/
private void checkInvariants() {
// uncomment the next line to skip the checks:
// return;
// either head and tail are both null, or neither is null.
// size is zero if and only if they are null, and otherwise is positive
verify((head == null) == (tail == null));
verify((size == 0) == (head == null));
verify(size >= 0);
// if the list only has one element, head should be the same as tail
// (and also if the list has no elements), otherwise they should differ
verify((head == tail) == (size <= 1));
// a non-null tail variable should always have a null "next" field
verify((tail == null) || (tail.next == null));
// check to make sure size is the same as the length of the list.
// this code takes O(n), so comment it out if performance is important
int measuredSize = 0;
LinkedNode<E> node = head;
// if visitedLast is null, the list is empty, and tail should also be null
LinkedNode<E> visitedLast = null;
while (node != null) {
visitedLast = node;
node = node.next;
measuredSize++;
}
verify(measuredSize == size);
// also make sure "last" really is the last node in the linked list
verify(visitedLast == tail);
}
/**
* initializes an empty linked list
*/
public LinkedList() {
head = null;
tail = null;
size = 0;
// one of the constructor's jobs is to make sure that the invariants hold.
checkInvariants();
}
// these private (helper) methods simplify implementation of
// the public "add" methods
// the helper methods never modify "size", the public methods
// take care of that, so the invariants probably do not hold at the end of
// a helper methods
/**
* adds at the head of the list
* @param the value to be added
*/
private void addAtFront(E value) {
head = new LinkedNode<E>(value, head);
if (tail == null) {
tail = head;
}
size++;
}
/**
* adds at the tail of the list. Assumes (and checks) that tail is not null
* @param the value to be added
* @throws RuntimeException
*/
private void addAtEnd(E value) {
if (tail == null) {
throw new RuntimeException ("invalid call to addAtEnd, tail is null");
}
LinkedNode<E> newNode = new LinkedNode<E>(value);
tail.next = newNode;
tail = newNode;
size++;
}
/**
* adds a value to the list after the given node
* @param the node after which the new value is added
* @param the value to be added
*/
private void addAfter(LinkedNode<E> reference, E value) {
LinkedNode<E> newNode = new LinkedNode<E>(value, reference.next);
reference.next = newNode;
if (reference == tail) { // if added at end, update tail value
tail = newNode;
size++;
}
}
/**
* adds a value to the end of the list
* @param the value to be added
* @return true (the add always succeeds)
*/
public boolean add(E value) {
checkInvariants(); // useful for debugging
if (head != null) {
addAtEnd (value);
} else {
addAtFront (value);
}
size++;
checkInvariants(); // invariants valid at start, are they still valid?
// i.e., did this method break the invariants?
return true;
}
/**
* returns the node at the requested position, may take time O(n)
* @param the position of the requested node, 0 for the head node
* @return the requested node
* @throws NullPointerException if the index is larger than the linked list
*/
private LinkedNode<E> nodeAtPosition(int index) {
verify (index >= 0);
LinkedNode<E> result = head;
while (index > 0) {
result = result.next;
index--;
}
verify (result != null);
return result;
}
/**
* adds a value to the list, in the given position
* @param the position at which to add: 0 to add at the start
* @param the value to be added
* @throws IndexOutOfBoundsException if the index is less than 0
* or greater than the number of elements in the linked list
*/
public void add(int index, E value) {
checkInvariants();
if ((index < 0) || (index > size)) {
String badIndex =
new String ("index " + index + " must be between 0 and " + size);
throw new IndexOutOfBoundsException(badIndex);
}
if (index == 0) {
addAtFront (value);
} else {
addAfter (nodeAtPosition (index - 1), value);
}
size++;
checkInvariants();
}
/**
* concatenates the elements of the linked list, separated by " ==> "
* @return the string representation of the list
*/
public String toString() {
checkInvariants();
LinkedNode<E> node = head;
StringBuffer result = new StringBuffer();
while (node != null) {
result.append (node.item.toString());
node = node.next;
if (node != null) {
result.append (" ==> ");
}
}
checkInvariants(); // make sure we didn't break anything
return result.toString();
}
public boolean remove(int index){
verify (index >= 0);
if(index == 0){
if(head.next == null){
head = null;
tail = null;
}
else{
head = head.next;
head = null;
}
size--;
}
else{
LinkedNode<E> result = head;
while (index > 1) {
result = result.next;
index--;
}
LinkedNode<E> cur = result.next;
result.next = cur.next;
size--;
verify (result != null);
}
}
public boolean remove(E value){
current = head;
if(current == null)
throw new RuntimeException("List is empty");
else{
LinkedNode<E> prev = null;
while(current != null || current.item != value)
{
prev = current;
current = current.next;
}
if(current != null)
{
prev.next = current.next;
size--;
}
}
}
public int size(){
return size;
}
/**
* unit test method -- basic testing of the functionality
* @param required, ignored
*/
public static void main (String [] arguments) {
LinkedList<String> ll = new LinkedList<String>();
System.out.println (ll);
ll.add ("foo");
System.out.println (ll);
ll.add (1, "bar");
System.out.println (ll);
ll.add ("baz");
System.out.println (ll);
ll.add (0, "hello");
System.out.println (ll);
ll.add (1, "world");
System.out.println (ll);
}
private class LinkedListIterator implements java.util.Iterator<E> {
private LinkedNode<E> current;
private LinkedListIterator() {
current = head; // head is declared in the enclosing class
}
public boolean hasNext() {
return (current != null);
}
public E next() {
if (hasNext()) {
E result = current.item;
current = current.next; // may be null
return result;
} // no next element
throw new java.util.NoSuchElementException("linked list.next");
}
public void remove() {
if(current == null)
throw new RuntimeException("List is empty");
else{
LinkedNode<E> prev = null;
while(current != null)
{
prev = current;
current = current.next;
}
prev.next = current.next;
size--;
}
}
}
}
--------------------------------------------------------------------------------------------------------------------------------------------
Hey, I have added the methods as mentioned in the questions. Also for creating size function, I have used the size data member in the class. As such I have updated the value of size in all the respective methods. The names of the new methods I have written are self explanatory. Please comment them as you see fit. Also call them from main function according to your need.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.