Here is the Question:

Covers: Implementing singly-linked lists

Based on Exercise 24.2 (Implement MyLinkedList):

(Professor said we are "just filling in methods that the book didn't provide")

Download from Blackboard the following files:

MyList.java

MyAbstractList.java

MyLinkedList.java

TestMyLinkedListForHW.java

In MyLinkedList.java complete the implementations of the following methods --

In the MyLinkedList class:

boolean contains(E e) E get(int index) int indexOf(E e) int lastIndexOf(E e) E set(int index, E e)

In the MyLinkedListIterator class:

void remove()

The methods contains, indexOf, and lastIndexOf should compare elements to e by using the _equals method. You will need to handle null values as a special case. For instance, the call e.equals() will throw a NullPointerException if _e is null. You do not want that exception thrown, so use == to compare null values.

set should throw an IndexOutOfBoundsException if index < 0 or index >= size(). When set does not throw an exception, it should return the element that was previously at the given index.

The _remove method from the iterator class is the trickiest one to implement. The following comments come from the description of the _remove method in the Java documentation:

/**

* Removes from the underlying collection the last element returned

* by this iterator. This method can be called

* only once per call to next. The behavior of an iterator

* is unspecified if the underlying collection is modified while the * iteration is in progress in any way other than by calling this

* method.

* throws IllegalStateException if the next method has not

* yet been called, or if the remove method has already * been called after the last call to the next method.

*/ void remove();

Some suggestions on how to implement the _remove() method are provided at the end of this writeup. Successfully implementing the _remove() method will almost certainly involve adding some code to the _next() method.

Testing your solution:

Use TestMyLinkedListForHW.java to test your solution. Here is the output that should obtain:

Test 1 successful

Test 2 successful

Test 3 successful

Test 4 successful

Test 5 successful

Test 6 successful

Test 7 successful

Test 8 successful

Test 9 successful

Test 10 successful

Test 11 successful

Test 12 successful

Test 13 successful

Test 14 successful

Test 15 successful

Test 16 successful

Test 17 successful

Test 18 successful

Test 19 successful

Test 20 successful

Test 21 successful

Test 22 successful

Test 23 successful

Test 24 successful

Test 25 successful

Test 26 successful

Test 27 successful

Tests completed

Of course, you are welcome to run additional tests on your solution.

What to turn in:

Submit your modified MyLinkedList.java file on Blackboard. Include your name at the top of file.

Suggestions for implementing the remove() method:

As described in the Java documentation, the _remove() method in your iterator class should throw an _{IllegalStateException} under certain circumstances. This is fairly easy to accomplish:

Review the _{ArrayListIterator} code that we will cover in class, which is in MyArrayList.java on Blackboard. Note that the ArrayListIterator code in the textbook never throws an IllegalStateException, so don't bother reviewing it for enlightenment on this issue. The key is the Boolean data field _canRemove.

A significant challenge is making the remove() method in your iterator class appropriately efficient: It should not need to search for the correct node to remove. Indeed, it should run in O(1) time (i.e. constant time). If the iterator code calls the _remove(int) or _remove(E) method from the outer class then removal will require O(n) time, which is too slow. Lets think about it:

Suppose the list consists of the strings "A", "B", "C", "D", "E". Suppose that you ask the list for an iterator object and that you call _next() on the iterator three times. The last value returned by the iterator will be "C", and _current will point to the node containing "D". Suppose now that you call _remove() on the iterator. The element that should be removed is "C", meaning that the next pointer in the node containing "B" is the one that needs to be updated! How do we reach that node quickly? Our linked list is only singly-linked and all of the links go in the forward direction! My suggestion is that, in addition to _{LinkedListIterator} having a data field of type _Node called _current and the _boolean data field _canRemove, the iterator should have two more data fields:

Node prev; // Refers to the node previous to current,

// if any. Otherwise null.

Node previousToLastReturned; // Refers to the node previous to the

