Problem 1. Extend the Array class adding the following two new methods:

a) [25 points] the method called min that returns the smallest number in the array.

E.g., applying min to the array [3, 2, 0, 10, 9, 7], we get 10. b) [25 points] the method called reverse that reverses the array. E.g., applying reverse to the array [3, 2, 0, 10, 9, 7], we change it to [7, 9, 10, 0, 2, 3].

Problem 2. [50 points] Extend the LinkedList class adding a new method printMiddle that prints values of the middle node(s) of a linked list in one pass. Assume that we do not know the size of the linked list ahead of time.

Note that if the list has an odd number of nodes, there will be only one middle node; otherwise, there will be two middle nodes. E.g., applying printMiddle to the linked list [1 7 5 4 2], we get 5; applying it to [1 2 3 4 5 6], we get 3 and 4.

Submission in Java

You only have to submit the source code of the classes Array and LinkedList with your methods added. Important: you need to submit files that have java extension, not class extension. Thus, your submission should include Array.java and LinkedList.java, and should NOT include main from where you ran and tested your code. You code will be run on the following main:

public class Main {

public static void main(String[] args) {

int length = 6;

Array arr = new Array(length);

for (int i = -3; i < length - 3; i++) {

arr.insert(i);

}

// problem 1.a

System.out.println(arr.min());

// problem 1.b

arr.reverse();

arr.print();

LinkedList list = new LinkedList();

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

list.addFirst(i);

}

// problem 2

list.printMiddle();

list.deleteLast();

list.printMiddle();

}

}

Array class for the problem 1.

public class Array {

private int[] elems;

private int nElems;

public Array(int size) {

if (size < 0) {

throw new IllegalArgumentException();

}

elems = new int[size];

}

public void print() {

System.out.print("[");

for (int i = 0; i < nElems; ++i)

if (i < nElems - 1) {

System.out.print(elems[i] + ", ");

} else {

System.out.print(elems[i]);

}

System.out.println("]");

}

public void insert(int element) {

// if the array is full, increases its size

if (elems.length == 0) {

int[] extendedElems = new int[1];

elems = extendedElems;

}

if (elems.length == nElems) {

int[] extendedElems = new int[nElems * 2];

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

extendedElems[i] = elems[i];

}

elems = extendedElems;

}

// otherwise, adds a new element at the end

elems[nElems] = element;

nElems++;

}

public void removeAt(int index) {

if (index < 0 || index >= nElems) {

throw new IllegalArgumentException();

} else {

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

elems[i] = elems[i + 1];

}

nElems--;

}

}

public int indexOf(int element) {

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

if (elems[i] == element) {

return i;

}

}

return -1;

}

public boolean contains(int element) { return (indexOf(element) != -1);

}

}

LinkedList class for the problem 2.

import java.util.NoSuchElementException;

public class LinkedList {

private Node head; // first

private Node tail; // last

private class Node {

private int value;

private Node next;

public Node(int value) {

this.value = value;

}

}

private boolean isEmpty() {

return (head == null);

}

private boolean hasNext(Node node) {

return (node.next != null);

}

public void print() {

Node current = head;

System.out.print("[");

while (current != null) {

if (hasNext(current)) {

System.out.print(current.value + ", ");

} else {

System.out.print(current.value);

}

current = current.next;

}

System.out.println("]");

}

public void addFirst(int value) {

Node node = new Node(value);

if (isEmpty()) {

head = tail = node;

} else {

node.next = head;

head = node;

}

}

public void addLast(int value) {

Node node = new Node(value);

if (isEmpty()) {

head = tail = node;

} else {

tail.next = node;

tail = node;

}

}

public int indexOf(int value) {

int index = 0;

Node current = head;

while (current != null) {

if (current.value == value) {

return index;

}

index++;

current = current.next;

}

return -1;

}

public boolean contains(int value) {

return (indexOf(value) != -1);

}

public void deleteFirst() {

if (isEmpty()) {

throw new NoSuchElementException();

}

if (head == tail) {

head = tail = null;

return;

}

Node second = head.next;

head.next = null;

head = second;

}

public Node previous(Node node) {

if (isEmpty())

throw new NoSuchElementException();

Node current = head;

while (current.next != node) {

if (!hasNext(current)) {

throw new NoSuchElementException();

}

current = current.next;

}

return current;

}

public void deleteLast() {

if (isEmpty()) {

throw new NoSuchElementException();

}

if (head == tail) {

head = tail = null;

return;

}

Node lastButOne = previous(tail);

lastButOne.next = null;

tail = lastButOne;

}

public int getKthNodeFromTheEnd(int k) {

if (isEmpty()) {

throw new IllegalStateException();

}

if (k <= 0) {

throw new IllegalArgumentException();

}

Node first = head;

Node second = head;

for (int i = 0; i < k - 1; i++) {

if (!hasNext(first)) {

throw new IllegalArgumentException();

}

first = first.next;

}

while (first != tail) {

first = first.next;

second = second.next;

}

return second.value;

}

}