Exercise 7.1.
Suppose that we want to extend the PositionalList ADT with a method indexOf(p) that returns the current index of the element stored at position p. Show how to implement this method using only other methods of the PositionalList Interface.
Exercise 7.2.
Suppose we want to extend the PositionalList ADT with a method findPosition(e) that returns the first position containing an element equal to e (or null if no such position exists). Show how to implement this method using only existing methods of the PositionalList interface.
Exercise 7.3.
Suppose we want to extend the PositionalList interface to include a method positionAtIndex(i) that returns the position of the element having index i (or throws an IndexOutOfBoundsException, if warranted). Show how to implement this method using only the existing methods from the PositionalList interface
Exercise 7.4.
Suppose we want to extend the PositionalList ADT with a method moveToFront(p) that moves the element at position p to the front of the list (if not already there), while keeping the relative order of the remaining elements unchanged. Show how to implement this method using only methods from the PositionalListInterface.
Exercise 7.5.
Modify the LinkedPositionalList class to support a method swap(p,q) that causes the underlying nodes referenced by positions p and q to be exchanged for each other. Relink the existing nodes. Don’t create any new node.
Exercise 7.6.
Design a circular positional list ADT that abstracts a circularly linked list in the same way that a positional list ADT abstract a doubly linked list.
Exercise 7.7.
Write a simple text editor, which stores and display a string of characters using the positional List ADT, together with a cursor object that highlights a position in the string. The editor must support the following operations: (1) left (Move cursor left one character, do nothing if at the beginning), right (Move cursor right one character, do nothing if at the end), insert c (insert character c just after cursor) and delete (Delete the character just after the cursor)
Exercise 7.8.
An array is sparse if most of its entries are null. A list L can be used to implement such an array A efficiently. In particular, for each nonnull cell A[i], we can store a pair (i,e) in L, where e is the element stored in A[i]. This approach allows us to represent A using O(m) storage, where m is the number of non null entries in A. Describe and analyze efficient ways of performing the methods of the array list ADT on such a representation.
Exercise 7.9.
Implement a CardHand class that supports a person arranging a group of cards in his or her hand. The simulator should represent the sequence of cards using a single positional list ADT so that cards of the same suit are kept together. Implement this strategy by means of four “fingers” into the hand, one for each of the suits of hearts, clubs, spades and diamonds, so that adding a new cardto the person’s hand or playing a correct card from the hand can be done in constant time. The class should support the following methods: addCard(r, s) (Add a new card with rank r and suit s to the hand), play(s) (Remove and return a card of suit s from the player’s hand; if there is no card of suit s, then remove and return an arbitrary card from the hand), Iterator() (return an iterator for all cards currently in the hand) as well as suitIterator(s) (return an iterator for all cards of suit s that are currently in the hand)
Exercise 7.10.
Give an array-based list implementation, with fixed capacity, treating the array circularly so that it achieves O(1) time for insertions and removals at index 0, as well as insertions and removals at the end of the array list. Your implementation should also provide for a constant time get method.
