Question

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);
}
}

Answer 1

Screenshot

Program

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);
}
}

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) {
   PersonNode curNode;

   curNode = headNode;
   while (curNode != null) {
       if(curNode.getAge()==ageValue) {
           return curNode;
       }
       curNode = curNode.nextNode;
   }
   return null;
}

// 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) {
   PersonNode curNode;

   curNode =tailNode;
   while (curNode != null) {
       if(curNode.getAge()==ageValue) {
           return curNode;
       }
       curNode = curNode.prevNode;
   }
   return null;
}

public void printPersonList() {
PersonNode curNode;

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

FindOcurrence.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.");
}
}
}

-----------------------------------------------------------

Output

Alex 23
Tom 41
Michelle 34
Vicky 24
-1
List before replacing:
Alex, 23
Tom, 41
Michelle, 34
Vicky, 24
23
Connor

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

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