Q2 - 25 pts) The Fibonacci sequence is generated using the following recursion: F(n) = F(n-2) + F(n-1), for n > 1. F(0) = 0 and F(1) = 1. In this question, you will generate the Fibonacci sequence as a "Singly Linked List" of integers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., N where N is the largest integer in the sequence that is less than the integer J, comprising the last three digits of your J#. For example, if your J# is J00543244, then J is 244. In that case, the Fibonacci sequence that is generated should be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233. If the last three digits of your J# form an integer that is less than 100, add 100 to the last three digits of your J# and use the resulting value as J. For example, if your J# is J00543034, then J is 34 + 100 = 134 and the Fibonacci sequence generated would be: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. You are given the code for the Singly Linked List-based implementation of the List ADT. Add a member function constructSequence(int) to the List class that takes an integer argument (upperBound: J for the Fibonacci sequence) The main function given to you already inserts the first two nodes (with data 0 and 1 respectively) to a List called FibonacciList. Your task will be to implement the constructSequence function that will insert a sequence of nodes (one node per iteration) to the FibonacciList whose last element will be the largest element in the sequence that is less than the upperBound.

the singly linked List-code is:

import java.util.*;

// implementing the dynamic List ADT using Linked List

class Node{

private int data; private Node nextNodePtr;

public Node(){}

public void setData(int d){ data = d; }

public int getData(){ return data; }

public void setNextNodePtr(Node nodePtr){ nextNodePtr = nodePtr; }

public Node getNextNodePtr(){ return nextNodePtr; }

}

class List{

private Node headPtr;

public List(){ headPtr = new Node(); headPtr.setNextNodePtr(null); }

public Node getHeadPtr(){ return headPtr; }

public boolean isEmpty(){

if (headPtr.getNextNodePtr() == null) return true;

return false; }

public void insert(int data){

Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr;

while (currentNodePtr != null){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr.getNextNodePtr(); }

Node newNodePtr = new Node(); newNodePtr.setData(data); newNodePtr.setNextNodePtr(null); prevNodePtr.setNextNodePtr(newNodePtr);

}

public void insertAtIndex(int insertIndex, int data){

Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == insertIndex) break;

prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr.getNextNodePtr(); index++; }

Node newNodePtr = new Node(); newNodePtr.setData(data); newNodePtr.setNextNodePtr(currentNodePtr); prevNodePtr.setNextNodePtr(newNodePtr);

}

public int read(int readIndex){

Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr; int index = 0;

while (currentNodePtr != null){

if (index == readIndex) return currentNodePtr.getData();

prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr.getNextNodePtr();

index++;

}

return -1; // an invalid value indicating // index is out of range

}

public void modifyElement(int modifyIndex, int data){

Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr; int index = 0;

while (currentNodePtr != null){

if (index == modifyIndex){ currentNodePtr.setData(data); return; }

prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr.getNextNodePtr();

index++; }

}

public void deleteElementAtIndex(int deleteIndex){

Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr; Node nextNodePtr = headPtr; int index = 0;

while (currentNodePtr != null){

if (index == deleteIndex){ nextNodePtr = currentNodePtr.getNextNodePtr(); break; }

prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr.getNextNodePtr();

index++; }

prevNodePtr.setNextNodePtr(nextNodePtr);

}

public void deleteElement(int deleteData){

Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr; Node nextNodePtr = headPtr;

while (currentNodePtr != null){

if (currentNodePtr.getData() == deleteData){ nextNodePtr = currentNodePtr.getNextNodePtr(); break; }

prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr.getNextNodePtr();

}

prevNodePtr.setNextNodePtr(nextNodePtr);

}

public void IterativePrint(){

Node currentNodePtr = headPtr.getNextNodePtr();

while (currentNodePtr != null){ System.out.print(currentNodePtr.getData()+" "); currentNodePtr = currentNodePtr.getNextNodePtr(); }

System.out.println();

}

public void constructSequence(int upperBound){

Node firstNodePtr = headPtr.getNextNodePtr(); Node secondNodePtr = firstNodePtr.getNextNodePtr();

// complete the code to construct a singly linked list that has the elements of the // Fibonacci sequence less than or equal to the upperBound

}

}

class SinglyLinkedList{

public static void main(String[] args){

Scanner input = new Scanner(System.in);

List FibonacciList = new List();

FibonacciList.insert(0); FibonacciList.insert(1);

int upperBoundFibonacciValue; System.out.print("Enter the upper bound for the sequence: "); upperBoundFibonacciValue = input.nextInt();

FibonacciList.constructSequence(upperBoundFibonacciValue);

FibonacciList.IterativePrint();

}

}