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:
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.
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.
Please follow the instructions below carefully. Don't try to skip ahead.
You should now have stubs in your new class. If you do not, delete the new class and start again, following the instructions carefully.
Declare instance variables to represent these has-as in your DoublyLinkedListOfInts class.
- 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.
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.
Add the necessary instance variable, accessors and setters to the ListItem class.
- Your constructor must create the objects and pointers that are shown on slide 2 of the studio prep material .
- It's usually a good idea to assume initially that instance variables could be final and then retreat from that if necessary.
- DO NOT MOVE ON until you have shown your constructor to your TA so we can be sure you see how this object is supposed to be initialized. It's important to understand that before moving to the methods below.
A good way to think of this is to look at slide 1 of the studio prep material .
Try to use the sentinels and double links to your advantage. This method is quite easy because of those. Strive for the cleanest, correct implementation. Talk with others and other groups about ideas for doing this.
If you get this far, that's great. You may find the rest challenging, but give it a try for the time you have left. We'll talk more about iterators in the next lecture.
It's really important that you understand why the above is true. Discuss this amongst yourselves and talk with a TA about it. Do not move on until your group sees this point. Think of what would happen with two nested iterators if you had the state in the DoublyLinkedLIstOfInts object.
When you done with this studio, you must be cleared by the TA to receive credit.
- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click OK while the TA watches
- If you request propagation, it does not happen immediately, but should be posted in the next day or so