MCX2                                                                                                                 Math Department
Mr. Gary. Jaye                                                                                                    Danny Jaye, A.P.S.

1992 APCS AB Exam: Question 2

This problem involves writing code to locate and rearrange elements in a doubly linked list.

Lists are implemented using the following definitions.

struct ListNode {
     int info;
     ListNode * prev;
     ListNode * next;
     ListNode(int val, ListNode *prevPtr, ListNode *nextPtr) // constructor
         : info(val), prev(prevPtr), next(nextPtr) { }
};

Part A

Write a function Location that takes a list and an integer as arguments and returns a pointer to the list node whose Info member contains the integer. If the list is empty or the integer is not in the list, Location should return 0/NULL. Location should not modify the list. Assume that the list contains no duplicate values.

For example. the diagram below illustrates the result of executing the statement:

        L = Location (List, 5);

Complete function Location below the following header.

ListNode *Location(ListNode *List, int Key) {
    //precondition: List points to a doubly linked list that contains no duplicate values

}

Part B

Write a procedure MoveToFront that, given a list and an integer as arguments, moves the list node whose whose Info member contains the integer to the front of the list. The order of the remaining nodes is to remain unchanged. If no node in the list contains the integer, MoveToFront should leave the list unchanged. Assume that the list contains no duplicate values.

The two diagrams below illustrate the effect of the call MoveToFront(List, 5).

                    Before the call:

In writing procedure MoveToFront, you may call the function Location of part (a). Assume that Location works as specified, regardless of what you wrote in part (a).

Complete procedure MoveToFront below the following header. You will receive NO credit for part (b) if your procedure includes any assignments to a list node's Info field.

void MovetoFront(ListNode *&List, int Key) {
// precondition: List represents the list of integers i₁ i₂ . . . i_n   and List contains no duplicate values.
//postcondition: If there exists an i_k, 1 <= k <= n, such that i_k = Key, then List represents the list 
//                        of integers  i_ki₁ . . . i_{k - 1}i_{k + 1} . . . i_n.  Otherwise,  List remains i₁ i₂ . . . i_n

}