Other 2008 FR Questions FR other years Be Prepared Home
AB-2
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:
  1. Adjustment for the newly added node.
  2. 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)

Other 2008 FR Questions | Back to Contents

Copyright © 2008 by Skylight Publishing
support@skylit.com