I need help with writing the add method below. I have already implemented the ot
ID: 3906497 • Letter: I
Question
I need help with writing the add method below.
I have already implemented the other methods outlined in the list interface class, so do not worry about those.
I only need help with the add method.
/**
* A class that implements the ADT list by using a chain of linked nodes that
* has a head reference.
*
* @author
*/
public class LListWithTail> implements ListInterface
{
private Node firstNode; // Head reference to first node
private Node lastNode; // Tail reference to last node
private int numberOfEntries; // Number of entries in list
//private int indexOfMinValue = 0;
//private int indexOfMaxValue = 0;
public LListWithTail()
{
initializeDataFields();
}
/**
* Removes all entries from this list.
*/
public void clear()
{
initializeDataFields();
}
// Initializes the class's data fields to indicate an empty list.
private void initializeDataFields()
{
firstNode = null;
lastNode = null;
numberOfEntries = 0;
}
/**
* Retrieves all entries that are in this list in the
* order in which they occur in the list.
* @return A newly allocated array of all the entries
* in the list. Note: If the list is empty, the returned array is empty.
*/
public T[] toArray()
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Comparable[numberOfEntries];
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.getData();
currentNode = currentNode.getNextNode();
index++;
}
return result;
}
/**
* Adds a new entry to the correct position in this list, so that
* entries in this list are in nondecreasing order.
* The list's size is increased by 1.
* @param newEntry: The object to be added as a new entry.
*/
public void add(T newEntry) //TODO
{
Node newNode = new Node(newEntry);
if(isEmpty())
{
firstNode = newNode;
lastNode = newNode;
numberOfEntries++;
return;
}
else
{
}
}
private class Node
{
private T data; // Entry in list
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
}
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
}
private T getData()
{
return data;
}
private void setData(T newData)
{
data = newData;
}
private Node getNextNode()
{
return next;
}
private void setNextNode(Node nextNode)
{
next = nextNode;
}
} // end Node
}// end LListWithTail
/**
* An interface for the ADT list. Entries in a list have positions that begin
* with 1.
* @author Darnesha Randle
*/
public interface ListInterface<T extends Comparable<? super T>>
{
/**
* Adds a new entry to the correct position in this list, so that
* entries in this list are in nondecreasing order.
* The list's size is increased by 1.
* @param newEntry: The object to be added as a new entry.
*/
public void add(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.
* @throws IndexOutOfBoundsException if either
* givenPosition < 1 or givenPosition > getLength().
*/
public T remove(int givenPosition);
/**
* Removes all entries from this list.
*/
public void clear();
/**
* 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.
* @throws IndexOutOfBoundsException if either
* givenPosition < 1 or givenPosition > getLength().
*/
public T getEntry(int givenPosition);
/**
* Retrieves all entries that are in this list in the
* order in which they occur in the list.
* @return A newly allocated array of all the entries
* in the list. Note: If the list is empty, the returned array is empty.
*/
public T[] toArray();
/**
* 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();
/**
* Returns the smallest object in this list.
*/
public T getMin();
/**
* Returns the largest object in this list.
*/
public T getMax();
/**
* Removes and returns the smallest object in this list.
*
*/
public T removeMin();
/**
* Removes and returns the largest object in this list.
*/
public T removeMax();
/**
* Returns a new list that are less than some given item.
*/
public ListInterface<T> getAllLessThan(T anObject);
} // end ListInterface
Explanation / Answer
Here is the completed code (add method) for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// LListWithTail.java
public class LListWithTail<T extends Comparable<? super T>> implements
ListInterface<T>
{
private Node firstNode; // Head reference to first node
private Node lastNode; // Tail reference to last node
private int numberOfEntries; // Number of entries in list
// private int indexOfMinValue = 0;
// private int indexOfMaxValue = 0;
public LListWithTail()
{
initializeDataFields();
}
/**
*
* Removes all entries from this list.
*/
public void clear()
{
initializeDataFields();
}
// Initializes the class's data fields to indicate an empty list.
private void initializeDataFields()
{
firstNode = null;
lastNode = null;
numberOfEntries = 0;
}
/**
*
* Retrieves all entries that are in this list in the
*
* order in which they occur in the list.
*
* @return A newly allocated array of all the entries
*
* in the list. Note: If the list is empty, the returned array is
* empty.
*/
public T[] toArray()
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Comparable[numberOfEntries];
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.getData();
currentNode = currentNode.getNextNode();
index++;
}
return result;
}
/**
*
* Adds a new entry to the correct position in this list, so that
*
* entries in this list are in nondecreasing order.
*
* The list's size is increased by 1.
*
* @param newEntry
* : The object to be added as a new entry.
*/
public void add(T newEntry) // TODO
{
Node newNode = new Node(newEntry);
if (isEmpty())
{
/**
* case where the list is empty
*/
firstNode = newNode;
lastNode = firstNode;
numberOfEntries++;
return;
}
else
{
Node currentNode = firstNode;
Node nextNode = firstNode.next;
if (nextNode == null) {
/**
* case where the list contains only one element
*/
if (newEntry.compareTo(currentNode.data) < 0) {
newNode.next = firstNode;
firstNode = newNode;
} else {
lastNode.next = newNode;
lastNode = newNode;
}
numberOfEntries++;
} else {
/**
* case where the list contain more than 1 elements
*/
if (newEntry.compareTo(firstNode.data) < 0) {
/**
* Adding to the first position
*/
newNode.next = firstNode;
firstNode = newNode;
numberOfEntries++;
return;
}
boolean added = false;// denote if the node is added or not
/**
* looping through all nodes
*/
while (nextNode != null) {
/**
* checking if the new node fits between the current pair of
* nodes
*/
if (newEntry.compareTo(currentNode.data) >= 0
&& newEntry.compareTo(nextNode.data) < 0) {
/**
* Adding to the middle of two nodes
*/
currentNode.next = newNode;
newNode.next = nextNode;
numberOfEntries++;
added = true;
break;
}
currentNode = currentNode.next;
nextNode = nextNode.next;
}
/**
* if still not added, adding to the last position
*/
if (!added) {
lastNode.next = newNode;
lastNode = newNode;
numberOfEntries++;
}
}
}
}
/**
* As you mentioned that you have implemented the other methods outlined in
* the list interface class, I'm leaving the other methods empty except
* isEmpty() method which is required for the above method to work.
*/
@Override
public T remove(int givenPosition) {
// TODO Auto-generated method stub
return null;
}
@Override
public T getEntry(int givenPosition) {
// TODO Auto-generated method stub
return null;
}
@Override
public boolean contains(T anEntry) {
// TODO Auto-generated method stub
return false;
}
@Override
public int getLength() {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return numberOfEntries == 0;
}
@Override
public T getMin() {
// TODO Auto-generated method stub
return null;
}
@Override
public T getMax() {
// TODO Auto-generated method stub
return null;
}
@Override
public T removeMin() {
// TODO Auto-generated method stub
return null;
}
@Override
public T removeMax() {
// TODO Auto-generated method stub
return null;
}
@Override
public ListInterface<T> getAllLessThan(T anObject) {
// TODO Auto-generated method stub
return null;
}
private class Node
{
private T data; // Entry in list
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
}
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
}
private T getData()
{
return data;
}
private void setData(T newData)
{
data = newData;
}
private Node getNextNode()
{
return next;
}
private void setNextNode(Node nextNode)
{
next = nextNode;
}
} // end Node
}// end LListWithTail
// Test.java (for testing)
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
/**
* creating a LListWithTail of integers
*/
LListWithTail<Integer> list=new LListWithTail<Integer>();
/**
* Adding some integers
*/
list.add(32);
list.add(24);
list.add(55);
list.add(55);
list.add(77);
list.add(-2);
list.add(7);
list.add(0);
list.add(0);
list.add(-1);
list.add(123);
list.add(46);
/**
* printing the list
*/
System.out.println(Arrays.toString(list.toArray()));
}
}
/*OUTPUT*/
[-2, -1, 0, 0, 7, 24, 32, 46, 55, 55, 77, 123]