9.8 LAB: Finding the first and last occurrence of a value (doubly-linked list)

Given main() and a PeopleNode class, complete the PeopleList class by writing findFirst() and findLast() methods. The findFirst() method should find the first occurrence of an age value in the linked list and return the corresponding node. Similarly, the findLast() method should find the last occurrence of the age value in the linked list and return the corresponding node. For both methods, if the age value is not found, null should be returned. The program will replace the name value of each found node with a new name.

Ex. If the input is

Alex 23
Tom 41
Michelle 34
Vicky 23
-1
23
Connor
34
Michela

the output is

List before replacing:
Alex, 23
Tom, 41
Michelle, 34
Vicky, 23

List after replacing the first occurrence of 23:
Connor, 23
Tom, 41
Michelle, 34
Vicky, 23

List after replacing the last occurrence of 34:
Connor, 23
Tom, 41
Michela, 34
Vicky, 23

FindOccurence.java

import java.util.Scanner;

public class FindOccurrence {
public static void main (String[] args) {
Scanner scnr = new Scanner(System.in);
PersonList personList = new PersonList();
PersonNode curNode;
PersonNode foundFirst;
PersonNode foundLast;
String name;
String replaceName;
int age;
int findAge;

name = scnr.next();

while (!name.equals("-1")) {
// Insert into linked list   
age = scnr.nextInt();
curNode = new PersonNode(name, age);
personList.append(curNode);
name = scnr.next();
}

System.out.println("List before replacing:");
personList.printPersonList();

foundFirst = new PersonNode();
findAge = scnr.nextInt();
foundFirst = personList.findFirst(findAge);
if (foundFirst != null) {
replaceName = scnr.next();
foundFirst.setName(replaceName);
System.out.println();
System.out.println("List after replacing the first occurrence of " + findAge + ":");
personList.printPersonList();
}
else {
System.out.println("Age value not found in the list.");
}
  
foundLast = new PersonNode();
findAge = scnr.nextInt();
foundLast = personList.findLast(findAge);
if (foundLast != null) {
replaceName = scnr.next();
foundLast.setName(replaceName);
System.out.println();
System.out.println("List after replacing the last occurrence of " + findAge + ":");
personList.printPersonList();
}
else {
System.out.println("Age value not found in the list.");
}
}
}

PersonList.java

public class PersonList {
// Linked list nodes
public PersonNode headNode;
public PersonNode tailNode;

public PersonList() {
// Front of nodes list   
headNode = null;
tailNode = null;
}

// append
public void append(PersonNode newNode) {
if (headNode == null) { // List empty
headNode = newNode;
tailNode = newNode;
}
else {
tailNode.nextNode = newNode;
newNode.prevNode = tailNode;
tailNode = newNode;
}
}

// prepend   
public void prepend(PersonNode newNode) {
if (headNode == null) { // list empty
headNode = newNode;
tailNode = newNode;
}
else {
newNode.nextNode = headNode;
headNode.prevNode = newNode;
headNode = newNode;
}
}
// insertAfter   
public void insertAfter(PersonNode curNode, PersonNode newNode) {
PersonNode sucNode;
if (headNode == null) { // List empty
headNode = newNode;
tailNode = newNode;
}
else if (curNode == tailNode) { // Insert after tail   
tailNode.nextNode = newNode;
newNode.prevNode = tailNode;
tailNode = newNode;
}
else {
sucNode = curNode.nextNode;
newNode.nextNode = sucNode;
newNode.prevNode = curNode;
curNode.nextNode = newNode;
sucNode.prevNode = newNode;
}
}

// TODO: Write findFirst() method
// Find the node with the first occurrence of the age
// Start with the headNode and traverse forward
public PersonNode findFirst(int ageValue) {

}

// TODO: Write findLast() method   
// Find the node with the last occurrence of the age   
// Start with the tailNode and traverse backward
public PersonNode findLast(int ageValue) {
  
}

public void printPersonList() {
PersonNode curNode;

curNode = headNode;
while (curNode != null) {
curNode.printNodeData();
curNode = curNode.nextNode;
}
}
}

PersonNode.java

public class PersonNode {
private String name;
private int age;
public PersonNode prevNode; // Reference to the previous node
public PersonNode nextNode; // Reference to the next node

public PersonNode() {
name = "";
age = 0;
prevNode = null;
nextNode = null;
}

// Constructor   
public PersonNode(String nameInit, int ageInit) {
this.name = nameInit;
this.age = ageInit;
this.prevNode = null;
this.nextNode = null;
}

// Constructor   
public PersonNode(String nameInit, int ageInit, PersonNode prevNode, PersonNode newNextNode) {
this.name = nameInit;
this.age = ageInit;
this.prevNode = prevNode;
this.nextNode = newNextNode;
}

public String getName() {
return this.name;
}

public long getAge() {
return this.age;
}

public void setName(String userName) {
this.name = userName;
}

public void setAge(int userAge) {
this.age = userAge;
}

public void printNodeData() {
System.out.println(this.name + ", " + this.age);
}
}

Question

Objective:

The objective of this lab exercise is to give you practice in programming with one of Python’s most widely used “container” data types -- the List (commonly called an “Array” in most other programming languages). More specifically you will demonstrate how to:

1. Declare list objects
2. Access a list for storing (i.e., writing) into a cell (a.k.a., element or component) and retrieving (i.e., reading) a value from a list cell/element/component
3. Iterate through a list looking for specific values using a for…in loop repetition construct
4. Pass an entire list argument to a function
5. Process a list parameter received by a function

Discussion:     

For this exercise you will be simulating a Weather Station responsible for recording hourly temperatures and reporting on certain characteristics (e.g., average temperature) from your recordings. You will also be expanding on your experience in creating functions and passing them more complex parameters (i.e., complete list arguments – sometimes empty and sometimes full).

Specifications:

DDI&T a Python program to input, store, and process hourly temperatures for each hour of the day (i.e., 24 temperatures). Your program should be divided logically into the following parts:

1. In function main() declare an empty List container:

         HourlyTemperatures = []    

2. Pass the empty HourlyTemperatures list to a function,

GetTemperatures(HourlyTemperatures)

         This function must interactively prompt for and input temperatures for each of the 24 hours in a day (0 through 23). For each temperature that is input, verify that its value lies in the range of minus 50 degrees and plus 130 degrees (i.e., validate your input values). If any value is outside the acceptable range, ask the user to re-enter the value until it is within this range before going on to the next temperature (HINT: use a nested loop (e.g., Python’s equivalent to a do-while loop) that exits only when a value in the specified range has been entered). Store each validated temperature in its corresponding element of the list container passed as a parameter to the function (Hint: Look at the ‘append(…)’ function that can be called on a list container).

3. Next pass the filled list container to a function,

ComputeAverageTemp(HourlyTemperatures)

         This function computes the average temperature of all the temperatures in the list and returns this average to the calling function.

4. Finally, pass the filled list container and the computed average temperature to another function,

                  DisplayTemperatures(HourlyTemperatures, AverageTemp)

         which displays the values of your temperature list in a columnar format followed by the values for the high temperature, low temperature, and average temperature for the day.  NOTE: If you want to create separate function(s) to find and return the high and low temperature values, then feel free to do so!

The resulting output should look something like this:

Hour                          Temperature

00:00                                42

01:00                                42

. . . . .                                . . . // Your program output must include all of these too!

22:00                                46

23:00                                48

High Temperature:          68

Low Temperature:           42

Average Temperature:    57.4

5.      Since you have several created functions to perform each of the major steps of your solution, your main(): function should be quite simple. The pseudo code for main() might look something like this:

                  main()

                       #declare any necessary variable(s) and HourlyTemperatures list

                       while user-wants-to-process-another-days’-worth-of-temperatures

                           call GetTemperatures(HourlyTemperatures)

                                 call ComputeAverageTemp(HourlyTemperatures)

                                 call DisplayTemperatures(HourlyTemperatures, AverageTemperature)

                                 ask if user want to process another days’ worth of temperatures

6.      Test your program with at least two (2) different sets of temperatures. Make sure you enter values to adequately test your temperature-validation code (e.g., temperatures below –50 and above +130 degrees).

Deliverable(s):

Your deliverable should be a Word document with screenshots showing the sample code you have created, and discuss the issues that you had for this project related to AWS and/or Python IDE and how you solved them.

Turn in the properly documented source listing of your program and complete outputs from at least TWO (2) test “runs”. Additionally, turn in screen captures of some of your interactive inputs demonstrating that your program properly detects invalid inputs and prompts the user to re-enter the temperature(s).

In this assignment you are to utilize the Node data structure provided on Blackboard.
In this assignment you are to write a main program that implements two methods and a main
method as their driver. So, only main and two methods with it.

Implementation Details:
Method 1:
^^^^^^^^^
Parameters and return type:
Takes as parameters an array of integers, the size of the array of integer (.length is acceptable also)
and it should return a Node that is supposed to represent the head of a linked list.

Note: You may also choose to make it a void method and pass the head of the linked list as a parameter,
if that's easier for you. You have the choice here.

Method Logic:
The method is supposed to create a linked list represented by its head and populate it with the
numbers stored in the array by placing the even numbers in the array first, followed by the odd
numbers. You may not change the order of the numbers inside of the array, the order must remain
the same as it was read from input.

Example: Assume the array is: [0,1, 4, 6, 7, 9, 2, 10, 11, 14, 13, 19, 20]

The linked list should be 20->14->10->2->6->4->0->1->7->9->11-13->19

So return back from the function the head of this linked list.

Method 2:
^^^^^^^^^
Parameters and return type:
This method should take as a parameter the linked list generated in method 1 represented by
its head.

Method logic:
The method should start by reading in one integer from standard input, and based on that
integer, it needs to shift the linked list by that many positions. Keep in mind that you need
to do the necessary error checking, the shifting can be between 0 and the size of the linked list - 1.

Example:
Assume the given linked list is: 20->14->10->2->6->4->0->1->7->9->11-13->19

You read in an integer: You input the number 3.
The linked list should look like: 2->6->4->0->1->7->9->11-13->19->20->14->10

If you read in a 6:
The linked list should look like: 0->1->7->9->11-13->19->20->14->10->2->6->4

If you read in a 13 The method should print an error asking you to enter a number between 0-12.

The main program:
^^^^^^^^^^^^^^^^^
1. Your program should run and ask the user to input the size of an array of integers. Once that's
done, the program should read these integers and store them into an array.

2. Once the array has been populated and its size is known, then you need to call method 1 defined
above. The result should be a head pointer of a linked list.

At this point you declare a cursor method and go through the linked list and print it to the screen.
Based on the above example: 20 14 10 2 6 4 0 1 7 9 11 13 19.

3. Call method 2

4. Print the linked list resulting from calling method 2. The rotated linked list.

- method 1 hints
The following should happen after reading an array a of size n Keep in mind that this is closer to pseudocode, so you need to fix it to compile, it's pretty close to what you need to do, but you need to adjust the code to work with the Node data structure. I am talking about private vs. public data members and the use of getters and setters.
Also the following is assuming a dummy node.
Node head = new Node(); Node cursor = head;
for(i = 0; i < n; i++ ) {
int x = a[i]; // this is the number we're working with.
if(x % 2 == 0) // the number is even.
{
// this will insert the even numbers in the reverse order of how they are in the array.
head.next = new Node(x, head.next);
}else{
cursor.next = new Node(x, null);
cursor = cursor.next
}
}
return head; // this will return the entire list represented by its head

- Method 2 hints
public static void rotateList(Node head){

// read in the number n to rotate by
// then do the rotation code by manipulating the head and where it's

// pointing and where the new end of the list is now.
}

In this assignment you are to utilize the Node data structure provided on Blackboard.
In this assignment you are to write a main program that implements two methods and a main
method as their driver. So, only main and two methods with it.

