LinkedList.java

import java.util.Iterator;

* @param

* the class (or an ancestor class) of objects to be stored in the list such that T

* implements the Comparable interface.

*/

public class LinkedListPlus>

implements ListInterface,

Iterable

{

private Node firstNode; // Head reference to first node

private Node lastNode; // Tail reference to last node

private int numberOfEntries;

public LinkedListPlus()

{

initializeDataFields();

} // end default constructor

@Override

public void clear()

{

initializeDataFields();

} // end clear()

@Override

public void add(T newEntry)

{

Node newNode = new Node(newEntry);

if (isEmpty())

firstNode = newNode;

else

lastNode.setNextNode(newNode);

lastNode = newNode;

numberOfEntries++;

} // end add()

@Override

public void add(int newPosition, T newEntry)

{

if ((newPosition >= 1) && (newPosition

{

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

throw new IndexOutOfBoundsException("Illegal position given to add operation.");

} // end add()

@Override

public T remove(int givenPosition)

{

T result = null; // Return value

if ((givenPosition >= 1) && (givenPosition

{

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: Not first entry

{

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--;

}

else

throw new IndexOutOfBoundsException("Illegal position given to remove operation.");

return result; // Return removed entry

} // end remove()

@Override

public T replace(int givenPosition, T newEntry)

{

if ((givenPosition >= 1) && (givenPosition

{

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()

@Override

public T getEntry(int givenPosition)

{

if ((givenPosition >= 1) && (givenPosition

{

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

{

result[ index ] = currentNode.getData();

currentNode = currentNode.getNextNode();

index++;

} // end while

return result;

} // end toArray()

@Override

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()

@Override

public int getLength()

{

return numberOfEntries;

} // end getLength()

@Override

public boolean isEmpty()

{

boolean result;

if (numberOfEntries == 0) // Or getLength() == 0

{

assert (firstNode == null) && (lastNode == null);

result = true;

}

else

{

assert (firstNode != null) && (lastNode != null);

result = false;

} // end if

return result;

} // end isEmpty()

@Override

public void sort()

{

// TODO Auto-generated method stub

} // end sort()

/* (non-Javadoc)

* @see java.lang.Iterable#iterator()

*/

@Override

public Iterator iterator()

{

// TODO Auto-generated method stub

return null;

} // end iterator()

// Initializes the class's data fields to indicate an empty list.

private void initializeDataFields()

{

firstNode = null;

lastNode = null;

numberOfEntries = 0;

} // end initializeDataFields()

// Returns a reference to the node at a given position.

// Precondition: List is not empty; 1

private Node getNodeAt(int givenPosition)

{

assert (firstNode != null) && (1

(givenPosition

Node currentNode = firstNode;

if (givenPosition == numberOfEntries)

currentNode = lastNode;

else if (givenPosition > 1)

{

assert givenPosition

// Traverse the chain to locate the desired node

for (int counter = 1; counter

currentNode = currentNode.getNextNode();

} // end if

assert currentNode != null;

return currentNode;

} // end getNodeAt()

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 inner class Node

} // end LinkedListPlus

Listinterfece.java:

public interface ListInterface > {

/**

* Task: Adds a new entry to the end of the 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);

/**

* Task: Adds a new entry at a specified position within the list. Entries

* originally at and above the specified position move to 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

*/

public void add(int newPosition, T newEntry);

/**

* Task: Removes all entries from the list.

*/

public void clear();

/**

* Task: Removes the entry at a given position from the list. Entries

* originally at positions higher than the given position move to 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 if successful, a reference to the removed entry, otherwise null (e.g.

* givenPosition

*/

public T remove(int givenPosition);

/**

* Task: Replaces the entry at a given position in the 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 a reference to the replaced entry if the replacement is successful,

* otherwise null (e.g. givenPosition getLength(), or

* newEntry isn't valid/acceptable)

*/

public T replace(int givenPosition, T newEntry);

/**

* Task: Retrieves the entry at a given position in the list.

*

* @param givenPosition an integer that indicates the position of the

* desired entry

* @return if successful, a reference to the indicated entry, otherwise null (e.g.

* givenPosition getLength())

*/

public T getEntry(int givenPosition);

/**

* Task: Sees whether the 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);

/**

* Task: Gets the length of the list.

*

* @return the integer number of entries currently in the list

*/

public int getLength();

/**

* Task: Sees whether the list is empty.

*

* @return true if the list is empty, or false if not

*/

public boolean isEmpty();

/**

* Task: Rearrange the entries in the list in non-descending order using a stable

* sorting algorithm.

*/

public void sort();

} // end ListInterface

For this lab, implement the ADT List by using a singly linked list contain its entries. Your implementation should differ from the book's implementation in the following ways: Your list must start at a position of 0 instead of 1, so the smallest valid entry is 0 . Your list should have an iterator defined in its class. (The remove implementation of the iterator is optional.) . Your list must implement sort. Implement the currently unimplemented methods in LinkedListPlus.java. In addition, modify the bodies of the already-implemented methods to account for the valid 0 index. For sorting, you must implement your own sorting code. You may not use Java's built-in sort. Note that the insertion sort in the slides doesn't account for a changing lastNode, so your sorting code should update that appropriately Ignore the toArray method. It is impossible to implement as-is To complete the Iterator implementation, follow the LinkedList WithIterator example from the slides/- book. Do not use the java.uti version of a list anywhere implementation the goal of this lab is to create an independent For this lab, implement the ADT List by using a singly linked list contain its entries. Your implementation should differ from the book's implementation in the following ways: Your list must start at a position of 0 instead of 1, so the smallest valid entry is 0 . Your list should have an iterator defined in its class. (The remove implementation of the iterator is optional.) . Your list must implement sort. Implement the currently unimplemented methods in LinkedListPlus.java. In addition, modify the bodies of the already-implemented methods to account for the valid 0 index. For sorting, you must implement your own sorting code. You may not use Java's built-in sort. Note that the insertion sort in the slides doesn't account for a changing lastNode, so your sorting code should update that appropriately Ignore the toArray method. It is impossible to implement as-is To complete the Iterator implementation, follow the LinkedList WithIterator example from the slides/- book. Do not use the java.uti version of a list anywhere implementation the goal of this lab is to create an independent