reverse() Method for List class Start with classes List.java and ListDemo.java t
ID: 3725604 • Letter: R
Question
reverse() Method for List class
Start with classes List.java and ListDemo.java that can be found next to this assignment. Add a new public method void reverse() to the class. The method must reverse the linked list data structure. You can implement either iterative or recursive solution. Test your method in ListDemo.java. Make sure it works for empty list as well as with a list with just one element. Requirement: Complexity of your solution must be O(N).
reverseToString() and recReverseToString()
Continue working with the same List.java class. Add two more methods to the class: public String reverseToString() method creates a string that holds all the integers in the list in reverse order. Requirements: o DO NOT reverse list, just traverse it and create a string that holds the elements in reverse order. o Your solution must be O(N). o This solution must be iterative.
Lake Washington Institute of Technology CS 143 Computer Science II (Java) Instructor: Alexandra Vaschillo
public String recReverseToString() is a RECURSIVE method with the same functionality - creates a string that holds all the integers in the list in reverse order. Requirements: o DO NOT reverse list, just traverse it and create a string that holds the elements in reverse order. o Your solution must be O(N). o This solution must be recursive.
Copy Constructor and clone() Methods
Continue working with the same List.java class. Add a copy constructor and clone() methods. Both must create a deep copy of the list.
smallestFirst() Method
Continue working with the same List.java class. Add void smallestFirst() method that moves the node with the smallest integer in the list to become the first node.
package listdemo;
/**
*
* @author LWTECH
*/
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);
}
/**
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;
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package listdemo;
/**
*
* @author LWTECH
*/
public class ListDemo {
/**
* @param args the command line arguments
*/
public static void main(String [] args)
{
List myList = new List();
myList.add(1);
myList.add(2);
myList.add(0, 3);
myList.add(2, 4);
myList.add(4, 5);
System.out.println("The members of the list are:");
System.out.print(myList);
myList.reverseList();
System.out.println("After reversal:");
System.out.print(myList);
}
}
Explanation / Answer
Hi, I have implemented first two methods. Please repost in separate post for other method implementation.
/**
*
* @author LWTECH
*/
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
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;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.