A limitation of standard lists is that you can only access the elements only from the front. Sometimes, we want to be able to access the elements from both ends. To accomplish that with the lists we've discussed so far, to access the last element takes O(n) time. We would like to have a data structure that has constant-time access at both ends.
In class, you were introduced the doubly-linked lists.
In comparison, our standard lists are sometimes called
singly-linked lists.
The implementation of the doubly-linked
CList
used the same basic idea as our previous singly-linked
LRStruct: adding indirection to the rest of the list
via a "node". Indirection allows us to modify the rest of the list
(and its empty/non-empty type).
The difference here is that we need not only to keep track of the
rest of the list, but also previous part of the list.
Furthermore, class described a version of doubly-linked lists that were circular. I.e., we essentially glue the two ends together into a circle. As a result, the list has no "end" anymore. Instead, we have two independent list "heads", one for working clockwise, and one for working counterclockwise.
So how do we use CList?
It is convenient to use the Visitor Pattern.
The basic data structure is complicated enough already.
We don't want to further complicate it by adding any more methods to
it than necessary.
Since we essentially have a list on which we can go either way,
we'll have two kinds of visitors: clockwise and counterclockwise.
We need a hook for each one:
executeClockwise() and
executeCounterClockwise().
But when does a visitor algorithm stop, if there's no "end" element?
We want to stop when we return to where we started.
Each visitor will keep track of that element; thus, the visitor
will have a data field, and not be a singleton.
(Alternatively, we could have added a parameter to the hooks.)
You will probably want to use CList on your next project.
CLists
Each algorithm is obligated to implement
IAlgo.
It probably uses only one of
executeClockwise() and
executeCounterClockwise() to look at all the previous and
next elements, respectively, although it could use both to look at
the list elements in some complicated way.
The constructor should take a starting/stopping element as an
argument, which we'll test against (with ==)
to know when to stop.
Our goal will be to find a maximal element (assume we're working
with Numbers) and whether it is closer clockwise or
counterclockwise.
Write and test a visitor to find the maximal element. Naturally, it doesn't matter whether you calculate this in a clockwise or counterclockwise direction. We've provided a stub to get you started.
Write and test two visitors, one each to find the distance in each direction to the maximal element.
Write a method to tie these pieces together to solve the original problem. For simplicity, this can just be a static method in your client.