I suggest start on this problem set early. If you start early, you are likely not to find it difficult at all. On the other hand, if you start late and make some mistakes in manipulating references (which is easy to do when dealing with linked lists), it may be too late to get help.
This assignment will give you experience with low-level data structure manipulations. Most of the time we will be using pre-packaged implementations of ADTs to solve problems. However, being able to write your own data structures to implement an ADT, when necessary, is a useful skill. It is also important to understand something about what is being hidden inside ADTs in order to be able to make intelligent tradeoffs.
SLL.javaWe saw that a major drawback to SLL.java is the fact that
deletion is an O(n) operation, because of the need to find the predecessor
of the current item in order to delete it.
In class I briefly mentioned a way
to get around this problem by using a dummy list header and keeping track
of the item before the current
item. In this part of the assignment you will modify
SLL.java
to use this representation. I suggest renaming the class. Mine is called
HeaderSLL, but you can choose whatever name that you like.
You could still call the instance variable current,
but it is less confusing to call it currentPred or
some such name. This is an excellent chance to use refactoring in Eclipse.
Select the name "current" in its declaration, chose "Rename" from within
the Refactor menu, change the name, and hit return. All instances of the
variable get renamed. The comments don't need to change, because we still
have the same idea of current. We have just changed how we represent it.
For the basic assignment you should eliminate the tail instance
variable. Updating this efficiently turns out to be trickier
than it would first appear. Keeping track of the tail of the list
will be extra credit.
Our SLL with dummy header and currentPred is shown below. The first
element in the linked list (with data field null) is not
part of the list represented. It is like the sentinel in SentinelDLL.
It is there to make operations easier. This represents a list with 3 elements,
not 4.
Note that
the current item is "NH", because currentPred
refers to the element before it in the list. Note that using this representation,
deleting the current item will be the same no matter which item is deleted.
You simply change the next field in the element referenced by
currentPred. This is the advantage of having a dummy list head.
So what should an empty list look like? The following shows head,
currentPred, and the dummy list header. Note that currentPred
references the dummy list header rather than being null. But if you follow
next from the dummy list header you get null, so this indicates that
there is no current. This is the situation that will arise naturally if you remove
the only item in a list, so it is more convenient than using currentPred == null
as the test for no current.
Draw pictures of what the list should look like before and after various operations.
Use them to figure out the names of fields that need to be changed and the values
that they need to be changed to. In many cases the only change needed is to use
currentPred.next in places that SLL.java used current.
Run your program with ListTest.java
to demonstrate that it works. Notice that you have to change one line in ListTest.java
in order to be able to test your implementation.
Figure out which line it is and fix it.
Make sure to test all of the boundary cases - adding and removing at the front of the list, the end of the list, the middle of the list, etc. Make sure that things work correctly for an empty list. Your testing should not be random, but should be clearly organized and complete enough to convince us that your program works correctly.
tailCreate an instance variable tail and maintain it correctly as
you do adds and removes. One thing that you will need to decide is
whether tail should point to the last element in the list or
to the element before the last element. (Note that head and
currentPred point to the element before the one that they really
mean.)
It is easy to introduce subtle bugs. Test your code carefully.
Please turn in a solution to the standard problem separately from the extra credit solution
(i.e., keep the two solutions as different files).
Solving the standard problem and then modifying it to use
tail is probably easier than starting with the tail instance variable.
Furthermore, by keeping them as two separate solutions,
you will not be penalized in your regular grade for errors in the
extra credit part.
SLL class.
SLL class.
SLL class if you did the extra credit.
(You should have one file with just the original assignment and
another for extra credit, because sometimes adding the extra credit breaks something
in the original assignment.)
Total of 70 points
| 10 | Modify add |
|---|---|
| 10 | Modify remove |
| 5 | Modify getLast |
| 5 | Modify addFirst |
| 5 | Modify isEmpty, hasCurrent,
and hasNext |
| 10 | Modify the other methods |
| 5 | Comments at top, explaining how your version represents the linked list. |
|---|---|
| 5 | Good names for methods, variables, parameters |
| 5 | Layout (blank lines, indentation, etc.) |
| 10 | A run demonstrating the correctness of the modified
SLL class. |
|---|
| 20 | Adding tail reference and updating efficiently and correctly |
|---|