Java Write a complete display() method for the LList class. LList implements Lis
ID: 3599205 • Letter: J
Question
Java
Write a complete display() method for the LList class.
LList implements ListInterface using linked nodes.
The method prints to the console the list index of each element along with the element.
Be sure to account for all possible times when the method could be invoked.
For full credit, write a method that is efficient (meaning better than O(n2)).
The method header is:
public void display()
For this question, you are writing code at the implementation level. This means you have access to the private instance data variables:
private Node firstNode
private int numberOfEntries
You can assume the following methods are already implemented:
Note that toArray is not listed and should not be used in your solution.
public void add(T newEntry)
public void add(int newPosition, T newEntry)
public boolean isEmpty()
public boolean contains(T anObject)
public T remove(int givenPosition)
public T replace(int givenPosition, T newEntry)
public T getEntry(int givenPosition)
public int getLength()
public void clear()
--------------------------------
LList.java
public class LList<T> implements ListInterface<T> {
private Node firstNode; // Reference to first node of chain
private int numberOfEntries;
public LList() {
initializeDataFields();
} // end default constructor
public void clear() {
initializeDataFields();
} // end clear
public void add(T newEntry) // OutOfMemoryError possible
{
Node newNode = new Node(newEntry);
if (isEmpty())
firstNode = newNode;
else // Add to end of non-empty list
{
Node lastNode = getNodeAt(numberOfEntries);
lastNode.setNextNode(newNode); // Make last node reference new node
} // end if
numberOfEntries++;
} // end add
public void add(int newPosition, T newEntry) {
if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) {
Node newNode = new Node(newEntry);
if (newPosition == 1) // Case 1: add to the beginning
{
newNode.setNextNode(firstNode);
firstNode = newNode;
} else // Case 2: add to some other position
{
Node nodeBefore = getNodeAt(newPosition - 1);
Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);
} // end if
numberOfEntries++;
} else
throw new IndexOutOfBoundsException(
"Illegal position given to add operation.");
} // 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(); // Remove entry
} else // Case 2: Not first entry
{
Node nodeBefore = getNodeAt(givenPosition - 1);
Node nodeToRemove = nodeBefore.getNextNode(); // same as getNodeAt(givenPosition)
result = nodeToRemove.getData(); // Save entry to be removed
Node nodeAfter = nodeToRemove.getNextNode();
nodeBefore.setNextNode(nodeAfter); // Remove entry // same as nodeBefore.setNextNode(noedBefore.getNextNode().getNextNode())
} // end if
numberOfEntries--; // Update count
return result; // Return removed entry
} else
throw new IndexOutOfBoundsException(
"Illegal position given to remove operation.");
} // end remove
public T replace(int givenPosition, T newEntry) {
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
assert !isEmpty();
Node desiredNode = getNodeAt(givenPosition);
T originalEntry = desiredNode.getData();
desiredNode.setData(newEntry);
return originalEntry;
} else
throw new IndexOutOfBoundsException(
"Illegal position given to replace operation.");
} // end replace
public T getEntry(int givenPosition) {
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
assert !isEmpty();
return getNodeAt(givenPosition).getData();
} else
throw new IndexOutOfBoundsException(
"Illegal position given to getEntry operation.");
} // end getEntry
public T[] toArray() {
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Object[numberOfEntries];
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
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 void swap(int firstPosition, int secondPosition) {
if(firstPosition >= 1 && firstPosition <= numberOfEntries &&
secondPosition >=1 && secondPosition <= numberOfEntries) {
Node firstToSwap = getNodeAt(firstPosition);
Node secondToSwap = getNodeAt(secondPosition);
T firstData = firstToSwap.getData();
T secondData = secondToSwap.getData();
T tmp = firstData;
firstToSwap.setData(secondData);
secondToSwap.setData(tmp);
}
}
public LList getAllLessThan(Comparable entry) {
LList smallerList = new LList();
Node currentNode = firstNode;
while(currentNode != null) {
T currentData = currentNode.getData();
if(entry.compareTo(currentData) > 0) {
smallerList.add(currentData);
}
currentNode = currentNode.getNextNode();
}
// this will work! but it's VERY inefficient!!
/*
for(int i=1; i<numberOfEntries; i++) {
T currentData = getEntry(i);
if(entry.compareTo(currentData) > 0) {
smallerList.add(currentData);
}
}
*/
return smallerList;
}
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
// Initializes the class's data fields to indicate an empty list.
private void initializeDataFields() {
firstNode = null;
numberOfEntries = 0;
} // end initializeDataFields
// Returns a reference to the node at a given position.
// Precondition: The chain is not empty;
// 1 <= givenPosition <= numberOfEntries.
private Node getNodeAt(int givenPosition) {
assert !isEmpty() && (1 <= givenPosition)
&& (givenPosition <= numberOfEntries);
Node currentNode = firstNode;
// Traverse the chain to locate the desired node
// (skipped if givenPosition is 1)
for (int counter = 1; counter < givenPosition; counter++)
currentNode = currentNode.getNextNode();
assert currentNode != null;
return currentNode;
} // end getNodeAt
private class Node {
private T data; // Entry in list
private Node next; // Link to next node
private Node(T dataPortion) {
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node nextNode) {
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 LList
Explanation / Answer
Added method is highlighted in BOLD
====================
public class LList<T> implements ListInterface<T> {
private Node firstNode; // Reference to first node of chain
private int numberOfEntries;
public LList() {
initializeDataFields();
} // end default constructor
public void clear() {
initializeDataFields();
} // end clear
public void add(T newEntry) // OutOfMemoryError possible
{
Node newNode = new Node(newEntry);
if (isEmpty())
firstNode = newNode;
else // Add to end of non-empty list
{
Node lastNode = getNodeAt(numberOfEntries);
lastNode.setNextNode(newNode); // Make last node reference new node
} // end if
numberOfEntries++;
} // end add
public void add(int newPosition, T newEntry) {
if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) {
Node newNode = new Node(newEntry);
if (newPosition == 1) // Case 1: add to the beginning
{
newNode.setNextNode(firstNode);
firstNode = newNode;
} else // Case 2: add to some other position
{
Node nodeBefore = getNodeAt(newPosition - 1);
Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);
} // end if
numberOfEntries++;
} else
throw new IndexOutOfBoundsException(
"Illegal position given to add operation.");
} // 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(); // Remove entry
} else // Case 2: Not first entry
{
Node nodeBefore = getNodeAt(givenPosition - 1);
Node nodeToRemove = nodeBefore.getNextNode(); // same as getNodeAt(givenPosition)
result = nodeToRemove.getData(); // Save entry to be removed
Node nodeAfter = nodeToRemove.getNextNode();
nodeBefore.setNextNode(nodeAfter); // Remove entry // same as nodeBefore.setNextNode(noedBefore.getNextNode().getNextNode())
} // end if
numberOfEntries--; // Update count
return result; // Return removed entry
} else
throw new IndexOutOfBoundsException(
"Illegal position given to remove operation.");
} // end remove
public T replace(int givenPosition, T newEntry) {
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
assert !isEmpty();
Node desiredNode = getNodeAt(givenPosition);
T originalEntry = desiredNode.getData();
desiredNode.setData(newEntry);
return originalEntry;
} else
throw new IndexOutOfBoundsException(
"Illegal position given to replace operation.");
} // end replace
public T getEntry(int givenPosition) {
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
assert !isEmpty();
return getNodeAt(givenPosition).getData();
} else
throw new IndexOutOfBoundsException(
"Illegal position given to getEntry operation.");
} // end getEntry
public T[] toArray() {
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Object[numberOfEntries];
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
public void display(){
System.out.println("Displaying all the Nodes data: ");
Node currentNode = firstNode;
while (currentNode != null) {
System.out.print(currentNode.getData() + " ");
currentNode = currentNode.getNextNode();
} // end while
}
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 void swap(int firstPosition, int secondPosition) {
if(firstPosition >= 1 && firstPosition <= numberOfEntries &&
secondPosition >=1 && secondPosition <= numberOfEntries) {
Node firstToSwap = getNodeAt(firstPosition);
Node secondToSwap = getNodeAt(secondPosition);
T firstData = firstToSwap.getData();
T secondData = secondToSwap.getData();
T tmp = firstData;
firstToSwap.setData(secondData);
secondToSwap.setData(tmp);
}
}
public LList getAllLessThan(Comparable entry) {
LList smallerList = new LList();
Node currentNode = firstNode;
while(currentNode != null) {
T currentData = currentNode.getData();
if(entry.compareTo(currentData) > 0) {
smallerList.add(currentData);
}
currentNode = currentNode.getNextNode();
}
// this will work! but it's VERY inefficient!!
/*
for(int i=1; i<numberOfEntries; i++) {
T currentData = getEntry(i);
if(entry.compareTo(currentData) > 0) {
smallerList.add(currentData);
}
}
*/
return smallerList;
}
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
// Initializes the class's data fields to indicate an empty list.
private void initializeDataFields() {
firstNode = null;
numberOfEntries = 0;
} // end initializeDataFields
// Returns a reference to the node at a given position.
// Precondition: The chain is not empty;
// 1 <= givenPosition <= numberOfEntries.
private Node getNodeAt(int givenPosition) {
assert !isEmpty() && (1 <= givenPosition)
&& (givenPosition <= numberOfEntries);
Node currentNode = firstNode;
// Traverse the chain to locate the desired node
// (skipped if givenPosition is 1)
for (int counter = 1; counter < givenPosition; counter++)
currentNode = currentNode.getNextNode();
assert currentNode != null;
return currentNode;
} // end getNodeAt
private class Node {
private T data; // Entry in list
private Node next; // Link to next node
private Node(T dataPortion) {
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node nextNode) {
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 LList
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.