Chapter 24 Exercise 16, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

24.16 (Test MyLinkedList ) Design and write a complete test program to test if the MyLinkedList class in Listing 24.6 meets all requirements.

public class MyLinkedList<E> extends MyAbstractList<E> {
 private Node<E> 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) {
   return null;
  }
  else {
   return head.element;
  }
 }

 /** Return the last element in the list */
 public E getLast() {
  if (size == 0) {
   return null;
  }
  else {
   return tail.element;
  }
 }

 /** Add an element to the beginning of the list */
 public void addFirst(E e) {
  Node<E> 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++; // Increate 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<E> newNode = new Node<>(e); // Create a new node for e
  if (tail == null) {
   head = tail = newNode; // The on;y node in list
  }
  else {
   tail.next = newNode; // Link the new node 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 lndex of the head element is 0 */
 public void add(int index, E e) {
  if (index == 0) addFirst(e); // Insert first
  else if (index >= size) addLast(e); // Insert last
  else { // Insert in the middle
   Node<E> current = head;
   for (int i = 1; i < index; i++)
    current = current.next;
   Node<E> 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) return null; // Nothing to delete
  else {
   Node<E> temp = head; // keep the first node temporarily
   head = head.next; // Move head to point to next node
   size--; // Reduce size by 1
   return temp.element; // Return the deleted element
  }
 }

 /** Remove the last node and
  * return the object that is contained in the removed node. */
 public E removeLast() {
  if (size == 0) return null; // Nothing to remove
  else if (size == 1) { // Only one element in the list
   Node<E> temp = head;
   head = tail = null; // list becomes empty
   size = 0;
   return temp.element;
  }
  else {
   Node<E> current = head;

   for (int i = 0; i < size - 2; i++)
    current = current.next;  

   Node<E> 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) {
  if (index < 0 || index >= size) return null; // Out of range
  else if (index == 0) return removeFirst(); // Remove first
  else if (index == size - 1) return removeLast(); // Remove last
  else {
   Node<E> previous = head;

   for (int i = 1; i < index; i++) {
    previous = previous.next;
   }

   Node<E> current = previous.next;
   previous.next = current.next;
   size--;
   return current.element;
  }
 }

 @Override
 public String toString() {
  StringBuilder result = new StringBuilder("[");

  Node<E> 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) {
  if (size == 0) return false;
  else {
   Node<E> current = head;

   while (current != null) {
    if (current.element == e)
     return true;
    current = current.next;
   }
  }
  return false;
 }

 @Override /** Return the element at the specified index */
 public E get(int index) {
  if (index < 0 || index >= size) return null; // Out of range
  else if (index == 0) return getFirst();
  else if (index == size - 1) return getLast();
  else {
   Node<E> current = head.next;

   for (int i = 1; i < index; i++)
    current = current.next;
   return current.element;
  }

 }

 @Override /** Return the index of the head matching element
  * in this list. Return -1 if no match. */
 public int indexOf(E e) {
  if (head.element == e) return 0;
  else if (tail.element == e) return size - 1;
  else {
   Node<E> current = head.next;
   int index = 1;
   while (current != null) {
    if (current.element == e)
     return index;
    current = current.next;
    index++;
   }
  }
  return -1;
 }

 @Override /** Return the index of the last matching element
  * in this list. Rreturn -1 if on match. */
 public int lastIndexOf(E e) {
  int index = -1;
  Node<E> current = head;
  for (int i = 0; i < size; i++) {
   if (current.element == e)
    index = i;
   current = current.next;
  }

  return index;
 }

 @Override /** Replace the element at the specified position
  * in this list with the specified element. */
 public E set(int index, E e) {
  if (index < 0 || index > size - 1) return null;
  else {
   Node<E> current = head;
   for (int i = 0; i < index; i++)
    current = current.next;
 
   current.element = e;
   return current.element;
  }
 }

 @Override /** Override iterator() defined in Iterable */
 public java.util.Iterator<E> iterator() {
  return new LinkedListIterator();
 }

 public class LinkedListIterator
   implements java.util.Iterator<E> {
  private Node<E> current = head; // Current index

  @Override
  public boolean hasNext() {
   return (current != null);
  }

  @Override
  public E next() {
   E e = current.element;
   current = current.next;
   return e;
  }

  @Override
  public void remove() {
   System.out.println("Implementation left as an exercise");
  }
 }

 // This class is only used in LinkedList, so it is private.
 // This class does not need to access any
 // instance members of LinkedList, so it is defined static.
 private static class Node<E> {
  E element;
  Node<E> next;

  public Node(E element) {
   this.element = element;
  }
 }
}

Solution: Program Flow:
• Create a MyLinkedListTestProgram class for the test of MyLinkedList class.
• This MyLinkedList class extends MyAbstractList class which implements MyList interface.
• In main() method of MyLinkedListTestProgram create an object of the MyLinkedList class
• add() methods that is used to insert elements in the linked list or to insert the elements at specified index of the array list.
• addFirst() method to insert String at first position of the list.
• addLast() method to insert String at last position of the list.
• remove () method which is used to remove elements from the linked list or remove any elements at specified index.
• removeFirst() method to remove String at first position of the list.
• removeLast() method to remove as last String element of the list.
• getFirst() method to get the first element of the list.
• getLast() method to get the last element of the list.
• contains() which is Boolean type method and this method check entered name is in the list or not.
• This method returns true when entered name exist else returns false.
• get() method used to get element at the specified index.
• indexOf()method to check entered name is in list or not. This method returns index of the entered name else returns -1.
• lastIndexOf() method to check entered name is in list or not. This method returns index of the entered name else returns -1.
• set()method is used to replace list elements by entered data at the specified index position.
• hasNext()returns true if at least one elements is in the list.
• next()returns true if current element is in the list.
• remove() method remove the size of the list.

import java.util.Iterator;
// Create class MyLinkedListTestProgram
public class MyLinkedListTestProgram {
 // main() method declare
 public static void main(String args[]) {
  // create linked list object listelement
  MyLinkedList listelement = new MyLinkedList < > ();
  // Add String to the linkedlist
  listelement.add("Smith");
  System.out.println("Add String: " + listelement);
  // Add String at specified index
  listelement.add(0, "John");
  System.out.println("Add String at 0 index: " + listelement);
  //Add as first String
  listelement.addFirst("Ethlic");
  System.out.println("Add at first index: " + listelement);
  //Add String at index 2 position
  listelement.add(2, "Abraham");
  System.out.println("Add at index 2: " + listelement);
  //Add as last String
  listelement.addLast("Cathlic");
  System.out.println("Add at last position: " + listelement);
  // Add String to the linkedlist
  listelement.add("Rihana");
  System.out.println("Add a String: " + listelement);
  //remove this String from the list
  listelement.remove(listelement.size - 1);
  System.out.println("RemoveLastString: " + listelement);
  //remove this String from the list
  listelement.remove("John");
  System.out.println("RemoveEnterString: " + listelement);
  // remove last String from the list
  listelement.removeLast();
  System.out.println("RemoveLast String: " + listelement.toString());
  // Print all remaining String in the list
  System.out.print("Remaining String in list: ");
  for (String s: listelement)
   System.out.print(s.toUpperCase() + " ");
  // Call getFirst() method to get
  // the first element of the list
  System.out.println("\n get first element: " + listelement.getFirst());
  // Call getLast() method to get
  // the last element of the list
  System.out.println("\n get last element: " + listelement.getLast());
  // Call contains() method to know
  // elements are in list or not
  System.out.println("\n contains elements: " + listelement.contains("Smith"));
  // Call get() method to retrieve
  // element at specified index
  System.out.println("get element: " + listelement.get(1));
  // Call indexOf() method to get
  // the index of specified element.
  System.out.println("index Of element: " + listelement.indexOf("Smith"));
  // Call lastIndexOf() method to get
  // the index of specified element.
  System.out.println("last index Of element: " + listelement.lastIndexOf("Ethlic"));
  // Call set() method to replace Abraham
  // to Michiel at specified index 1
  System.out.println("set element: " + listelement.set(1, "Michiel"));
  // Print all elements of list
  for (String s: listelement)
   System.out.print(s.toUpperCase() + " ");
  // Create an object of Iterator
  Iterator itr = listelement.iterator();
  // Call hasNext() method to check
  // if any element in list it returns true
  System.out.println("hasNext: " + itr.hasNext());
  // Call next() method, it returns true
  // if current element is in list
  System.out.println(" next: " + itr.next());
  System.out.println("remove size of list. ");
  // Call remove() method to remove size
  itr.remove();
  // print to next line
  System.out.println();
  // Call clear() method to remove
  // all elements form the list
  listelement.clear();
  System.out.print("All elements are clear now. ");
 }
}

Output:
Add String: [Smith]
Add String at 0 index: [John, Smith]
Add at first index: [Ethlic, John, Smith]
Add at index 2: [Ethlic, John, Abraham, Smith]
Add at last position: [Ethlic, John, Abraham, Smith, Cathlic]
Add a String: [Ethlic, John, Abraham, Smith, Cathlic, Rihana]
RemoveLastString: [Ethlic, John, Abraham, Smith, Cathlic]
RemoveEnterString: [Ethlic, Abraham, Smith, Cathlic]
RemoveLast String: [Ethlic, Abraham, Smith]
Remaining String in list: ETHLIC ABRAHAM SMITH
get first element: Ethlic
get last element: Smith
contains elements: true
get element: Abraham
index Of element: 2
last index Of element: 0
set element: Abraham
ETHLIC MICHIEL SMITH
hasNext: true
next: Ethlic
remove size of list.
All elements are clear now.