Part (a)
/** Gets a value at a given index in this list.
* @param n the index at which to get a value
* Precondition: 0 = n < size()
* @return the object at the given index
* Postcondition: The remembered node and index refer to the node at index n
*/
public Object get(int n)
{
if (remIndex == -1 || remIndex > n)
{
remIndex = 0;
remNode = front;
}
while (remIndex < n)
{
remNode = remNode.getNext();
remIndex++;
}
return remNode.getValue();
}
Part (b)
/** Adds a new node containing obj to the front of this list.
* @param obj the value to add to the list
*/
public void addFirst(Object obj)
{
front = new ListNode(obj, front);
listSize++;
if (remIndex >= 0)
remIndex++; 1, 2
}
Notes:
- Adjustment for the newly added node.
-
remIndex and remNode must always remain in sync.
The above solution keeps them both unchanged when addFirst is called for an empty list.
This is in agreement with the instructions: "This method
should not change the value of remNode
since there is no advantage to remembering a node at the front
of the list."
(An alternative solution would update both remIndex and
remNode :
front = new ListNode(obj, front);
listSize++;
remIndex++;
if (remNode == null)
remNode = front;
Actually, this version is slightly more efficient when the list is initially empty and
several consecutive calls to addFirst are
followed by a call to "get last.")
Part (c)
SomeListType |
printForward |
printReverse |
LinkedList<Object> |
O(n2) |
O(n2) |
APList |
O(n) |
O(n2) |
|