override method add(E e) so as to insert the element into a new node in an ordered list.

rewrite methods addFirst(E e), addLast(E e) and add(int index, E e) so as to insert the element into a new node in an ordered list.

implement methods contains(E e), get(int index), indexOf(E e), lastIndexOf(E e) and set(int index, E e) making any changes necessary to the code that improves efficiency for an ordered list.

Add code to class to demonstrate your implementations and that the list managed is an ordered list.

public class MyOrderedLinkedList extends MyAbstractList {

private Node head, tail; /**Create a default list*/ public MyOrderedLinkedList() { }

/**Create a list from an array of objects*/ public MyOrderedLinkedList(E[] objects) { super(objects); }

// ************************************************************** // ************************************************************** /** Add a new element to the list in order.*/ // ************************************************************** // ************************************************************** public void add(E e) { } /**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; } }

// ************************************************************** // ************************************************************** /**Must be rewritten to add a new element to the list in order.*/ // ************************************************************** // ************************************************************** 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; } }

// ************************************************************** // ************************************************************** /**Must be rewritten to add a new element to the list in order.*/ // ************************************************************** // ************************************************************** 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 // ************************************************************** // ************************************************************** /**Must be rewritten to add a new element to the list in order.*/ // ************************************************************** // ************************************************************** public void add(int index, E e) { if (index == 0) { addFirst(e); } else if (index >= size) { 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++; } }

// ************************************************************** // ************************************************************** /**Must be rewritten to do nothing and return null.*/ // ************************************************************** // ************************************************************** public E removeFirst() { if (size == 0) { return null; } else { Node temp = head; head = head.next; size--; if (head == null) { tail = null; } return temp.element; } }

// ************************************************************** // ************************************************************** /**Must be rewritten to do nothing and return null.*/ // ************************************************************** // ************************************************************** 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) { 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) { if (size == 0) { return false; } else { Node 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 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 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. Return -1 if * no match.*/ public int lastIndexOf(E e) { int index = -1; Node 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 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 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() { 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"); } } // end of LinkedListIterator

private static class Node {

E element; Node next;

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

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 /**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. * Must be overridden to avoid multiple calls to indexOf. */ // ************************************************************** // ************************************************************** public boolean remove(E e) { int i = indexOf(e); if (i >= 0) { remove(i); remove(e); //call this method again to go through the list again to see if theres another occurrence return true; } else { return false; } } }

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(); }