CODEWITHSUNDEEP
javalistdata-structurescircular-list
Joker
Joker

Reputation: 11150

Lack of certainty in Circular linked list and Iterator API

I am trying to create a circular linked list implementation using 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.

Upvotes: 1

Views: 98

Answers (1)

Harmlezz
Harmlezz

Reputation: 8078

In my opinion this is neither a flaw in the Collections API nor in the way the contracts for both methods hasNext and hasPrevious are defined.

The problem steams from the way you think about your circular list:

  • the list has a fixed size of elements and hence an iterator should be able to order them in a way which has a start and an end.
  • it does not matter how you organized your elements in the list for answering hasNext and hasPrevious. The ordering does only define when which element is returned.

If your iterator returns the same element (identity in terms of absolute position in your list) then your iterator implementation is wrong.

You have to decouple the idea of how to order your elements from how many elements your list contains. The number of elements in the list is defined by the result of size. Hence, if navigating only forward, hasNext should answer with true exactly size times. The same is true for hasPrevious when navigating backwards after getting false as answer from hasNext.

Upvotes: 1

Related Questions