A List Implementation that satisfies the contract, yet breaks standard implementations!

[Ant...]

I have just been trying to create a circular linked list implementation
of the List interface, and have noticed an interesting side effect.

Though the CircularLinkedList satisfies the List contract, it breaks the
other currently implemented collection classes!

The problem is this - the ListIterator interface gives the following
contract for the hasNext() and hasPrevious() methods:

public boolean hasNext()

Returns true if this list iterator has more elements when
traversing the list in the forward direction. (In other words, returns
true if next would return an element rather than throwing an exception.)

public boolean hasPrevious()

Returns true if this list iterator has more elements when
traversing the list in the reverse direction. (In other words, returns
true if previous would return an element rather than throwing an exception.)

Now in a circular list, each of these should by the contract return
false if and only if the List is empty. The problem shows itself when
you try to add a circular list with the appropriate list iterator to
another Collection using the addAll() method - the method uses
hasNext() to constrain the iteration as it adds each element. Hence the
loop never terminates!

I am currently thinking of breaking the contract of either the
ListIterator, to make the list look like a linked list if you are
looking at the hasNext() method, or creating a subclass of the iterator
with hasNext overridden to be returned by the iterator() method.

Two questions:
1) Is there a better way of doing this without breaking the Iterator or
ListIterator contracts?
2) Does anyone else think that this is a flaw in the AbstractCollection
class (which is where the inherited behaviour comes from). Note that
some collections do perform the adding in a more robust way, by calling
the toArray() method of the collection to be added, and adding each
element of the array.

Cheers,

Anthony Roy

 

[Matt Humphrey]

I have just been trying to create a circular linked list implementation
of the List interface, and have noticed an interesting side effect.

Though the CircularLinkedList satisfies the List contract, it breaks the
other currently implemented collection classes!

The problem is this - the ListIterator interface gives the following
contract for the hasNext() and hasPrevious() methods:

public boolean hasNext()

Returns true if this list iterator has more elements when
traversing the list in the forward direction. (In other words, returns
true if next would return an element rather than throwing an exception.)

public boolean hasPrevious()

Returns true if this list iterator has more elements when
traversing the list in the reverse direction. (In other words, returns
true if previous would return an element rather than throwing an exception.)

Now in a circular list, each of these should by the contract return
false if and only if the List is empty.

I don't intend to make light of your design problem, but the purpose of an
iterator is to be able to sequentially retrieve all your elements. Since we
know that iterators already have a state memory of where they are in the
list, there's no reason that the iterator for a circular list would not
remember where it started and stop there (return false) when it got back
there again. It is best if the circularity of the list is accessed through
add-on methods (e.g. an endless iterator) rather than through those defined
by the interface.

The real question is: what are you trying to accomplish? What special
function do you need from a circular list that an ordinary one cannot
provide?

Cheers,
Matt Humphrey (e-mail address removed) http://www.iviz.com/

 

[Chris Smith]

I have just been trying to create a circular linked list implementation
of the List interface, and have noticed an interesting side effect.

Though the CircularLinkedList satisfies the List contract, it breaks the
other currently implemented collection classes!

Whether or not you can construe language in such a way that your
circular list meets the language of the description of certain
operations, your data structure is *clearly* not a java.util.List. You
should define your own interface to represent the circular list, rather
than trying to reuse another interface that's only half-appropriate.
(Incidentally, I would argue that the API specification clearly tells
you this; I wouldn't call a circular linked list data structure
"ordered" since it has no unique global order.)

All of your problems arise because you're abusing this well-specified
interface to describe a data structure that doesn't meet its
abstraction.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[ak]

CircularList is endless but it have start position (the first call to
nextElement() returns item at first pos) and end position.
End position is the position used for last addElement(Object o) call.

Hope this helps

ak

 

[John C. Bollinger]

I have just been trying to create a circular linked list implementation
of the List interface, and have noticed an interesting side effect.