// one containing the last element returned by next(), // if there is such a node and canRemove is true. // Otherwise null.

In the example scenario above, _prev should point to the node containing "C" and previousToLastReturned should point to the node containing "B". The remove() method should advance _{previousToLastReturned.next} so that it points to the node containing "D". Then your code should set canRemove to false and set _{previousToLastReturned} to null.

Your remove() code will need to treat removing the head node and removing the tail node as special cases. Note also that it is possible that you are removing the only node in the list, which would be both the head and the tail simultaneously. So be sure to handle that case as well.

____________________________________________________________________________________________________________________________

Here is the MyList.java Code

public interface MyList extends java.lang.Iterable {

/** Add a new element at the end of this list */

public void add(E e);

/** Add a new element at the specified index in this list */

public void add(int index, E e);

/** Clear the list */

public void clear();

/** Return true if this list contains the element */

public boolean contains(E e);

/** Return the element from this list at the specified index */

public E get(int index);

/** Return the index of the first matching element in this list.

* Return -1 if no match. */

public int indexOf(E e);

/** Return true if this list contains no elements */

public boolean isEmpty();

/** Return the index of the last matching element in this list

* Return -1 if no match. */

public int lastIndexOf(E e);

/** Remove the first occurrence of the element o from this list.

* Shift any subsequent elements to the left.

* Return true if the element is removed. */

public boolean remove(E e);

/** Remove the element at the specified position in this list

* Shift any subsequent elements to the left.

* Return the element that was removed from the list. */

public E remove(int index);

/** Replace the element at the specified position in this list

* with the specified element and returns the new set. */

public Object set(int index, E e);

/** Return the number of elements in this list */

public int size();

/** Return an iterator for the list */

public java.util.Iterator iterator();

}

_____________________________________________________________________________________________

Here is MyAbstractList.java code

public abstract class MyAbstractList implements MyList {

 protected int size = 0; // The size of the list

 /** Create a default list */

 protected MyAbstractList() {

 }

 /** Create a list from an array of objects */

 protected MyAbstractList(E[] objects) {

 for (int i = 0; i < objects.length; i++)

 add(objects[i]);

 }

 @Override /** Add a new element at the end of this list */

 public void add(E e) {

 add(size, e);

 }

 @Override /** Return true if this list contains no elements */

 public boolean isEmpty() {

 return size == 0;

 }

 @Override /** Return the number of elements in this list */

 public int size() {

 return size;

 }

 @Override /** Remove the first occurrence of the element e 

 * from this list. Shift any subsequent elements to the left.

 * Return true if the element is removed. */

 public boolean remove(E e) {

 if (indexOf(e) >= 0) {

 remove(indexOf(e));

 return true;

 }

 else

 return false;

 }

}

_____________________________________________________________________________________________________________

Here is MyLinkedList.java code

import java.util.NoSuchElementException;

public class MyLinkedList extends MyAbstractList {

 private Node head, tail;

 /** Create a default list */

 public MyLinkedList() {

 }

 /** Create a list from an array of objects */

 public MyLinkedList(E[] objects) {

 super(objects);

 }

 /** Return the head element in the list */

 public E getFirst() {

 if (size == 0) {

 throw new NoSuchElementException();

 }

 else {

 return head.element;

 }

 }

 /** Return the last element in the list */

 public E getLast() {

 if (size == 0) {

 throw new NoSuchElementException();

 }

 else {

 return tail.element;

 }

 }

 /** Add an element to the beginning of the list */

 public void addFirst(E e) {

 Node newNode = new Node(e); // Create a new node

 newNode.next = head; // link the new node with the head

 head = newNode; // head points to the new node

 size++; // Increase list size

 if (tail == null) // the new node is the only node in list

 tail = head;

 }

 /** Add an element to the end of the list */

