CSE 131 (Fall 2008)
Studio 9

If necessary, review studio procedures before starting. Work in groups of 2-3 people. I really mean it!
No more than 3 people per group please.

Circular List

In lecture this week, we looked at an implmentation of a Buffer<T> based on the Doubly Linked List. We then examined how Buffer<T> could support the Stack<T> and Queue<T> ADTs. In studio this week, you will investigate the Circular List, developing a parametric implementation that can also support the Stack<T> and Queue<T> ADTs.

The investigation should conclude with your ability to explain the qualitative difference in design and implementation between a singly, doubly, and circularly linked list. The quiz on this module will emphasize those distinctions, as follows:

Here are the steps:
  1. Gather around one workstation and plan to exchange turns at the keyboard.
  2. You should already be somewhat familiar with the studio prep material on circular lists. Spend a few minutes talking about the material and making sure you understand the basic ideas.
  3. Make or open a Java project called Studio9 in an eclipse workspace. Be sure to check the box to put source and compiled files in the same folder. Create a studio9 package in there and do your work in that package.
  4. Create a ListItem class and define it parametrically as ListItem<T> with instance variables exactly as follows: Do not declare them private, as they will be manipulated by another class in the studio9 package.
    ListItem is a parametric type: an instantiation of ListItem requires specification of an actual type for the type variable T. Discuss why parameterized types are useful. What role does the type variable play in the definition of the ListItem class?
  5. Define only the following two methods for the ListItem<T> class:
  6. Now start work on your CircularList<T> ADT. Create the class in your package and start working on the methods as follows.
    The studio prep material is going to be very helpful in reasoning about how to set up this ADT and maintain its structure with insertion and deletion. Have the last few pages of the notes handy as you work.
  7. The class will have only one instance variable to support the basic list structure:
     
      ListItem<T> back;
    
    Although it should be private, do not make it private! We will want to access it for testing.
  8. The constructor will take no inputs but should initialize all instance variables.
  9. Write the isEmpty() method.
  10. Write a toString() method for your CircularList<T> ADT.
    It is here, and not in ListItem, that you should create a String that shows the whole list. Your method should be as simple as possible. Try to articulate the fewest number of special cases (should be just one special case and then general treatment for all else).
  11. Write an addFirst method by discussing in your group how the method should be implemented. Be sure to consider any special cases, such as the empty list.
  12. Copy and paste the following code into a new JUnit test to try it out:
    //
    //  You may have to put the following lines, uncommented, after the package statement:
    //   import org.junit.Test;
    //   import org.unit.Assert.*;
    //
    @Test
    public void testAddFirst() {
       CircularList<Integer> list = new CircularList<Integer>();
       System.out.println("Empty lists looks like: " + list.toString());
       assertTrue(list.isEmpty());
       list.addFirst(new Integer(1));
       System.out.println("List with 1 looks like: " + list.toString());
       assertTrue(!list.isEmpty());
       list.addFirst(new Integer(2));
       System.out.println("List with 2 and 1 looks like: " + list.toString());
       System.out.println("This should print just one thing: " + list.back.toString());
       //
       // If the following fails, then  perhaps
       //   a) You did the wrong thing in ListItem's toString()
       //   b) Your CircularList instance variable back is not pointing to the
       //        rear of the list.
       //
       assertEquals("1", list.back.toString());
       assertTrue(!list.isEmpty());
    }
    

    Check the output of the above code in the console window to make sure your toString() is working properly.
  13. OK, now implement T getFirst() in your CircularList<T> ADT. Discuss as a group what this method should do if the list is empty.

    Add the following test to your JUnit test file and see what happens:


    @Test
    public void testGetFirst() {
       CircularList<Integer> list = new CircularList<Integer>();
       for (int i=0; i < 50; ++i) {
          list.addFirst(new Integer(i));
          //
          // Integer knows how to compare itself with other Integers
          //   no need to use toString() here for comparison purposes
          //
          assertEquals(new Integer(i), list.getFirst());
       }
       assertTrue(!list.isEmpty());
    }
    

  14. Now implement T removeFirst(). What are the special cases for this method?

    Test with the following code:


    @Test
    public void testRemoveFirst() {
       CircularList<Integer> list = new CircularList<Integer>();
       for (int i=0; i <= 49; ++i) {
          list.addFirst(new Integer(i));
       }
       for (int i=49; i >= 0; --i) {
          assertEquals(new Integer(i), list.removeFirst());
       }
       assertTrue(list.isEmpty());
    }
    

  15. There will be no removeLast method. It's not needed for this ADT, and it would be difficult to implement. So let's try addLast(T item) and T getLast(), testing with the following code:
    @Test
    public void testLastStuff() {
       CircularList<Integer> list = new CircularList<Integer>();
       for (int i=0; i <= 49; ++i) {
          list.addFirst(new Integer(i));
          list.addLast(new Integer(100+i));
       }
       for (int i=49; i >= 0; --i) {
          assertEquals(new Integer(i), list.removeFirst());
          assertEquals(new Integer(149), list.getLast());
       }
       for (int i=0; i <= 49; ++i) {
          assertEquals(new Integer(100+i), list.removeFirst());
       }
       assertTrue(list.isEmpty());
    }
    

  16. Why would T removeLast() be difficult to implement?
  17. Discuss how to implement a Stack<T> class using your CircularList<T> class. Show this to a TA, no need to test it here in studio.
  18. (tricky) Discuss how to implement a Queue<T> class using only the Stack<T> ADT.
  19. With your TA and amongst yourselves, discuss the differences between the Circular List, the Singly Linked List, and the Doubly Linked List.



Last modified 07:25:15 CST 04 November 2008 by Ron K. Cytron