goldman.collection.positional
Class DoublyLinkedList<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.positional.AbstractPositionalCollection<E>
          extended by goldman.collection.positional.SinglyLinkedList<E>
              extended by goldman.collection.positional.DoublyLinkedList<E>
All Implemented Interfaces:
Collection<E>, PositionalCollection<E>, Tracked<E>, Iterable<E>

public class DoublyLinkedList<E>
extends SinglyLinkedList<E>
implements PositionalCollection<E>

The doubly linked list is the only positional collection data structure that provides amortized constant time methods for all of the PositionalCollectionLocator methods except getCurrentPosition. Furthermore, it is a tracked implementation. Since a doubly linked list maintains a pointer from each element to the one that precedes it, an element that is known to be located near the end of the collection can be efficiently located by traversing backwards from the tail. This list-based data structure extends SinglyLinkedList to have each list item also maintain a reference to the previous list node. The primary advantage of a doubly linked list, over all of the other data structures, is that through a locator an element can be added or removed from the middle portion of the list in constant time. Also, it takes O(min(p+1,n-p)) time, instead of O(p) time for SinglyLinkedList to access the element at position p without the use of a locator. Furthermore, the retreat method takes constant time. The primary disadvantage of DoublyLinkedList is that including a previous reference adds space overhead and all methods that modify the structure of the list must adjust twice as many references.


Nested Class Summary
protected static class DoublyLinkedList.DLListItem<E>
           
 
Nested classes/interfaces inherited from class goldman.collection.positional.SinglyLinkedList
SinglyLinkedList.ListItem<E>, SinglyLinkedList.Tracker
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
 
Fields inherited from class goldman.collection.positional.SinglyLinkedList
CUTOFF, head
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version
 
Constructor Summary
DoublyLinkedList()
           
 
Method Summary
protected  SinglyLinkedList.ListItem<E> getLast()
           
protected  DoublyLinkedList.DLListItem<E> getPtr(int p)
           
protected  SinglyLinkedList.ListItem<E> getPtrForPrevItem(SinglyLinkedList.ListItem<E> ptr)
           
protected  SinglyLinkedList.ListItem<E> getTail()
           
protected  DoublyLinkedList.DLListItem<E> newListItem(E value)
           
protected  void setLast(SinglyLinkedList.ListItem<E> ptr)
           
 
Methods inherited from class goldman.collection.positional.SinglyLinkedList
add, add, addItemLast, addTracked, bucketsort, clear, contains, get, getLocator, getPtrForPrevElement, heapsort, heapsort, heapsortImpl, insertAfter, insertionsort, insertionsort, iterator, iteratorAt, iteratorAtEnd, merge, mergesort, mergesort, mergesortImpl, partition, placeListItemFirst, positionOf, quicksort, quicksort, radixsort, remove, remove, removeFirst, removeLast, removeNext, removeRange, repositionElementByRank, repositionElementByRank, resetList, set, swap, swapAfter, treesort, treesort, treesortImpl
 
Methods inherited from class goldman.collection.positional.AbstractPositionalCollection
addFirst, addLast, toString
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, traverseForVisitor, trimToSize, writeElements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.positional.PositionalCollection
add, addFirst, addLast, bucketsort, get, heapsort, heapsort, insertionsort, insertionsort, iterator, iteratorAtEnd, mergesort, mergesort, positionOf, quicksort, quicksort, radixsort, remove, removeFirst, removeLast, removeRange, repositionElementByRank, repositionElementByRank, set, swap, treesort, treesort
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getLocator, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize
 

Constructor Detail

DoublyLinkedList

public DoublyLinkedList()
Method Detail

newListItem

protected DoublyLinkedList.DLListItem<E> newListItem(E value)
Parameters:
value - the desired element
Returns:
a new DLListItem holding the given element.

getTail

protected SinglyLinkedList.ListItem<E> getTail()

getLast

protected SinglyLinkedList.ListItem<E> getLast()
Returns:
a reference to the last item in the list.

getPtr

protected DoublyLinkedList.DLListItem<E> getPtr(int p)
Overrides:
getPtr in class SinglyLinkedList<E>
Parameters:
p - a valid user position or -1
Returns:
a reference to the element in the collection at position p or the head sentinel if p is -1

getPtrForPrevItem

protected SinglyLinkedList.ListItem<E> getPtrForPrevItem(SinglyLinkedList.ListItem<E> ptr)
Parameters:
ptr - reference to an element in the collection
REQUIRES: ptr is a pointer to an element of the collection.
Returns:
a reference to the list item just before that referenced by ptr (possibly the head sentinel).

setLast

protected void setLast(SinglyLinkedList.ListItem<E> ptr)
Overrides:
setLast in class SinglyLinkedList<E>
Parameters:
ptr - a reference to the list item that is now the last one in the list