CSE 131 Module 9: 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. It's also in your personal repos, but it would be easier not to mention that now.
    The code you should probably study is the SinglyLinkedListWithSentinel class, since it uses sentinels and so does this studio.

    I will go over this when studio begins.

  4. Examine the provided IntList interface.
  5. Now let's start a new class in this package, DoublyLinkedListOfInts:
    • 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
    You should now have stubs in your new class.
  6. A DoublyLinkedListOfInts has-a:
    • head pointer, just as we have in the SinglyLinkedListWithSentinel
    • tail pointer, which points to the other sentinel, at the end of the list
    • size, which reflects the number of bona fide integers in this list. In other words, the sentinels are not included in the size count.
    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:
    • Constructor -- like the LinkedListOfInts but it will have to initialize the head and tail the sentinels as well. Can those instance variables be final?
      • 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.
    • String toString() -- you might want to implement this first, so you can use it for debugging by printing out the state of the list.
      A good way to think of this is to look at slide 1 of the studio prep material .
    • 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 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.

    • 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 class.
        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 this list.

Submitting your work (read carefully)

Last modified 11:27:54 CST 30 November 2012
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

TA: Password: