CSE 131 Module 9: ADT Representations
Review studio procedures before
- Form groups of no more than three people.
If your group
is joined by a fourth person, split into two groups of two.
- One of you should log in, launch eclipse, and
open the SVN Repository Exploring perspective:
Window...Open Perspective...Other...SVN Repository Exploring
- Click on the New Repository Location icon (looks like a
gold battery with a green plus sign).
- Copy the following URL using your mouse:
- Change XXXXX to your username that you use to log into cec computers. For example, jdl2.
- Be sure the directory after fall09 is studios and
- Change ZZZZZZ to the word on your sticker.
For example, animal.
- If prompted, type in your name and password.
- If the repository is validated, keep going; otherwise get help.
- Right-click on the project name and Check Out the workspace.
- Return to the Java perspective.
In lecture this week, we looked at an
implmentation of a Buffer<T> based on the
Doubly Linked List. We then examined how
could support the
In studio this week, you will investigate the Circular List, developing a
parametric implementation that can also support the
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:
- What are the respective lists' advantages and disadvantages?
- What implementation considerations were important to a given implementation
as compared with the others?
- If you want to look at the code developed during lecture, use the
following SVN URL (edit to put in your username):
- 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.
- Use eclipse to add a new class ListItem (from the
File menu) and define it
ListItem<T>. You can specify the whole parameterized
name as the new Java class name to eclipse.
- Give ListItem<T>
instance variables defined exactly as follows:
Do not declare them private, as they will be manipulated by
another class in the studio9 package.
- final T item
- ListItem<T> next
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?
- Define only the following two methods for the
- public ListItem(T item) initializes the instance
variable item to the supplied value, and sets next to
- public String toString() returns something appropriate
by delegating to the item's toString().
object's toString() should be concerned only with this
- You should avoid referencing other objects from toString(),
particularly those that could be involved in cycles of reference.
- Now add a new class for your
Work on the methods as follows, testing where indicated.
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.
- The class will have only one instance variable to support the
basic list structure:
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 .
- The constructor will take no inputs but should initialize all
- Write the isEmpty() method.
- Write a toString() method for your
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).
- 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.
- 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.
- OK, now implement T getFirst() in your
Discuss as a group what this method should do if the list is empty.
- You should now pass the testGetFirst test.
- Now implement T removeFirst().
What are the special cases for this method?
You should now pass the testRemoveFirst test.
- There will be no removeLast method. It's not needed for
this ADT, and it would be difficult to implement.
Let's try addLast(T item) and
T getLast(), testing to pass the testLastStuff test.
- Why would T removeLast() be difficult to implement?
- 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.
- (tricky) Discuss how to implement a Queue<T> class using
- 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)
- Complete the feedback.txt file and be sure to list
your group members' names and ID last-3-digits.
- Answer the other questions in the feedback.txt file.
- You must commit all of your work to your repository. It's best to do this
from the top-most level of your repository, which bears your name and student ID.
- You must have the TA clear you by signing your studio group sheet.
Be sure your names and IDs are written
clearly on the TA's demo sheet.
Last modified 22:14:03 CST 11 November 2009
by Ron K. Cytron