/* * Complete the methods below. * None of the methods should modify the list, u
ID: 3908656 • Letter: #
Question
/*
* Complete the methods below.
* None of the methods should modify the list, unless that is the purpose of the method.
*
* You may not add any fields to the node or list classes.
* You may not add any methods to the node class.
*
* You MAY add private methods to the list class (helper functions for the recursion).
*/
public class MyLinked {
static class Node {
public Node (double item, Node next) { this.item = item; this.next = next; }
public double item;
public Node next;
}
int N;
Node first;
// write a function to compute the size of the list, using a loop
// empty list has size 0
public int sizeLoop () {
return StdRandom.uniform (100); //TODO: fix this
}
// write a function to compute the size of the list, using an optimistic, forward recursion
// empty list has size 0
public int sizeForward () {
return StdRandom.uniform (100); //TODO: fix this
}
// write a function to compute the size of the list, using an optimistic, backward recursion
// empty list has size 0
public int sizeBackward () {
return StdRandom.uniform (100); //TODO: fix this
}
// compute the position of the first 5.0 in the list, counting as an offset from the beginning.
// if 5.0 is the FIRST element, the position is 0
// if 5.0 does not appear, return a negative number
// you can write this using a loop or recursion, in any style, but you should only have one loop or recursive helper
// I would expect
// [0,1,2,5,5,5,5,5,8,9].positionOfFirstFiveFromBeginning() == 3
// [0,1,2,5,5,5,5,5,8,9].positionOfLastFiveFromEnd() == 2
Explanation / Answer
public int sizeLoop(){
Node p = first;
int count = 0;
while(p != null){
p = p.next;
count++;
}
return count;
}
private lengthForward(Node p){
if (p == null)
return 0;
else
return 1 + lengthForward(p.next);
}
public int sizeForward () {
return lengthForward(first);
}
private lengthBackward(Node p){
if (p == null)
return 0;
else
return lengthBackward(p.next) + 1;
}
public int sizeBackward() {
return lengthBackward(first);
}
public int positionOfFirstFiveFromBegining(){
Node p = first;
if (p.item == 5.0){
return 0;
}
else {
int count = 0;
while(p != null && p.item != 5.0){
p = p.next;
count++;
}
if (p == null)
return -1;
else
return count;
}
}
public int positionOfFirstFiveFromEnd(){
Node p = first;
if (p.item == 5.0){
return (sizeLoop() - 1);
}
else {
int count = 0;
int pos = -1;
while(p != null){
p = p.next;
if (p.item == 5.0)
pos = count;
}
if (pos == -1)
return -1;
else
return (sizeLoop() 1 - pos);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.