Copy Constructor and clone() Methods

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

smallestFirst() Method

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

List.java

public class 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

/**

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

}

/**

* Reverse to string.

*/

public void reverseToString() {

Node current = first; // used to search through the list

Node last = null; // stores the last element that we printed

while (last != first) { // = we didn't print everything yet

// find next element to print - it's one element before we reach "last"

while (current.next != last) {

current = current.next;

}

// Store the current element as the new last and print it

last = current;

System.out.println(last.value);

// reset current and start all over

current = first;

}

}

/**

* Helper class for Recursive call

* Rec reverse to string.

*/

public void recReverseToString()

{

printReverse(first);

}

/**

* Prints the reverse.

*

* @param node is the reference to the position in the list

* @return node.value from end

*/

private void printReverse(Node node)

{

if (node.next != null)

{

printReverse(node.next);

}

System.out.println(node.value);

}

/**

* Reverse list.

*/

public void reverseList() {

Node reverse = null;

Node current = first;

while (current != null) {

Node next = current.next;

current.next = reverse;

reverse = current;

current = next;

}

first = reverse;

}

/**

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;

}

}