goldman.collection.positional
Class DoublyLinkedList<E>
java.lang.Object
goldman.collection.AbstractCollection<E>
goldman.collection.positional.AbstractPositionalCollection<E>
goldman.collection.positional.SinglyLinkedList<E>
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.
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.AbstractCollection |
accept, addAll, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, traverseForVisitor, trimToSize, writeElements |
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 |
DoublyLinkedList
public DoublyLinkedList()
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