 public void addLast(E e) {

 Node newNode = new Node(e); // Create a new for element e

 if (tail == null) {

 head = tail = newNode; // The new node is the only node in list

 }

 else {

 tail.next = newNode; // Link the new with the last node

 tail = tail.next; // tail now points to the last node

 }

 size++; // Increase size

 }

 @Override /** Add a new element at the specified index 

 * in this list. The index of the head element is 0 */

 public void add(int index, E e) {

 if (index < 0 || index > size) {

 throw new IndexOutOfBoundsException

 ("Index: " + index + ", Size: " + size);

 }

 else if (index == 0) {

 this.addFirst(e);

 }

 else if (index == size) {

 this.addLast(e);

 }

 else {

 Node current = head;

 for (int i = 1; i < index; i++) {

 current = current.next;

 }

 Node temp = current.next;

 current.next = new Node(e);

 (current.next).next = temp;

 size++;

 }

 }

 /** Remove the head node and

 * return the object that is contained in the removed node. */

 public E removeFirst() {

 if (size == 0) {

 throw new NoSuchElementException();

 }

 else {

 Node temp = head;

 head = head.next;

 size--;

 if (head == null) {

 tail = null;

 }

 return temp.element;

 }

 }

 /** Remove the last node and

 * return the object that is contained in the removed node. */

 public E removeLast() {

 if (size == 0) {

 throw new NoSuchElementException();

 }

 else if (size == 1) {

 Node temp = head;

 head = tail = null;

 size = 0;

 return temp.element;

 }

 else {

 Node current = head;

 for (int i = 0; i < size - 2; i++) {

 current = current.next;

 }

 Node temp = tail;

 tail = current;

 tail.next = null;

 size--;

 return temp.element;

 }

 }

 @Override /** Remove the element at the specified position in this 

 * list. Return the element that was removed from the list. */

 public E remove(int index) {

 checkIndex(index);

 if (index == 0) {

 return removeFirst();

 }

 else if (index == size - 1) {

 return removeLast();

 }

 else {

 Node previous = head;

 for (int i = 1; i < index; i++) {

 previous = previous.next;

 }

 Node current = previous.next;

 previous.next = current.next;

 size--;

 return current.element;

 }

 }

 @Override /** Override toString() to return elements in the list */

 public String toString() {

 StringBuilder result = new StringBuilder("[");

 Node current = head;

 for (int i = 0; i < size; i++) {

 result.append(current.element);

 current = current.next;

 if (current != null) {

 result.append(", "); // Separate two elements with a comma

 }

 else {

 result.append("]"); // Insert the closing ] in the string

 }

 }

 return result.toString();

 }

 @Override /** Clear the list */

 public void clear() {

 size = 0;

 head = tail = null;

 }

 @Override /** Return true if this list contains the element e */

 public boolean contains(E e) {

 System.out.println("Implementation left as an exercise");

 return true;

 }

 @Override /** Return the element at the specified index */

 public E get(int index) {

 System.out.println("Implementation left as an exercise");

 return null;

 }

 @Override /** Return the index of the head matching element in 

 * this list. Return -1 if no match. */

 public int indexOf(E e) {

 System.out.println("Implementation left as an exercise");

 return 0;

 }

 @Override /** Return the index of the last matching element in 

 * this list. Return -1 if no match. */

 public int lastIndexOf(E e) {

 System.out.println("Implementation left as an exercise");

 return 0;

 }

 @Override /** Replace the element at the specified position 

 * in this list with the specified element. */

 public E set(int index, E e) {

 System.out.println("Implementation left as an exercise");

 return null;

 }

 @Override /** Override iterator() defined in Iterable */

 public java.util.Iterator iterator() {

 return new LinkedListIterator();

 }

 private void checkIndex(int index) {

 if (index < 0 || index >= size)

 throw new IndexOutOfBoundsException

 ("Index: " + index + ", Size: " + size);

 }

 private class LinkedListIterator 

 implements java.util.Iterator {

 private Node current = head; // Node containing the next element in the iteration

 @Override

 public boolean hasNext() {

 return (current != null);

 }

 @Override

 public E next() {

 if (!hasNext())

 throw new NoSuchElementException();

 E e = current.element;

 current = current.next;

 return e;

 }

 @Override

 public void remove() {

 System.out.println("Implementation left as an exercise");

 }

 }

 private static class Node {

 E element;

 Node next;

 public Node(E element) {

 this.element = element;

 }

 }

}

_____________________________________________________________________________________________________________________

Here is the test code for the program (TestMyLinkedListForHW.java)

// TestMyLinkedListForHW.java

// This program tests the following methods --

// In the MyLinkedList class:

// boolean contains(E e)

// E get(int index)

// int indexOf(E e)

// int lastIndexOf(E e)

// E set(int index, E d)

// In the MyLinkedListIterator class:

// void remove()

import java.util.*;

public class TestMyLinkedListForHW {

 public static void main(String[] args) {

 MyLinkedList stringList = new MyLinkedList();

 stringList.add("Alabama");

 stringList.add("Alaska");

 stringList.add("Arizona");

 stringList.add("Arkansas");

 stringList.add(4, "California");

 stringList.set(1, "Arkansas");

 if (stringList.toString().equals("[Alabama, Arkansas, Arizona, Arkansas, California]"))

 System.out.println("Test 1 successful");

 else {

 System.out.println("Test 1 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.contains("Arizona"))

 System.out.println("Test 2 successful");

 else {

 System.out.println("Test 2 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (!stringList.contains("Alaska"))

 System.out.println("Test 3 successful");

 else {

 System.out.println("Test 3 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.get(2).equals("Arizona"))

 System.out.println("Test 4 successful");

 else {

 System.out.println("Test 4 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.indexOf("Arkansas") == 1)

 System.out.println("Test 5 successful");

 else {

 System.out.println("Test 5 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.lastIndexOf("Arkansas") == 3)

 System.out.println("Test 6 successful");

 else {

 System.out.println("Test 6 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.set(2, null).equals("Arizona"))

 System.out.println("Test 7 successful");

 else {

 System.out.println("Test 7 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.get(2) == null)

 System.out.println("Test 8 successful");

 else {

 System.out.println("Test 8 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.contains(null))

 System.out.println("Test 9 successful");

 else {

 System.out.println("Test 9 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.indexOf(null) == 2)

 System.out.println("Test 10 successful");

 else {

 System.out.println("Test 10 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.lastIndexOf(null) == 2)

 System.out.println("Test 11 successful");

 else {

 System.out.println("Test 11 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.indexOf("California") == 4)

 System.out.println("Test 12 successful");

 else {

 System.out.println("Test 12 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.lastIndexOf("Alabama") == 0)

 System.out.println("Test 13 successful");

 else {

 System.out.println("Test 13 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 if (stringList.lastIndexOf("Kentucky") == -1)

 System.out.println("Test 14 successful");

 else {

 System.out.println("Test 14 failed");

 System.out.println(stringList);

 System.exit(1);

 }

 try {

 stringList.get(-1);

 System.out.println("Test 15 failed");

 System.exit(1);

 }

 catch (IndexOutOfBoundsException ex) {

 System.out.println("Test 15 successful");

 }

 try {

 stringList.get(5);

 System.out.println("Test 16 failed");

 System.exit(1);

 }

 catch (IndexOutOfBoundsException ex) {

 System.out.println("Test 16 successful");

 }

 try {

 stringList.set(-1, "Colorado");

 System.out.println("Test 17 failed");

 System.exit(1);

 }

 catch (IndexOutOfBoundsException ex) {

 System.out.println("Test 17 successful");

 }

 try {

 stringList.set(5, "Conneticut");

 System.out.println("Test 18 failed");

 System.exit(1);

 }

 catch (IndexOutOfBoundsException ex) {

 System.out.println("Test 18 successful");

 }

 MyLinkedList