Problem 2 Start with the file LList2.java and add the following methods: 4.Add t
ID: 3803919 • Letter: P
Question
Problem 2
Start with the file LList2.java and add the following methods:
4.Add the method
int getLastIndex(T item)
that returns the index of the last entry which is equal to item. If item is not found, it returns -1. (15 points)
5.Add the method
int removeEvery(T item) that removes all occurrences of item and returns the number of removed items. (15 points)
6.Add the method
boolean equals(Object other) method that returns true when the contents of 2 LList2 objects are the same (the two objects in this case are the current object and other). Note that 2 LList2 objects are the same if they have the same number of items and each item in one object exists in the same location in the other object (15 points)
7.Provide a second implementation of the method
boolean contains2(T anEntry)
that calls a private recursive method
private boolean contains(T anEntry, Node startNode)
that returns whether the list that starts at startNode contains the entry anEntry. (10 points)
LList2.java
/**
A class that implements the ADT list by using a chain of nodes.
The chain has both a head reference and a tail reference.
@author Frank M. Carrano
@version 3.0
*/
public class LList2<T> implements ListInterface<T>
{
private Node firstNode; // head reference to first node
private Node lastNode; // tail reference to last node
private int numberOfEntries;
public LList2()
{
clear();
} // end default constructor
public final void clear() // NOTICE clear is not final in interface and that is OK
{
firstNode = null;
lastNode = null;
numberOfEntries = 0;
} // end clear
public void add(T newEntry) // OutOfMemoryError possible
{
Node newNode = new Node(newEntry); // create new node
if (isEmpty())
firstNode = newNode;
else
lastNode.setNextNode(newNode);
lastNode = newNode;
numberOfEntries++;
} // end add
public boolean add(int newPosition, T newEntry) // OutOfMemoryError possible
{
boolean isSuccessful = true;
if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1))
{
Node newNode = new Node(newEntry);
if (isEmpty())
{
firstNode = newNode;
lastNode = newNode;
}
else if (newPosition == 1)
{
newNode.setNextNode(firstNode);
firstNode = newNode;
}
else if (newPosition == numberOfEntries + 1)
{
lastNode.setNextNode(newNode);
lastNode = newNode;
}
else
{
Node nodeBefore = getNodeAt(newPosition - 1);
Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);
} // end if
numberOfEntries++;
}
else
isSuccessful = false;
return isSuccessful;
} // end add
public T remove(int givenPosition)
{
T result = null; // return value
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{
assert !isEmpty();
if (givenPosition == 1) // case 1: remove first entry
{
result = firstNode.getData(); // save entry to be removed
firstNode = firstNode.getNextNode();
if (numberOfEntries == 1)
lastNode = null; // solitary entry was removed
}
else // case 2: givenPosition > 1
{
Node nodeBefore = getNodeAt(givenPosition - 1);
Node nodeToRemove = nodeBefore.getNextNode();
Node nodeAfter = nodeToRemove.getNextNode();
nodeBefore.setNextNode(nodeAfter); // disconnect the node to be removed
result = nodeToRemove.getData(); // save entry to be removed
if (givenPosition == numberOfEntries)
lastNode = nodeBefore; // last node was removed
} // end if
numberOfEntries--;
} // end if
return result; // return removed entry, or
// null if operation fails
} // end remove
public boolean replace(int givenPosition, T newEntry)
{
boolean isSuccessful = true;
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{
assert !isEmpty();
Node desiredNode = getNodeAt(givenPosition);
desiredNode.setData(newEntry);
}
else
isSuccessful = false;
return isSuccessful;
} // end replace
public T getEntry(int givenPosition)
{
T result = null; // result to return
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{
assert !isEmpty();
result = getNodeAt(givenPosition).getData();
} // end if
return result;
} // end getEntry
public boolean contains(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.getData()))
found = true;
else
currentNode = currentNode.getNextNode();
} // end while
return found;
} // end contains
public int getLength()
{
return numberOfEntries;
} // end getLength
public boolean isEmpty()
{
boolean result;
if (numberOfEntries == 0) // or getLength() == 0
{
assert firstNode == null;
result = true;
}
else
{
assert firstNode != null;
result = false;
} // end if
return result;
} // end isEmpty
public T[] toArray()
{
// the cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries]; // warning: [unchecked] unchecked cast
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.getData();
currentNode = currentNode.getNextNode();
index++;
} // end while
return result;
} // end toArray
// Returns a reference to the node at a given position.
// Precondition: List is not empty; 1 <= givenPosition <= numberOfEntries.
private Node getNodeAt(int givenPosition)
{
assert (firstNode != null) && (1 <= givenPosition) && (givenPosition <= numberOfEntries);
Node currentNode = firstNode;
if (givenPosition == numberOfEntries)
currentNode = lastNode;
else if (givenPosition > 1) // traverse the chain to locate the desired node
{
for (int counter = 1; counter < givenPosition; counter++)
currentNode = currentNode.getNextNode();
} // end if
assert currentNode != null;
return currentNode;
} // end getNodeAt
// Lab 3
// Problem 1
int getIndex(T item) {
return 0;
}
// Problem 2
int removeEvery(T item) {
return 0;
}
// Problem 3
boolean equals(Object other) {
return false;
}
//Problem 4
boolean contains2(T anEntry) {
return false;
}
private boolean contains(T anEntry, Node startNode) {
return false;
}
private class Node
{
private T data; // data portion
private Node next; // next to next node
private Node(T dataPortion)// PRIVATE or PUBLIC is OK
{
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node nextNode)// PRIVATE or PUBLIC is OK
{
data = dataPortion;
next = nextNode;
} // end constructor
private T getData()
{
return data;
} // end getData
private void setData(T newData)
{
data = newData;
} // end setData
private Node getNextNode()
{
return next;
} // end getNextNode
private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
} // end LList2
ListInterface
/**
An interface for the ADT list.
Entries in the list have positions that begin with 1.
@author Frank M. Carrano
@version 3.0
*/
public interface ListInterface<T>
{
/** Adds a new entry to the end of this list.
Entries currently in the list are unaffected.
The listÕs size is increased by 1.
@param newEntry the object to be added as a new entry */
public void add(T newEntry);
/** Adds a new entry at a specified position within this list.
Entries originally at and above the specified position
are at the next higher position within the list.
The listÕs size is increased by 1.
@param newPosition an integer that specifies the desired
position of the new entry
@param newEntry the object to be added as a new entry
@return true if the addition is successful, or
false if newPosition < 1, or newPosition > getLength() + 1 */
public boolean add(int newPosition, T newEntry);
/** Removes the entry at a given position from this list.
Entries originally at positions higher than the given
position are at the next lower position within the list,
and the listÕs size is decreased by 1.
@param givenPosition an integer that indicates the position of
the entry to be removed
@return a reference to the removed entry or null, if either
the list was empty, givenPosition < 1, or
givenPosition > getLength() */
public T remove(int givenPosition);
/** Removes all entries from this list. */
public void clear();
/** Replaces the entry at a given position in this list.
@param givenPosition an integer that indicates the position of
the entry to be replaced
@param newEntry the object that will replace the entry at the
position givenPosition
@return true if the replacement occurs, or false if either the
list is empty, givenPosition < 1, or
givenPosition > getLength() */
public boolean replace(int givenPosition, T newEntry);
/** Retrieves the entry at a given position in this list.
@param givenPosition an integer that indicates the position of
the desired entry
@return a reference to the indicated entry or null, if either
the list is empty, givenPosition < 1, or
givenPosition > getLength() */
public T getEntry(int givenPosition);
/** Sees whether this list contains a given entry.
@param anEntry the object that is the desired entry
@return true if the list contains anEntry, or false if not */
public boolean contains(T anEntry);
/** Gets the length of this list.
@return the integer number of entries currently in the list */
public int getLength();
/** Sees whether this list is empty.
@return true if the list is empty, or false if not */
public boolean isEmpty();
/** Retrieves all entries that are in this list in the order in which
they occur in the list. */
public T[] toArray();
} // end ListInterface
ListClient
public class ListClient
{
public static void main(String[] args)
{
testList();
} // end main
public static void testList()
{
ListInterface<String> runnerList = new AList<String>();
// runnerList has only methods in ListInterface
runnerList.add("16"); // winner
runnerList.add(" 4"); // second place
runnerList.add("33"); // third place
runnerList.add("27"); // fourth place
displayList(runnerList);
} // end testList
public static void displayList(ListInterface<String> list)
{
int numberOfEntries = list.getLength();
System.out.println("The list contains " + numberOfEntries +
" entries, as follows:");
for (int position = 1; position <= numberOfEntries; position++)
System.out.println(list.getEntry(position) +
" is entry " + position);
System.out.println();
} // end displayList
} // end ListClient
Explanation / Answer
public class Llist2 {
private Node l = new Node(0);
private int len = 0;
public void add(int n) {
Node tmp = new Node(n);
tmp.setNext(l.getNext());
l.setNext(tmp);
len++;
}
public String toString() {
String s = "";
Node tmp;
for (tmp = l.getNext() ; tmp != null ; tmp = tmp.getNext()) {
s = s + tmp.getData() + " --> ";
}
s = s + "null";
return s;
}
public int get(int n) {
Node tmp = l;
if (n >= len) {
return -1;
}
for (int i = 0 ; i <= n ; i++) {
tmp = tmp.getNext();
}
return tmp.getData();
}
public void add(int n, int s) {
Node newEl = new Node(s);
Node curnode = l.getNext();
if (n > len) {
throw new IndexOutOfBoundsException();
}
for (int i = 0 ; i < n - 1 ; i++) {
curnode = curnode.getNext();
}
newEl.setNext(curnode.getNext());
curnode.setNext(newEl);
len++;
}
public int length() {
return len;
}
public int remove(int n) {
if (n >= len || n < 0) {
throw new IndexOutOfBoundsException();
}
Node curnode = l;
for (int i = 0 ; i < n - 1 ; i++) {
curnode = curnode.getNext();
}
int removed = curnode.getNext().getData();
curnode.setNext(curnode.getNext().getNext());
return removed;
}
}
public class Llist2 {
private Node l = new Node(0);
private int len = 0;
public void add(int n) {
Node tmp = new Node(n);
tmp.setNext(l.getNext());
l.setNext(tmp);
len++;
}
public String toString() {
String s = "";
Node tmp;
for (tmp = l.getNext() ; tmp != null ; tmp = tmp.getNext()) {
s = s + tmp.getData() + " --> ";
}
s = s + "null";
return s;
}
public int get(int n) {
Node tmp = l;
if (n >= len) {
return -1;
}
for (int i = 0 ; i <= n ; i++) {
tmp = tmp.getNext();
}
return tmp.getData();
}
public void add(int n, int s) {
Node newEl = new Node(s);
Node curnode = l.getNext();
if (n > len) {
throw new IndexOutOfBoundsException();
}
for (int i = 0 ; i < n - 1 ; i++) {
curnode = curnode.getNext();
}
newEl.setNext(curnode.getNext());
curnode.setNext(newEl);
len++;
}
public int length() {
return len;
}
public int remove(int n) {
if (n >= len || n < 0) {
throw new IndexOutOfBoundsException();
}
Node curnode = l;
for (int i = 0 ; i < n - 1 ; i++) {
curnode = curnode.getNext();
}
int removed = curnode.getNext().getData();
curnode.setNext(curnode.getNext().getNext());
return removed;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.