|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.positional.AbstractPositionalCollection<E>
goldman.collection.positional.SinglyLinkedList<E>
public class SinglyLinkedList<E>
The simplest of the list-based positional collections, SinglyLinkedList
maintains a linked list where each list node only references the
next element in the list. Our implementation also maintains a reference to the last item in
the list. It is a tracked implementation.
When using a locator to iterate through the collection, in constant time a new
element can be added or the next element in the collection can be removed.
The primary drawback of using a singly linked list is that it takes O(p) time
to locate the element at position p for 0 ≤ p ≤ n-2.
Another weakness of SinglyLinkedList is that
it takes O(p) time to find the element that precedes the element at position p. Hence, the
retreat
method cannot be efficiently implemented.
Moreover, in order to efficiently remove a tracked
element from position p of the collection, it takes O(p) time.
Nested Class Summary | |
---|---|
static class |
SinglyLinkedList.ListItem<E>
The ListItem interface must be supported by any
class defining objects to be used in a singly linked list or a
doubly linked list. |
protected class |
SinglyLinkedList.Tracker
|
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection |
---|
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator |
Field Summary | |
---|---|
protected int |
CUTOFF
Quicksort is only applied to a subcollection with a size greater than the constant CUTOFF . |
protected SinglyLinkedList.ListItem<E> |
head
|
Fields inherited from class goldman.collection.AbstractCollection |
---|
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version |
Constructor Summary | |
---|---|
SinglyLinkedList()
Creates an empty collection |
Method Summary | |
---|---|
void |
add(E value)
Inserts it at the end of the positional collection. |
void |
add(int p,
E value)
Inserts value at position p
and increments the position number for the elements that were at
positions p to size-1 . |
protected void |
addItemLast(SinglyLinkedList.ListItem<E> x)
|
Locator<E> |
addTracked(E value)
Inserts value into the collection
at an arbitrary position. |
void |
bucketsort(Bucketizer<? super E> bucketizer)
Sorts this collection using bucket sort with the given bucketizer. |
void |
clear()
Removes all elements from the collection. |
boolean |
contains(E value)
This implementation for contains takes linear time, so it
is overridden by a more efficient method in most data structure
implementations. |
E |
get(int p)
Returns the element at position p. |
PositionalCollectionLocator<E> |
getLocator(E element)
Returns a locator that has been initialized to an element equivalent to target . |
protected SinglyLinkedList.ListItem<E> |
getPtr(int p)
|
protected SinglyLinkedList.ListItem<E> |
getPtrForPrevElement(E value)
|
void |
heapsort()
Uses the default comparator to order the elements |
void |
heapsort(Comparator<? super E> comp)
Sorts this collection with heap sort using the provided comparator. |
void |
heapsortImpl(Comparator sorter)
Is the implementation of heap sort |
protected PositionalCollectionLocator<E> |
insertAfter(SinglyLinkedList.ListItem<E> ptr,
E value)
Inserts a list item holding the new element after the list item referenced by ptr |
void |
insertionsort()
Sorts this collection with insertion sort using the default comparator. |
void |
insertionsort(Comparator<? super E> comp)
Sorts this collection with insertion sort using the default comparator. |
PositionalCollectionLocator<E> |
iterator()
Creates a new marker that is at FORE. |
PositionalCollectionLocator<E> |
iteratorAt(int pos)
Returns a new marker that is at the given position. |
PositionalCollectionLocator<E> |
iteratorAtEnd()
Creates a new marker that is at AFT. |
protected SinglyLinkedList.ListItem<E> |
merge(Comparator<? super E> comp,
SinglyLinkedList.ListItem<E> ptr1,
SinglyLinkedList.ListItem<E> ptr2)
Merges the two lists and |
void |
mergesort()
Uses the default comparator to order the elements |
void |
mergesort(Comparator<? super E> comp)
Sorts the list using mergesort |
protected SinglyLinkedList.ListItem<E> |
mergesortImpl(Comparator<? super E> comp,
int n,
SinglyLinkedList.ListItem<E> ptr)
|
protected void |
partition(SinglyLinkedList.ListItem<E> loc,
SinglyLinkedList.ListItem<E> beforeEnd,
goldman.collection.positional.SinglyLinkedList.Divider divider,
Comparator<? super E> comp)
Partitions the subcollection from loc +1 to beforeEnd +1 (inclusive) |
protected void |
placeListItemFirst(SinglyLinkedList.ListItem<E> x)
|
int |
positionOf(E value)
Returns the position of the first occurrence (if any) of an element equivalent to value . |
void |
quicksort()
Sorts this collection with quicksort using the default comparator. |
void |
quicksort(Comparator<? super E> comp)
Sorts the array in place |
void |
radixsort(Digitizer<? super E> digitizer)
Sorts this collection using radix sort with the provided digitizer. |
boolean |
remove(E value)
Removes the first element in the collection equivalent to value |
E |
remove(int p)
Removes the element at position p and decrements
the positions of
u_{p+1}, ..., u_{size -1} by one. |
E |
removeFirst()
Removes the element at position 0 and decrements the position for the elements that were at positions 1 to size-1 . |
E |
removeLast()
Removes the element at position size-1 |
protected E |
removeNext(SinglyLinkedList.ListItem<E> ptr)
|
void |
removeRange(int fromPos,
int toPos)
Requires 0 ≤ fromPos ≤ toPos < size . |
E |
repositionElementByRank(int r)
Modifies the positional collection so element in position r is in its proper sorted order when using the default comparator, and returns that element. |
E |
repositionElementByRank(int r,
Comparator<? super E> comp)
Modifies the positional collection so element in position r is in its proper sorted order when using the provided comparator, and returns this element. |
protected void |
resetList()
Update the list to be empty without changing the value of size |
E |
set(int p,
E value)
Replaces the element at position p by the given value , and
returns the element that had been in position p . |
protected void |
setLast(SinglyLinkedList.ListItem<E> last)
|
void |
swap(int a,
int b)
Swaps the elements held in positions a and b |
protected void |
swapAfter(SinglyLinkedList.ListItem<E> aPrev,
SinglyLinkedList.ListItem<E> bPrev)
|
void |
treesort()
Uses the default comparator to order the elements |
void |
treesort(Comparator<? super E> comp)
Sorts this collection with tree sort using the provided comparator. |
protected void |
treesortImpl(Comparator sorter)
Is the implementation of tree sort |
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.Collection |
---|
accept, addAll, checkRep, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Field Detail |
---|
protected SinglyLinkedList.ListItem<E> head
protected final int CUTOFF
CUTOFF
.
Constructor Detail |
---|
public SinglyLinkedList()
Method Detail |
---|
protected SinglyLinkedList.ListItem<E> getPtr(int p)
p
- a valid user position or -1
p
or the head sentinel if p = -1
public E get(int p)
PositionalCollection
size-1
(i.e., that the position exists in the collection).
Otherwise a PositionOutOfBoundsException
is thrown.
get
in interface PositionalCollection<E>
p
- a valid user position
p
PositionOutOfBoundsException
- the p is not a valid positionprotected SinglyLinkedList.ListItem<E> getPtrForPrevElement(E value)
value
- the target
value
.
The method returns null, if there is no equivalent element.public boolean contains(E value)
AbstractCollection
contains
takes linear time, so it
is overridden by a more efficient method in most data structure
implementations.
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
value
- the target
value
exists in the collectionpublic int positionOf(E value)
PositionalCollection
value
.
It throws a
NoSuchElementException
if there is no equivalent element.
(The Java collections return -1 when there is no element with
the given value, but throwing an exception will better enable a
problem to be detected if an application program did not consider the possibility of -1
being returned.)
positionOf
in interface PositionalCollection<E>
value
- the target
value
.
NoSuchElementException
- no element in the collection is equivalent
to value
protected void setLast(SinglyLinkedList.ListItem<E> last)
last
- the list element that is last in the collection.public E set(int p, E value)
PositionalCollection
p
by the given value
, and
returns the element that had been in position p
. It is required that 0 ≤
p
≤ size-1
. Otherwise, a PositionOutOfBoundsException
is thrown.
set
in interface PositionalCollection<E>
p
- a valid user positionvalue
- the element to put at position p
p
PositionOutOfBoundsException
- p
is not
a valid positionprotected void swapAfter(SinglyLinkedList.ListItem<E> aPrev, SinglyLinkedList.ListItem<E> bPrev)
aPrev
- a reference to list item before the one
to be swappedbPrev
- a reference to the list item before the other one
to be swappedpublic void swap(int a, int b)
a
and b
swap
in interface PositionalCollection<E>
a
- a valid positionb
- a valid position
PositionOutOfBoundsException
- either a
or b
is not a valid positionprotected PositionalCollectionLocator<E> insertAfter(SinglyLinkedList.ListItem<E> ptr, E value)
ptr
ptr
- a reference to a list
item in the collection (possibly the sentinel head)value
- the element to insert
public void add(int p, E value)
value
at position p
and increments the position number for the elements that were at
positions p
to size-1
.
add
in interface PositionalCollection<E>
p
- the position where the element is to be placedvalue
- the element to insert
PositionOutofBoundsException
- p
is neither size
nor a valid positionpublic void add(E value)
add
in interface Collection<E>
value
- the new elementpublic Locator<E> addTracked(E value)
value
into the collection
at an arbitrary position.
addTracked
in interface Tracked<E>
value
- the new element
protected E removeNext(SinglyLinkedList.ListItem<E> ptr)
ptr
- a reference to the list item (possibly the sentinel head item) preceding
the one to remove
ptr
references head
or a reachable
list item.
NoSuchElementException
- ptr
references the last list itempublic void removeRange(int fromPos, int toPos)
fromPos
≤ toPos
< size
.
It removes the elements at positions
fromPos
, ..., toPos
, inclusive,
from the collection and
decrements the positions of the
elements at positions toPos+1
to size-1
by
toPos-fromPos+1
(the number of elements
being removed)
removeRange
in interface PositionalCollection<E>
fromPos
- a valid positiontoPos
- a valid position
PositionOutOfBoundsException
- either of the arguments
is not a valid position
IllegalArgumentException
- fromPos
is greater
than toPos
public E remove(int p)
p
and decrements
the positions of
u_{p+1}, ..., u_{size
-1} by one.
remove
in interface PositionalCollection<E>
p
- a valid position
PositionOutOfBoundsException
- p
is not a valid
positionpublic E removeFirst()
1
to size-1
.
removeFirst
in interface PositionalCollection<E>
NoSuchElementException
- the collection is emptypublic E removeLast()
size-1
removeLast
in interface PositionalCollection<E>
NoSuchElementException
- the collection is emptypublic boolean remove(E value)
value
remove
in interface Collection<E>
value
- the element to remove
public void clear()
clear
in interface Collection<E>
clear
in class AbstractCollection<E>
public PositionalCollectionLocator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface PositionalCollection<E>
iterator
in interface Iterable<E>
iterator
in class AbstractPositionalCollection<E>
public PositionalCollectionLocator<E> iteratorAtEnd()
iteratorAtEnd
in interface PositionalCollection<E>
iteratorAtEnd
in class AbstractPositionalCollection<E>
public PositionalCollectionLocator<E> iteratorAt(int pos)
iteratorAt
in class AbstractPositionalCollection<E>
pos
- the user position of an element
NoSuchElementException
- the given position is not a valid user position.public PositionalCollectionLocator<E> getLocator(E element)
Collection
target
. Like the iterator
method, this method enables
navigation, but from a specified starting point. This method
throws a NoSuchElementException
if there is no equivalent element
in the collection.
getLocator
in interface Collection<E>
element
- the element to track
NoSuchElementException
- the given element is not in the collection.protected void addItemLast(SinglyLinkedList.ListItem<E> x)
x
- the item to be placed at the end of the listpublic void insertionsort()
PositionalCollection
insertionsort
in interface PositionalCollection<E>
public void insertionsort(Comparator<? super E> comp)
PositionalCollection
insertionsort
in interface PositionalCollection<E>
public void mergesort()
mergesort
in interface PositionalCollection<E>
public void mergesort(Comparator<? super E> comp)
mergesort
in interface PositionalCollection<E>
comp
- the comparator
to use to order the elementsprotected SinglyLinkedList.ListItem<E> mergesortImpl(Comparator<? super E> comp, int n, SinglyLinkedList.ListItem<E> ptr)
comp
- the comparator
to use to order the elementsn
- the number of elements in this portion
of this listptr
- the pointer to the first item in the list
protected SinglyLinkedList.ListItem<E> merge(Comparator<? super E> comp, SinglyLinkedList.ListItem<E> ptr1, SinglyLinkedList.ListItem<E> ptr2)
comp
- the comparator
to use to order the elementsptr1
- the pointer to the first item in the first list
to mergeptr2
- the pointer to the first item in the second list to merge
protected void resetList()
size
public void heapsort()
heapsort
in interface PositionalCollection<E>
public void heapsort(Comparator<? super E> comp)
PositionalCollection
heapsort
in interface PositionalCollection<E>
comp
- the comparator
to use to order the elementspublic void heapsortImpl(Comparator sorter)
sorter
- the comparator defined
over list items to usepublic void treesort()
treesort
in interface PositionalCollection<E>
public void treesort(Comparator<? super E> comp)
PositionalCollection
treesort
in interface PositionalCollection<E>
comp
- the comparator
to use to order the elementsprotected void treesortImpl(Comparator sorter)
sorter
- the comparator to usepublic void quicksort()
PositionalCollection
quicksort
in interface PositionalCollection<E>
public void quicksort(Comparator<? super E> comp)
quicksort
in interface PositionalCollection<E>
comp
- the comparator
to use to order the elements in the positional collectionprotected void partition(SinglyLinkedList.ListItem<E> loc, SinglyLinkedList.ListItem<E> beforeEnd, goldman.collection.positional.SinglyLinkedList.Divider divider, Comparator<? super E> comp)
loc
+1 to beforeEnd
+1 (inclusive)
loc
- a reference to the list item that references the start of
the subcollection to partitionbeforeEnd
- a reference to the second to last list item in the subcollection to partitionprotected void placeListItemFirst(SinglyLinkedList.ListItem<E> x)
x
- a
reference to the list item to insert to the front of the listpublic void radixsort(Digitizer<? super E> digitizer)
PositionalCollection
radixsort
in interface PositionalCollection<E>
digitizer
- the digitizer to use
in radix sortpublic void bucketsort(Bucketizer<? super E> bucketizer)
PositionalCollection
bucketsort
in interface PositionalCollection<E>
bucketizer
- the bucketizer
to usepublic E repositionElementByRank(int r)
PositionalCollection
repositionElementByRank
in interface PositionalCollection<E>
r
- the rank of the desired element in the sorted order
of the elements
r
when using the default comparator
PositionOutOfBoundsException
- r
is not a valid positionpublic E repositionElementByRank(int r, Comparator<? super E> comp)
PositionalCollection
repositionElementByRank
in interface PositionalCollection<E>
r
- the rank of the desired element in the sorted order of the elementscomp
- the comparator to use for determining the order
r
when using the given comparator
NoSuchElementException
- the collection is empty
or r
is not a valid position
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |