For the following class, create the methods: void smallestFirst() method that mo
ID: 3728875 • Letter: F
Question
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;
}
}
Explanation / Answer
Best Regards
The functions as required have been implemented as follows :
List.java
class List implements Cloneable{
private class Node implements Cloneable
{
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);
}
public Node clone() throws CloneNotSupportedException {
return (Node) super.clone();
}
}
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;
}
public void smallestFirst() {
if(first == null) return;
//lets first find out the min value
Node p = first;
int m = Integer.MAX_VALUE, index = -1, i = 0;
while (p != null) {
if(p.value < m){
m = p.value;
index = i;
}
p = p.next;
i++;
}
remove(index); //remove the Node
add(0, m); //insert it at the beginning
}
public List(List l){
if(l.first != null){
int sz = l.size();
int values[] = new int[sz];
int i = 0;
Node itr = l.first;
while(itr != null){
values[i++] = itr.value;
itr = itr.next;
}
Node prev = null;
for(i = sz - 1; i >= 0; i--){
prev = new Node(values[i], prev);
}
first = prev;
}
}
protected List clone() throws CloneNotSupportedException{
List cloned = (List) super.clone();
cloned.first = this.first.clone();
Node itr = cloned.first;
Node itr1 = this.first;
while(itr1.next != null){
itr.next = itr1.next.clone();
itr = itr.next;
itr1 = itr1.next;
}
itr.next = null;
return cloned;
}
public static void main(String[] args) throws CloneNotSupportedException{
List a = new List();
a.add(12);a.add(66);a.add(3);a.add(45);
List b = new List(a);
b.add(29);
List c = b.clone();
a.smallestFirst();
c.smallestFirst();
System.out.println(a);
System.out.println(b);
System.out.println(c);
}
}