Circular Double Linked Lists and ListIterator

CircularDoubleLinkedList<E>

Working with positive and negative indices

• void add(int index, E data), E get(int index), E remove(int index) should work with positive and negative indices

Positive index

Negative index

Working with indices that would normally be out of bounds

• void add(int index, E data), E get(int index), E remove(int index) should work with indices that would normally go out of bounds
• For example, calling get on the following list with an index of 10

= index % size
= 10 % 6
= 4

And what of large negative values? Say -13?

= index % size
= -13 % 6
= -1

Interface ListIterator<E>

An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list. A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). An iterator for a list of length n has n+1 possible cursor positions, as illustrated by the carets (^) below:

                      Element(0)   Element(1)   Element(2)   ... Element(n-1)
   cursor positions: ^           ^            ^            ^                  ^

void add(E e)

Inserts the specified element into the list (optional operation). The element is inserted immediately before the element that would be returned by next(), if any, and after the element that would be returned by previous(), if any. (If the list contains no elements, the new element becomes the sole element on the list.) The new element is inserted before the implicit cursor: a subsequent call to next would be unaffected, and a subsequent call to previous would return the new element. (This call increases by one the value that would be returned by a call to nextIndex or previousIndex.)

Details of add

• The element is inserted immediately before the element that would be returned by next(), if any
• The element is inserted immediately after the element that would be returned by previous(), if any
• Special case is handled if list is empty
• Increases the size by 1
• After an add, a call to next() would be unaffected
• After an add, a call to previous() would return the new element
• Increases the value of nextIndex() and previousIndex() by 1

Exceptions thrown by add

• Do not need to implement exceptions for add

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.)

Details of hasNext()

• For a the Josephus problem, should always return true unless list is empty

Exceptions throw by hasNext()

• None

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.)

Details of hasPrevious()

• For a the Josephus problem, should always return true unless list is empty

Exceptions throw by hasPrevious()

• None

E next()

Returns the next element in the list and advances the cursor position. This method may be called repeatedly to iterate through the list, or intermixed with calls to previous() to go back and forth. (Note that alternating calls to next and previous will return the same element repeatedly.)

Details of next()

• May be called as often as you like
• Returns the data from within the node, and advances the cursor position
• Alternating calls between next() and previous() will return the same element repeatedly

Exceptions thrown by next()

• A NoSuchElementException should be thrown if the iteration has no next element
• This occurs in the Josephus problem if the list is empty and a call to next() is made

E previous()

Returns the previous element in the list and moves the cursor position backwards. This method may be called repeatedly to iterate through the list backwards, or intermixed with calls to next() to go back and forth. (Note that alternating calls to next and previous will return the same element repeatedly.)

Details of previous()

• May be called as often as you like
• Returns the data from within the node, and moves the cursor backwards
• Alternating calls between next() and previous() will return the same element repeatedly

Exceptions thrown by previous()

• A NoSuchElementException should be thrown if the iteration has no previous element
• This occurs in the Josephus problem if the list is empty and a call to previous() is made

int nextIndex()

Returns the index of the element that would be returned by a subsequent call to next(). (Returns list size if the list iterator is at the end of the list.)

Details of nextIndex()

• Returns the index of the element that would be returned by a subsequent call to next()

Exceptions thrown by nextIndex()

• None

int previousIndex()

Returns the index of the element that would be returned by a subsequent call to previous(). (Returns -1 if the list iterator is at the beginning of the list.)

Details of previousIndex()

• Returns the index of the element that would be returned by a subsequent call to previous()
• Always one less than nextIndex()
• Can simply use the value (nextIndex() - 1)

Exceptions thrown by nextIndex()

• None

void remove()

Removes from the list the last element that was returned by next() or previous() (optional operation). This call can only be made once per call to next or previous. It can be made only if add(E) has not been called after the last call to next or previous.

Details of remove()

• Removes the last element that was returned by next() or previous()
• Can only be called once per call to next() or previous()
• Can not be called if add() was called after a call to next() or previous()

Exceptions thrown by remove()

• IllegalStateException if neither next() nor previous() have been called
• IllegalStateException if remove() has already been called since the last call to next() or previous()
• IllegalStateException if add() has already been called since the last call to next() or previous()

void set(E e)

Replaces the last element returned by next() or previous() with the specified element (optional operation). This call can be made only if neither remove() nor add(E) have been called after the last call to next or previous.

Details of set()

• Replaces the last element returned by next() or previous()
• Can not be called if remove() has been called since last call to next() or previous()
• Can not be called if add() has been called since last call to next() or previous()

Exceptions thrown by set()

• IllegalStateException if neither next() nor previous() have been called
• IllegalStateException if remove() has been called after the last call to next() or previous()
• IllegalStateException if add() has been called after the last call to next() or previous()

Tips for working with ListIterator

• Keep track of the node that was last returned by next() or previous() (maybe call it lastReturned)
• lastReturned could be used by add(), set(), remove()
• Update lastReturned to point to null, if remove() or add() have been called
• In set() and remove(), if lastReturned is null, then you most likely should throw an IllegalStateException
• Keep track of nextIndex, and calculate previousIndex from nextIndex

Helpful links:

• DoublyLinkedList.java

• CircularDoublyLinkedList (for Josephus problem)