Big Java / Java Concepts Lab 20

Using Linked Lists

1.

Using the "cursor in a word processor" notation from the book, indicate the contents of the list and the iterator position after each step in the code below.

LinkedList<String> letters = new LinkedList<String>();
ListIterator<String> iterator = letters.listIterator();
iterator.add("A");
iterator.add("C");
iterator.add("D");
iterator = letters.listIterator();
iterator.next();
iterator.next();
iterator.remove();

Implementing Linked Lists

2.

The LinkedList class in the standard Java library has a get(int index) method that allows you to retrieve arbitrary list elements, just like you can in an ArrayList. In this lab, we want to analyze why this operation is inefficient.

Add a method

Object get(int index)

to the LinkedList implementation of Chapter 20. What is the code for your method?

3.

 What does your method do if index is < 0 or >= the size of the linked list?

4.

Write a tester program that adds ten items to a LinkedList and then executes the loop

for (int i = 0; i < list.size(); i++)
   System.out.println(list.get(i));

What is the code for your tester program?

5.

 How many times does the tester program look up the next value of a list node? How many lookups would it make if there were 100 elements in the list?

6.

It is possible to optimize the behavior of the get method in some common cases. You can cache the last visited position and its Node pointer. Then you can start from that position instead of the start of the linked list. 

public Object get(int index)
{
   Node current;
   if (lastVisitedPosition > 0 && lastVisitedPosition < index)
   {
      current = lastVisitedNode;       
      while (. . .) 
         current = current.next;      
   }
   else
   {
      current = first;      
      while (. . .) 
         current = current.next;      
   }
   // remember for next time
   lastVisitedPosition = index;
   lastVisitedNode = current;
   . . .
}

Finish the implementation of the method, and test it with the same tester program.

What is the code of the get method?

7.

 With this modification, how many times does the tester program look up the next value of a list node?

8.

 This is an ingenious trick, but it has limitations. If another method mutates the linked list, then the cached position may no longer be accurate, and the cache should be invalidated by setting lastVisitedPosition to -1. Which methods of the LinkedList and LinkedListIterator class need to be modified?

9.

 The standard library does not use this trick in its implementation of get, but it uses another optimization: if index is > size() / 2, then the search starts at the end of the list, not at the beginning. With that optimization, how many lookups of the next or previous value would the tester program make if it looped through a list with 100 elements?

Abstract and Concrete Data Types

10.

You are assigned to write a program to schedule appointments for a doctor's office. An appointment is scheduled every half an hour from 8 a.m. to 4 p.m., with no appointments between 12 p.m. and 1 p.m. Not all times may be scheduled, and some times may be double-booked. You must be able to delete and add appointments at anytime. Would you use a linked list or an array to store appointments? Why?


11.

When performing a binary search, is it more appropriate to use an array or a linked list? Why?

Stacks and Queues

12.

A deque is a double-ended stack or a double-ended queue. Items can be inserted or removed from either end. Write an implementation of a deque of strings using a LinkedList. No other type of element access should be permitted (e.g. get element at position i).

public class Deque
{
    . . .

    public void addFirst(Object str){ . . . }
    public Object removeFirst(){ . . . }
    public void addLast(Object str){ . . . }
    public Object removeLast(){ . . . }

    private LinkedList<Object> list;
}

13.

Suppose you make your previous deque implementation iterable by modifying it as follows:


public class Deque implements Iterable<Object>
{
   . . .

    public Iterator<Object> iterator()
    {
       return list.iterator();
    }

    private LinkedList<Object> list;
}

Now you can iterate through the deque using the "for each" loop. Adding this functionality is very useful because it allows us to iterate through the elements of the queue and print them.

Write a test program that adds elements to a deque and then prints them out with a "for each" loop. What is your test program?

14.

The problem is that by returning an iterator, we would be allowing an illegal operation to the deque: to be able remove an element at an arbitrary position, by calling iterator.remove().

Write a tester program that shows that if you change your queue implementation as suggested above, you can now remove an element in the middle of the list.


15.

You can solve the problem by disabling the remove() method for your Deque iterator You can do that by creating your own iterator class which just calls the methods of the list iterator, except for the remove method. If another class calls the iterator's remove method, the method should not perform the remove operation; instead, it should throw an UnsupportedOperationException.

Part of the code of the class has been provided for you:

public class Deque implements Iterable<Object>
{

    public Iterator<Object> iterator() { return new DequeIterator(); }

    private class DequeIterator implements Iterator<Object>
    {
        public DequeIterator() { . . . }
        public boolean hasNext() { . . . }
        public Object next() { . . . }
        public void remove() { . . . }

        private Iterator<Object> iterator;
    }
    . . .
}

What is the code of your modified ListQueue class?


16.

Use the tester program you created in problem 14. What happens when you try to remove an element using the iterator's remove()?


17.

A couple has a monthly surplus of $300 that is set aside in an account for discretionary spending. The account balance was $0 in January. In April, the couple decided to purchase a new couch that cost $1600. In May they decided to purchase a weaving loom that cost $2000. In August, they decided to purchase a laptop computer for $1,100. In September, they decided to purchase a trip to Italy for $4,000. In December, they decided to purchase a season pass for the local cross-country ski resort for $200. 

Items are purchased when there is money available. Unpurchased items remain in the queue until sufficient funds become available. This way, the items are purchased in the order that they are requested.

Write a program to simulate the spending and savings of this couple. Allow a user to enter the amount of discretionary money that is set aside each month. Also allow the user to enter items to be purchased each month.

What is the code for your program?


18.

With the data from the preceding problem,
   1. What is the largest surplus accumulated in the special account for discretionary spending?
   2. What is the largest deficiency for items for which there are insufficient funds?

Modify your program to supply this information and give the results.