The only file that you need to work on is MyLinkedList.java. The other three files (myList.java, MyAbstractList.java, and TestMyLinkedList.java) are simply given to you. Complete the method body for add(int index, E e) and remove(int index) and the three methods in the Iterator class.

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) { 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 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) { //TODO1: add e to the head

} else if (index >= size) { //TODO2: add e to the tail

} else { //TODO3: add e to the index i location

} }

/** Remove the head node and * return the object that is contained in the removed node. */ public E removeFirst() { if (size == 0) { return null; } 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) { return null; } 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) { if (index < 0 || index >= size) { return null; } else if (index == 0) { //TODO1: change the following statement: remove the element at head and return it. return null; } else if (index == size - 1) { //TODO2: change the following statement: remove the element at tail and return it. return null; } else { //TODO3: remove the element at ith index location and return it. return null; } }

@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; // Current index

@Override public boolean hasNext() { //TODO1: change null to a proper boolean expression return true; }

@Override public E next() { //TODO2: return the value at current and move current to the next node return null; }

@Override public void remove() { //TODO3: implement this method } }

private static class Node { E element; Node next;

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