JAVA I have already written the four new methods and added to the LinkedIntList.
ID: 3763612 • Letter: J
Question
JAVA
I have already written the four new methods and added to the LinkedIntList.java. I just don't know how to Write the test class to compile my methods.
#1) Exercise 16.4 p.999
Write a method lastIndexOf that accepts an integer value as a parameter and that returns the index in the list of the last occurrence of that value, or -1 if the value is not found in the list. For example, if a variable list stores the following sequence of values, then the call of list.lastIndexOf(18) should return 6 because that is the index of the last occurrence of 18:
[1, 18, 2, 7, 18, 39, 18, 40]
If the call had instead been list.lastIndexOf(3), the method would return -1 because 3 does not appear in the list. You may not call any other methods of the class to solve this problem.
Assume that you are adding this method to the LinkedIntList class as defined below:
public class LinkedIntList {
private ListNode front; // null for an empty list
...
}
#2) Exercise 16.5 p.999
Write a method countDuplicates that returns the number of duplicates in a sorted list. The list will be in sorted order, so all of the duplicates will be grouped together. For example, if a variable list stores the sequence of values below, the call of list.countDuplicates() should return 7 because there are 2 duplicates of 1, 1 duplicate of 3, 1 duplicate of 15, 2 duplicates of 23 and 1 duplicate of 40:
[1, 1, 1, 3, 3, 6, 9, 15, 15, 23, 23, 23, 40, 40]
Remember that you may assume that the list is in sorted order, so any duplicates would occur consecutively.
Assume that you are adding this method to the LinkedIntList class as defined below:
public class LinkedIntList {
private ListNode front; // null for an empty list
...
}
#3) Exercise 16.6 p.999
Write a method hasTwoConsecutive that returns whether or not a list of integers has two adjacent numbers that are consecutive integers (true if such a pair exists and false otherwise). For example, if a variable list stores the following sequence of values, then the call list.hasTwoConsecutive() should return true because the list contains the adjacent numbers (7, 8) which are a pair of consecutive numbers:
[1, 18, 2, 7, 8, 39, 18, 40]
If the list had stored the following sequence of values, then the method should return false:
[1, 18, 17, 2, 7, 39, 18, 40, 8]
This sequence contains some pairs of numbers that could represent consecutive integers (e.g., 1 and 2, 7 and 8, 39 and 40), but those pairs of numbers are not adjacent in the sequence. The list also has a pair of adjacent numbers (18, 17) that are not in the right order to be considered consecutive. You may not make any assumptions about how many elements are in the list.
Assume that you are adding this method to the LinkedIntList class as defined below:
public class LinkedIntList {
private ListNode front; // null for an empty list
...
}
#4) Exercise 16.7 p.999
Write a method deleteBack that deletes the last value (the value at the back of the list) and returns the deleted value. If the list is empty, your method should throw a NoSuchElementException.
Assume that you are adding this method to the LinkedIntList class as defined below:
public class LinkedIntList {
private ListNode front; // null for an empty list
...
}
import java.awt.List;
import java.util.ArrayList;
import java.util.NoSuchElementException;
// A LinkedIntList object can be used to store a list of integers.
public class LinkedIntList {
private ListNode front; // node holding first value in list (null if empty)
private String name = "front"; // string to print for front of list
// Constructs an empty list.
public LinkedIntList() {
front = null;
}
// Constructs a list containing the given elements.
// For quick initialization via Practice-It test cases.
public LinkedIntList(int... elements) {
this("front", elements);
}
public LinkedIntList(String name, int... elements) {
this.name = name;
if (elements.length > 0) {
front = new ListNode(elements[0]);
ListNode current = front;
for (int i = 1; i < elements.length; i++) {
current.next = new ListNode(elements[i]);
current = current.next;
}
}
}
// Constructs a list containing the given front node.
// For quick initialization via Practice-It ListNode test cases.
private LinkedIntList(String name, ListNode front) {
this.name = name;
this.front = front;
}
// Appends the given value to the end of the list.
public void add(int value) {
if (front == null) {
front = new ListNode(value, front);
} else {
ListNode current = front;
while (current.next != null) {
current = current.next;
}
current.next = new ListNode(value);
}
}
// Inserts the given value at the given index in the list.
// Precondition: 0 <= index <= size
public void add(int index, int value) {
if (index == 0) {
front = new ListNode(value, front);
} else {
ListNode current = front;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = new ListNode(value, current.next);
}
}
public boolean equals(Object o) {
if (o instanceof LinkedIntList) {
LinkedIntList other = (LinkedIntList) o;
return toString().equals(other.toString()); // hackish
} else {
return false;
}
}
// Returns the integer at the given index in the list.
// Precondition: 0 <= index < size
public int get(int index) {
ListNode current = front;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
// Removes the value at the given index from the list.
// Precondition: 0 <= index < size
public void remove(int index) {
if (index == 0) {
front = front.next;
} else {
ListNode current = front;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
}
}
// Returns the number of elements in the list.
public int size() {
int count = 0;
ListNode current = front;
while (current != null) {
count++;
current = current.next;
}
return count;
}
// Returns a text representation of the list, giving
// indications as to the nodes and link structure of the list.
// Detects student bugs where the student has inserted a cycle
// into the list.
public String toFormattedString() {
ListNode.clearCycleData();
String result = this.name;
ListNode current = front;
boolean cycle = false;
while (current != null) {
result += " -> [" + current.data + "]";
if (current.cycle) {
result += " (cycle!)";
cycle = true;
break;
}
current = current.__gotoNext();
}
if (!cycle) {
result += " /";
}
return result;
}
// Returns a text representation of the list.
public String toString() {
return toFormattedString();
}
// Returns a shorter, more "java.util.LinkedList"-like text representation of the list.
public String toStringShort() {
ListNode.clearCycleData();
String result = "[";
ListNode current = front;
boolean cycle = false;
while (current != null) {
if (result.length() > 1) {
result += ", ";
}
result += current.data;
if (current.cycle) {
result += " (cycle!)";
cycle = true;
break;
}
current = current.__gotoNext();
}
if (!cycle) {
result += "]";
}
return result;
}
// ListNode is a class for storing a single node of a linked list. This
// node class is for a list of integer values.
// Most of the icky code is related to the task of figuring out
// if the student has accidentally created a cycle by pointing a later part of the list back to an earlier part.
public static class ListNode {
private static final ArrayList ALL_NODES = new ArrayList();
public static void clearCycleData() {
for (ListNode node : ALL_NODES) {
node.visited = false;
node.cycle = false;
}
}
public int data; // data stored in this node
public ListNode next; // link to next node in the list
public boolean visited; // has this node been seen yet?
public boolean cycle; // is there a cycle at this node?
// post: constructs a node with data 0 and null link
public ListNode() {
this(0, null);
}
// post: constructs a node with given data and null link
public ListNode(int data) {
this(data, null);
}
// post: constructs a node with given data and given link
public ListNode(int data, ListNode next) {
ALL_NODES.add(this);
this.data = data;
this.next = next;
this.visited = false;
this.cycle = false;
}
public ListNode __gotoNext() {
return __gotoNext(true);
}
public ListNode __gotoNext(boolean checkForCycle) {
if (checkForCycle) {
visited = true;
if (next != null) {
if (next.visited) {
// throw new IllegalStateException("cycle detected in list");
next.cycle = true;
}
next.visited = true;
}
}
return next;
}
}
public int lastIndexOf (int value){
int count = -1;
int index = 0;
ListNode current = front;
while (current != null){
if (current.data == value){
count = index;
}
index = index + 1;
current = current.next;
}
if (count >= 0){
return count;
}else{
return -1;
}
}
public int countDuplicates(){
int count = 0;
if (front == null){
return count;
}else {
ListNode prev = front;
ListNode current = front.next;
while (current != null){
if (prev.data == current.data){
count = count +1;
}
prev = current;
current = current.next;
}
return count;
}
}
public boolean hasTwoConsecutive(){
if (front == null) {
return false;
}else{
ListNode prev = front;
ListNode current = front.next;
while(current != null){
if (prev.data == current.data -1){
return true;
}
prev = current;
current = current.next;
}
return false;
}
}
public int deleteBack(){
if(front==null){
throw new NoSuchElementException();
}else{
if(front.next == null){
int value = front.data;
front = null;
return value;
}
ListNode current = front.next;
ListNode prev= front;
while(current.next!=null){
prev = current;
current = current.next;
}
int value = current.data;
prev.next = null;
return value;
}
}
}
Explanation / Answer
2)
public int countDuplicates()
{
int cnt = 0;
if (front == null)
return 0;
ListNode current = front;
while(current.next != null) {
if (current.data == current.next.data)
cnt++;
current = current.next;
}
return cnt;
}
3)
public boolean hasTwoConsecutive()
{
if (front == null)
return false;
ListNode current = front;
while (current.next != null) {
if (current.data + 1 == current.next.data)
return true;
current = current.next;
}
return false;
}
4)
public class LinkedIntList
{
private ListNode front;
private String name = "front";
public LinkedIntList() {
front = null;
}
public LinkedIntList(int elements) {
this("front", elements);
}
public LinkedIntList(String name, int elements) {
this.name = name;
if (elements.length > 0) {
front = new ListNode(elements[0]);
ListNode current = front;
for (int i = 1; i < elements.length; i++) {
current.next = new ListNode(elements[i]);
current = current.next;
}
}
}
private LinkedIntList(String name, ListNode front) {
this.name = name;
this.front = front;
}
public void add(int value) {
if (front == null) {
front = new ListNode(value, front);
} else {
ListNode current = front;
while (current.next != null) {
current = current.next;
}
current.next = new ListNode(value);
}
}
public void add(int index, int value) {
if (index == 0) {
front = new ListNode(value, front);
} else {
ListNode current = front;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = new ListNode(value, current.next);
}
}
public boolean equals(Object o) {
if (o instanceof LinkedIntList) {
LinkedIntList other = (LinkedIntList) o;
return toString().equals(other.toString()); // hackish
} else {
return false;
}
}
public int get(int index) {
ListNode current = front;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
public void remove(int index)
{
if (index == 0) {
front = front.next;
} else {
ListNode current = front;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
}
}
public int size()
{
int count = 0;
ListNode current = front;
while (current != null) {
count++;
current = current.next;
}
return count;
}
public String toFormattedString()
{
ListNode.clearCycleData();
String result = this.name;
ListNode current = front;
boolean cycle = false;
while (current != null) {
result += " -> [" + current.data + "]";
if (current.cycle) {
result += " (cycle!)";
cycle = true;
break;
}
current = current.__gotoNext();
}
if (!cycle)
{
result += " /";
}
return result;
}
public String toString()
{
return toFormattedString();
}
public static class ListNode
{
private static final List<ListNode> ALL_NODES = new ArrayList<ListNode>();
public static void clearCycleData()
{
for (ListNode node : ALL_NODES)
{
node.visited = false;
node.cycle = false;
}
}
public int data;
public ListNode next;
public boolean visited;
public boolean cycle;
public ListNode()
{
this(0, null);
}
public ListNode(int data)
{
this(data, null);
}
public ListNode(int data, ListNode next)
{
ALL_NODES.add(this);
this.data = data;
this.next = next;
this.visited = false;
this.cycle = false;
}
public ListNode __gotoNext()
{
return __gotoNext(true);
}
public ListNode __gotoNext(boolean checkForCycle) {
if (checkForCycle) {
visited = true;
if (next != null)
{
if (next.visited)
{
next.cycle = true;
}
next.visited = true;
}
}
return next;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.