For the following class, create the methods:

void smallestFirst() method that moves the node with the smallest integer in the list to become the first node.

copy constructor and clone() methods. Both must create a deep copy of the list.

private class Node

{

int value;

Node next;

/**

Constructor.

@param val The element to store in the node.

@param n The reference to the successor node.

*/

Node(int val, Node n)

{

value = val;

next = n;

}

/**

Constructor.

@param val The element to store in the node.

*/

Node(int val)

{

// Call the other (sister) constructor.

this(val, null);

}

}

private Node first; // list head

public String reverseToString(){

String result = "";

Node temp = first;

while(temp != null) {

result = temp.value + result;

temp = temp.next;

}

return result;

}

public String recReverseToString() {

return recReverseToStringUtil(first);

}

public String recReverseToStringUtil(Node n) {

if(n == null)

return "";

return Integer.toString(n.value) + recReverseToStringUtil(n.next);

}

/**

Constructor.

*/

public List()

{

first = null;

}

/**

The isEmpty method checks to see

if the list is empty.

@return true if list is empty,

false otherwise.

*/

public boolean isEmpty()

{

return first == null;

}

/**

The size method returns the length of the list.

@return The number of elements in the list.

*/

public int size()

{

int count = 0;

Node p = first;

while (p != null)

{

// There is an element at p

count ++;

p = p.next;

}

return count;

}

/**

The add method adds an element to

the end of the list.

@param e The value to add to the

end of the list.

*/

public void add(int e)

{

if (isEmpty())

{

first = new Node(e);

}

else

{

// Add to end of existing list

Node current = first;

// moving current reference to the ent of the list

while(current.next!=null) current = current.next;

current.next = new Node(e);

}

}

/**

The add method adds an element at a position.

@param e The element to add to the list.

@param index The position at which to add

the element.

@exception IndexOutOfBoundsException When

index is out of bounds.

*/

public void add(int index, int e)

{

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

{

String message = String.valueOf(index);

throw new IndexOutOfBoundsException(message);

}

// Index is at least 0

if (index == 0)

{

// New element goes at beginning

first = new Node(e, first);

return;

}

// Set a reference pred to point to the node that

// will be the predecessor of the new node

Node pred = first;

for (int k = 1; k <= index - 1; k++)

{

pred = pred.next;

}

// Splice in a node containing the new element

pred.next = new Node(e, pred.next);

}

/**

The toString method computes the string

representation of the list.

@return The string form of the list.

*/

public String toString()

{

StringBuilder strBuilder = new StringBuilder();

// Use p to walk down the linked list

Node p = first;

while (p != null)

{

strBuilder.append(p.value + " ");

p = p.next;

}

return strBuilder.toString();

}

/**

The remove method removes the element at an index.

@param index The index of the element to remove.

@return The element removed.

@exception IndexOutOfBoundsException When index is

out of bounds.

*/

public int remove(int index)

{

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

{

String message = String.valueOf(index);

throw new IndexOutOfBoundsException(message);

}

int element; // The element to return

if (index == 0)

{

// Removal of first item in the list

element = first.value;

first = first.next;

}

else

{

// To remove an element other than the first,

// find the predecessor of the element to

// be removed.

Node pred = first;

// Move pred forward index - 1 times

for (int k = 1; k <= index -1; k++)

pred = pred.next;

// Store the value to return

element = pred.next.value;

// Route link around the node to be removed

pred.next = pred.next.next;

}

return element;

}

}