Start with the file LList2.java and add the following methods: Add the method: i
ID: 3726891 • Letter: S
Question
Start with the file LList2.java and add the following methods:
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.
Add the method:
int removeEvery(T item) that removes all occurrences of item and returns the number of removed items.
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
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.
//LList2.java
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
Explanation / Answer
Please find the code below with detailed inline comments.
CODE
============================
// LList2.java
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
/**
*
* @param item
* @return returns the index of the last entry which is equal to item. If item is not found, it returns -1.
*/
int getLastIndex(T item) {
Node currentNode = firstNode; // initialize current node to firstNode
int i = 0, lastIndex = -1;
// loop until currentNode is null
while (currentNode != null) {
// if the current node is same as item, update lastIndex to current index
if(currentNode.data == item)
lastIndex = i;
currentNode = currentNode.getNextNode();
i ++;
} // end while
// return lastIndex
return lastIndex;
}
// Problem 2
/**
*
* @param item
* removes all occurrences of item
* @return returns the number of removed items.
*/
int removeEvery(T item) {
// Store first node
Node temp = firstNode, prev = null;
int count = 0;
// If first node itself holds the key or multiple occurrences of key
while (temp != null && temp.data == item)
{
count ++; // increment count
firstNode = temp.next; // Changed first node
temp = firstNode; // Change temp
}
// Delete occurrences other than head
while (temp != null)
{
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev.next'
while (temp != null && temp.data != item)
{
prev = temp;
temp = temp.next;
}
// If key was not present in linked list
if (temp == null)
return count;
// Unlink the node from linked list
prev.next = temp.next;
//Update Temp for next iteration of outer loop
temp = prev.next;
count ++; // increment count
}
// return count
return count;
}
// Problem 3
/**
*
* @param other
* @return returns true when the contents of 2 LList2 objects are the same
* (the two objects in this case are the current object and other)
*/
boolean equals(LList2<T> other) {
// return false if the two lists are not of same size
if (this.numberOfEntries != other.numberOfEntries)
return false;
Node curr = this.firstNode, listNode = other.firstNode;
// check data of both lists node by node
while(curr != null) {
// return false if they don't match
if (curr.data != listNode.data)
return false;
curr = curr.next;
listNode = listNode.next;
}
// else, return true
return true;
}
//Problem 4
boolean contains2(T anEntry) {
return contains(anEntry, firstNode);
}
/**
*
* @param anEntry
* @param startNode
* @return returns whether the list that starts at startNode contains the entry anEntry.
*/
private boolean contains(T anEntry, Node startNode) {
if(startNode == null)
return false;
if(startNode.data == anEntry)
return true;
return contains(anEntry, startNode.getNextNode());
}
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.