Though the CircularLinkedList satisfies the List contract, it breaks the
other currently implemented collection classes!

I disagree that your class satisfies the List contract, and I assert
that that is why you cannot create a ListIterator implementation that
obeys its contract. The very first sentence of List's API documentation
describes a list as "An ordered collection (also known as a sequence)."
Your implementation does not satisfy this description, because every
element is both before and after every other element. There is local
order, but no global order. Moreover, if you want to be technical, your
class also does not satisfy its contract in that its listIterator() and
listIterator(int) methods do not return a correct ListIterator -- a
correct Iterator returns each element exactly once (as you proceed in a
forward direction).

The problem is this - the ListIterator interface gives the following
contract for the hasNext() and hasPrevious() methods:

public boolean hasNext()

Returns true if this list iterator has more elements when
traversing the list in the forward direction. (In other words, returns
true if next would return an element rather than throwing an exception.)

public boolean hasPrevious()

Returns true if this list iterator has more elements when
traversing the list in the reverse direction. (In other words, returns
true if previous would return an element rather than throwing an exception.)

Now in a circular list, each of these should by the contract return
false if and only if the List is empty. The problem shows itself when
you try to add a circular list with the appropriate list iterator to
another Collection using the addAll() method - the method uses
hasNext() to constrain the iteration as it adds each element. Hence the
loop never terminates!

And that works fine with any correct Iterator implementation.

I am currently thinking of breaking the contract

Shame on you!

You are trying to shoehorn your circular list into the wrong
abstraction, hence your problems. Breaking contracts is likely to cause
you grief later (as it's causing you grief now), so find a
better-matching abstraction instead.

of either the
ListIterator, to make the list look like a linked list if you are
looking at the hasNext() method, or creating a subclass of the iterator
with hasNext overridden to be returned by the iterator() method.

I don't have any clue what you mean by that second alternative, at least
if it means anything different from the first one.

Two questions:
1) Is there a better way of doing this without breaking the Iterator or
ListIterator contracts?

As I said, choose a better abstraction. This type of collection could
be a direct implementation of Collection. Alternatively, create a new
type of collection by defining a suitable Collection subinterface, and
write your class to that subinterface. The Iterator returned by the
iterator() method may wrap around, if desired, but it must stop when it
gets back to the starting point of the iteration.

ListIterator is not an alternative for you, but you could define a
similar CircularIterator suitable for your collection.

2) Does anyone else think that this is a flaw in the AbstractCollection
class (which is where the inherited behaviour comes from). Note that
some collections do perform the adding in a more robust way, by calling
the toArray() method of the collection to be added, and adding each
element of the array.

No. You have violated the Collection contract by returning an incorrect
Iterator (one that returns the same elements more than once). If you
obey the relevant contracts then you will not have problems of this
kind. Furthermore, I am not persuaded that an addAll implementation
that uses toArray() is necessarily more robust. It is quite likely more
costly for many kinds of collections than is iterating.


John Bollinger
(e-mail address removed)

 

[Thomas G. Marshall]

I don't intend to make light of your design problem, but the purpose
of an iterator is to be able to sequentially retrieve all your
elements. Since we know that iterators already have a state memory
of where they are in the list, there's no reason that the iterator
for a circular list would not remember where it started and stop
there (return false) when it got back there again.

Correct, but that depends upon the following: All iterators have a notion of
"has more". Does "has more" mean that there are simply elements available
(perhaps they are allowed to be removed /during/ iteration though usually
not the case), or does it mean that it has retreived all the elements once
already.

 

[Ant...]

Having mulled over your various responses, I come to the conclusion
that it is not a list at all. It has been correctly pointed out that
the circular list does not have a total ordering (the 'order' is
symmetric where even a partial order must be assymmetric).

Thanks for the comments! I think I will go back to my
(non-List-implementing) version of the CircularList.

Cheers,

Ant...