CSE 131 Module 9: ADT Representations

Studio

Studio 9

Review studio procedures before starting.

Warmup

Circular List

In lecture this week, we looked at a Buffer<T> ADT. 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:

  1. 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.
    All the work below is to be done in your group's studio9 package space.
  2. Use eclipse to add a new class ListItem (from the File menu) and define it parametrically as ListItem<T>. You can specify the whole parameterized name as the new Java class name to eclipse.
  3. Give ListItem<T> instance variables defined exactly as follows:
    • final T item
    • ListItem<T> next
    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?
  4. Define only the following two methods for the ListItem<T> class:
    • public ListItem(T item) initializes the instance variable item to the supplied value, and sets next to null.
    • public String toString() returns something appropriate by delegating to the item's toString().
      • Generally, an object's toString() should be concerned only with this object.
      • You should avoid referencing other objects from toString(), particularly those that could be involved in cycles of reference.
  5. Now add a new class for your CircularList<T> implementation. Work on the methods as follows, testing where indicated.
    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.
  6. 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.
    If you are not sure what back does, take a look at the pictures on page 6 of the studio prep material .
  7. The constructor will take no inputs but should initialize all instance variables.
  8. Write the isEmpty() method.
  9. 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).
  10. 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.
  11. Try the JUnit test included with the studio. You should pass the testAddFirst test.
    Check the output of the test in the console window to make sure your toString() is working properly.
  12. OK, now implement T getFirst() in your CircularList<T> ADT. Discuss as a group what this method should do if the list is empty.
  13. You should now pass the testGetFirst test.
  14. Now implement T removeFirst(). What are the special cases for this method?

    You should now pass the testRemoveFirst test.

  15. There will be no removeLast method. It's not needed for this ADT, and it would be difficult to implement.
  16. Let's try addLast(T item) and T getLast(), testing to pass the testLastStuff test.
  17. Why would T removeLast() be difficult to implement?
  18. 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.
  19. (tricky) Discuss how to implement a Queue<T> class using only the Stack<T> ADT.
  20. With your TA and amongst yourselves, discuss the differences between the Circular List, the Singly Linked List, and the Doubly Linked List.

Submitting your work (read carefully)


Last modified 14:30:49 CDT 03 September 2011
When you done with this studio, you must be cleared by the TA to receive credit.

Studio repo name: studio9- (from your sticker)

People on your team:

Last name 6-digit ID
1
2
3
4
5
6
TA: Password: