CSE 131 Module 11: Lists


If necessary, review studio procedures before starting.


Doubly Linked Lists

In lecture this week, we implemented an IntList interface using lists with one link per item. In this studio, you will investigate implementation of our IntList ADT using a doubly linked list. Your work will include design and implementation of iterators (forwards and backwards) for the list, and a discussion that compares your implementation with the singly linked list from lecture.
Here are the steps:
  1. Gather your group around one workstation. Plan on taking turns at the keyboard.
  2. Review the studio prep material on doubly linked lists. Keep that material open on somebody's display for reference during the studio.
    Note: The "null" in the sentinel nodes should really be "any integer you like because it will be ignored". In other words, the sentinels should also be ListItem objects.
  3. Code developed during lecture is in your studio workspace. Look in the studio9 package of the studios source folder.
    The code you should probably study is the SinglyLinkedListWithSentinel class, since it uses sentinels and so does this studio.

    This code is in your studio9 package.

  4. Examine the provided IntList interface.
    Please follow the instructions below carefully. Don't try to skip ahead.
  5. Now let's start a new class in this package, DoublyLinkedListOfInts:
    You should now have stubs in your new class. If you do not, delete the new class and start again, following the instructions carefully.
  6. A DoublyLinkedListOfInts has-a:
    Declare instance variables to represent these has-as in your DoublyLinkedListOfInts class.
  7. For each method in the interface, discuss an implementation and sketch how it would work:
    • More details are provided below, but you should first talk about this.
    • As you work, look for opportunities to reduce one method's work to another's.
    • One of the most important aspects of this design is the use of a sentinel, as depicted in the studio prep material . Discuss the role of sentinels and how they affect (simplify) your implementation.
  8. For testing, I've included a TestLinkedListOfObjects jUnit test you can use as-is to test your code. Notice the declarations of the interface type (IntList) as compared with the actual objects instantiated (LinkedListOfInts).
    Use the interface type as much as possible. It does not commit to an implementation and this makes it easier to change from one implementation of the interface to another.
  9. The ListItem class, as given to you and as used in lecture, had only one pointer, namely next. For the doubly linked list, you need to augment ListItem to have two pointers: next and prev.
    Add the necessary instance variable, accessors and setters to the ListItem class.
  10. Work on implementing the methods as we did in class, in the following order:

Submitting your work (read carefully)

Last modified 11:55:48 CDT 13 May 2014
When you done with this studio, you must be cleared by the TA to receive credit.

Last name WUSTL Key Propagate?
(or your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others
3 Copy from 3 to all others
4 Copy from 4 to all others

TA: Password: