CSE 131 Module 8: List Structures
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.
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:
- Gather your group around one workstation. Plan on taking turns
at the keyboard.
- Review the
studio prep material
on doubly linked
Keep that material open on somebody's display for reference during the
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.
- If you want to load the workspace I developed during lecture,
copy and paste
into the SVN Explorer as a new URL,
change the yourusername to something more
appropriate, and check
The code you should probably study is the
SinglyLinkedListWithSentinel class, since it uses
sentinels and so does this studio.
- Examine the provided IntList interface.
- Now let's start a new class in this package, DoublyLinkedListOfInts:
You should now have stubs in your new class.
- Click: File...New...Class
- Fill in the name (DoublyLinkedListOfInts)
- In the Interfaces section, Add the IntList interface.
- Be sure the Inherit abstract methods box is checked.
- Finish it up
- For each method in the interface, discuss an implementation and
sketch how it would 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.
- For testing, I've included a TestLinkedListOfObjects jUnit test you can use as-is to test your code.
declarations of the interface type (IntList) as compared with the actual objects instantiated
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.
- 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
- Work on implementing the methods as we did in class, in the following order:
- Constructor -- like the LinkedListOfInts but it will have to initialize
the head and tail
the sentinels as well. Can those instance variables be final?
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.
- void addFirst(int item) -- be sure to think about special cases, such
as adding to an empty list.
- void addLast(int item) -- recall in the studio prep material, there is
not only a head pointer, but also a tail pointer. Try to do this operation
as efficiently and cleanly as you can.
- int size() -- remember that this returns the perceived size of the list, in terms
of how the end-user views the list. The sentinels do not count toward the size.
- int indexOf(int item) -- should return -1 if the item is not found.
Otherwise it should return the first occurence of the item in the list.
- boolean remove(int item) tries to remove the first occurence of the item, if any.
The method returns true if something was removed, false otherwise.
Try to use the sentinels to your advantage to avoid special cases as much as possible.
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
- Iterator<Integer> iterator() will take some thought.
Here are some ideas.
- It will not work to keep the state of the Iterator in the DoublyLinkedListOfInts
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.
- You can use extra classes if you need them. Just add them into the lists package
and use them however you like.
- This method must return an instance of an object that "implements" all of
the methods in the Iterator<Integer> interface:
- boolean hasNext()
- Integer next()
- void remove() -- for this method, do nothing, just have
a stub that is empty.
- IntList reverse() returns a new list with the elements in the reverse order of
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