Implementation Details:
Method 1:
^^^^^^^^^
Parameters and return type:
Takes as parameters an array of integers, the size of the array of integer (.length is acceptable also)
and it should return a Node that is supposed to represent the head of a linked list.

Note: You may also choose to make it a void method and pass the head of the linked list as a parameter,
if that's easier for you. You have the choice here.

Method Logic:
The method is supposed to create a linked list represented by its head and populate it with the
numbers stored in the array by placing the even numbers in the array first, followed by the odd
numbers. You may not change the order of the numbers inside of the array, the order must remain
the same as it was read from input.

Example: Assume the array is: [0,1, 4, 6, 7, 9, 2, 10, 11, 14, 13, 19, 20]

The linked list should be 20->14->10->2->6->4->0->1->7->9->11-13->19

So return back from the function the head of this linked list.

Method 2:
^^^^^^^^^
Parameters and return type:
This method should take as a parameter the linked list generated in method 1 represented by
its head.

Method logic:
The method should start by reading in one integer from standard input, and based on that
integer, it needs to shift the linked list by that many positions. Keep in mind that you need
to do the necessary error checking, the shifting can be between 0 and the size of the linked list - 1.

Example:
Assume the given linked list is: 20->14->10->2->6->4->0->1->7->9->11-13->19

You read in an integer: You input the number 3.
The linked list should look like: 2->6->4->0->1->7->9->11-13->19->20->14->10

If you read in a 6:
The linked list should look like: 0->1->7->9->11-13->19->20->14->10->2->6->4

If you read in a 13 The method should print an error asking you to enter a number between 0-12.

The main program:
^^^^^^^^^^^^^^^^^
1. Your program should run and ask the user to input the size of an array of integers. Once that's
done, the program should read these integers and store them into an array.

2. Once the array has been populated and its size is known, then you need to call method 1 defined
above. The result should be a head pointer of a linked list.

At this point you declare a cursor method and go through the linked list and print it to the screen.
Based on the above example: 20 14 10 2 6 4 0 1 7 9 11 13 19.

3. Call method 2

4. Print the linked list resulting from calling method 2. The rotated linked list.

- method 1 hints
The following should happen after reading an array a of size n Keep in mind that this is closer to pseudocode, so you need to fix it to compile, it's pretty close to what you need to do, but you need to adjust the code to work with the Node data structure. I am talking about private vs. public data members and the use of getters and setters.
Also the following is assuming a dummy node.
Node head = new Node(); Node cursor = head;
for(i = 0; i < n; i++ ) {
int x = a[i]; // this is the number we're working with.
if(x % 2 == 0) // the number is even.
{
// this will insert the even numbers in the reverse order of how they are in the array.
head.next = new Node(x, head.next);
}else{
cursor.next = new Node(x, null);
cursor = cursor.next
}
}
return head; // this will return the entire list represented by its head

- Method 2 hints
public static void rotateList(Node head){

// read in the number n to rotate by
// then do the rotation code by manipulating the head and where it's

// pointing and where the new end of the list is now.
}

A circular conducting loop is held fixed in a uniform magnetic field that varies in time according to B(t) = B exp(-at) where t is in s, a is in s^-1 and B is the field strength in T at t = 0. At t = 0, the emf induced in the loop is 0.0614 V. At t = 2.74 s, the emf is 0.0197V. Find a.

L₁

+ Ri₂ + Ri₃ = E(t)

L₂

+ Ri₂ + Ri₃ = E(t).

Solve the system in part (a) if

R = 10 Ω, L₁ = 0.01 h, L₂ = 0.05 h, E = 200 V, i₂(0) = 0, and i₃(0) = 0.

A particle is moving according to the given data

v(t)=t^2 - sqrt(t), x(0) = 0, 0 ≤ t ≤ 4.

• Find x(t), the position of the particle at time t.
• For what values of t is the particle moving to the left? To the right?

• Find the displacement of the particle.
• Find the total distance covered by the particle.