T
- the type of all elements in the NodeList
public class NodeList<T>
extends java.util.AbstractSequentialList<T>
implements java.util.Deque<T>
LinkedList
,
but publicly exposes its NodeList.Node
structure. This allows for O(1) navigation,
insertion, and removal at arbitrary positions for which NodeList.Node
instances
have already been obtained, rather than performing an O(n) lookup each time.
Java Collections Framework features, including index access and direct access
to element values stored in NodeList.Node
, are provided by implementing
Deque
and extending AbstractSequentialList
. Iterators “fail fast”
by checking for concurrent modifications by non-iterator methods.
Modifier and Type | Class and Description |
---|---|
static class |
NodeList.Node<T>
Provides a generic node within a
NodeList . |
Constructor and Description |
---|
NodeList()
Creates an empty
NodeList . |
NodeList(java.util.Collection<? extends T> collection)
Creates a
NodeList containing the elements of the specified Collection . |
Modifier and Type | Method and Description |
---|---|
void |
add(int index,
T value)
Adds the specified element at the specified position in the
NodeList . |
boolean |
add(T value)
Adds the specified element at the end of the
NodeList . |
void |
addAfter(NodeList.Node<T> node,
T value)
Adds the specified element after the specified
NodeList.Node . |
boolean |
addAll(int index,
java.util.Collection<? extends T> collection)
Adds all specified elements at the specified position in the
NodeList . |
void |
addBefore(NodeList.Node<T> node,
T value)
Adds the specified element before the specified
NodeList.Node . |
void |
addFirst(T value)
Adds the specified element at the start of the
NodeList . |
void |
addLast(T value)
Adds the specified element at the end of the
NodeList . |
void |
clear()
Removes all elements from the
NodeList . |
boolean |
contains(java.lang.Object obj)
Determines whether the
NodeList contains the specified element. |
int |
countNodes()
Counts the number of elements in the
NodeList . |
java.util.Iterator<T> |
descendingIterator()
Returns an
Iterator over the elements in the NodeList
in reverse order, starting after the last element. |
T |
element()
Retrieves, but does not remove, the first element in the
NodeList . |
NodeList.Node<T> |
findFirstNode(T value)
Finds the first
NodeList.Node in the NodeList that contains the specified element. |
NodeList.Node<T> |
findLastNode(T value)
Finds the last
NodeList.Node in the NodeList that contains the specified element. |
NodeList.Node<T> |
first()
Gets the first
NodeList.Node in the NodeList . |
T |
get(int index)
Gets the element at the specified position in the
NodeList . |
T |
getFirst()
Retrieves, but does not remove, the first element in the
NodeList . |
T |
getLast()
Retrieves, but does not remove, the last element in the
NodeList . |
NodeList.Node<T> |
getNode(int index)
Gets the
NodeList.Node at the specified position in the NodeList . |
boolean |
isEmpty()
Indicates whether the
NodeList is empty. |
NodeList.Node<T> |
last()
Gets the last
NodeList.Node in the NodeList . |
java.util.ListIterator<T> |
listIterator(int index)
Returns a
ListIterator over the elements in the NodeList ,
starting at the specified position. |
boolean |
offer(T value)
Adds the specified element at the end of the
NodeList . |
boolean |
offerFirst(T value)
Adds the specified element at the start of the
NodeList . |
boolean |
offerLast(T value)
Adds the specified element at the end of the
NodeList . |
T |
peek()
Retrieves, but does not remove, the first element in the
NodeList . |
T |
peekFirst()
Retrieves, but does not remove, the first element in the
NodeList . |
T |
peekLast()
Retrieves, but does not remove, the last element in the
NodeList . |
T |
poll()
Retrieves and removes the first element in the
NodeList . |
T |
pollFirst()
Retrieves and removes the first element in the
NodeList . |
T |
pollLast()
Retrieves and removes the last element in the
NodeList . |
T |
pop()
Retrieves and removes the first element from the
NodeList . |
void |
push(T value)
Adds the specified element at the start of the
NodeList . |
T |
remove()
Retrieves and removes the first element from the
NodeList . |
T |
remove(int index)
Removes the element at the specified position in the
NodeList . |
void |
remove(NodeList.Node<T> node)
Removes the specified
NodeList.Node from the NodeList . |
boolean |
remove(java.lang.Object obj)
Removes the first occurence of the specified element from the
NodeList . |
T |
removeFirst()
Retrieves and removes the first element from the
NodeList . |
boolean |
removeFirstOccurrence(java.lang.Object obj)
Removes the first occurence of the specified element from the
NodeList . |
T |
removeLast()
Retrieves and removes the last element from the
NodeList . |
boolean |
removeLastOccurrence(java.lang.Object obj)
Removes the last occurence of the specified element from the
NodeList . |
protected void |
removeRange(int fromIndex,
int toIndex)
Removes all elements within the specified index range from the
NodeList . |
T |
set(int index,
T value)
Sets the specified position in the
NodeList to the specified element. |
int |
size()
Gets the number of elements in the
NodeList . |
equals, hashCode, indexOf, lastIndexOf, listIterator, subList
addAll, containsAll, removeAll, retainAll, toArray, toArray, toString
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
public NodeList()
NodeList
.public NodeList(java.util.Collection<? extends T> collection)
NodeList
containing the elements of the specified Collection
.
All collection
elements are added in iteration order.collection
- the Collection
whose elements to addjava.lang.NullPointerException
- if collection
is null
or contains any null
elementspublic NodeList.Node<T> first()
NodeList.Node
in the NodeList
.
This is an O(1) operation.NodeList.Node
in the NodeList
,
or null
if the NodeList
is emptypublic NodeList.Node<T> last()
NodeList.Node
in the NodeList
.
This is an O(1) operation.NodeList.Node
in the NodeList
,
or null
if the NodeList
is emptypublic void addAfter(NodeList.Node<T> node, T value)
NodeList.Node
.
This is an O(1) operation.node
- the NodeList.Node
after which to add value
value
- the element to addjava.lang.IllegalArgumentException
- if node
is not part of the NodeList
java.lang.NullPointerException
- if node
or value
is null
public void addBefore(NodeList.Node<T> node, T value)
NodeList.Node
.
This is an O(1) operation.node
- the NodeList.Node
before which to add value
value
- the element to addjava.lang.IllegalArgumentException
- if node
is not part of the NodeList
java.lang.NullPointerException
- if node
or value
is null
public int countNodes()
NodeList
.
This is an O(n) operation, counting each NodeList.Node
from first()
to last()
. Intended for testing the internally tracked size()
.NodeList
public NodeList.Node<T> findFirstNode(T value)
NodeList.Node
in the NodeList
that contains the specified element.
Searches the NodeList
from first()
to last()
, using
Object.equals(java.lang.Object)
to compare elements. This is an O(n) operation.value
- the element to searchNodeList.Node
in the NodeList
whose NodeList.Node.value()
equals value
, or null
if no such NodeList.Node
existsjava.lang.NullPointerException
- if value
is null
public NodeList.Node<T> findLastNode(T value)
NodeList.Node
in the NodeList
that contains the specified element.
Searches the NodeList
from last()
to first()
, using
Object.equals(java.lang.Object)
to compare elements. This is an O(n) operation.value
- the element to searchNodeList.Node
in the NodeList
whose NodeList.Node.value()
equals value
, or null
if no such NodeList.Node
existsjava.lang.NullPointerException
- if value
is null
public NodeList.Node<T> getNode(int index)
NodeList.Node
at the specified position in the NodeList
.
Uses the internally tracked size()
to search from last()
rather than first()
if index
is greater than size()
/2.
This is an O(min(index
, size()
– index
)) operation.index
- the index of the NodeList.Node
to getNodeList.Node
at index
java.lang.IndexOutOfBoundsException
- if index
is less than zero,
or equal to or greater than size()
public void remove(NodeList.Node<T> node)
NodeList.Node
from the NodeList
.
This is an O(1) operation.node
- the NodeList.Node
to removejava.lang.IllegalArgumentException
- if node
is not part of the NodeList
java.lang.NullPointerException
- if node
is null
public boolean add(T value)
NodeList
.
Calls addLast(T)
with value
. This is an O(1) operation.add
in interface java.util.Collection<T>
add
in interface java.util.Deque<T>
add
in interface java.util.List<T>
add
in interface java.util.Queue<T>
add
in class java.util.AbstractList<T>
value
- the element to addjava.lang.NullPointerException
- if value
is null
public void add(int index, T value)
NodeList
.
This is an O(1) operation if index
equals size()
in which case
value
is added at the end. Otherwise, this is an O(index
)
operation, as described in getNode(int)
.add
in interface java.util.List<T>
add
in class java.util.AbstractSequentialList<T>
index
- the index at which to add value
value
- the element to add at index
java.lang.IndexOutOfBoundsException
- if index
is less than zero or greater than size()
java.lang.NullPointerException
- if value
is null
public boolean addAll(int index, java.util.Collection<? extends T> collection)
NodeList
.
This is an O(m) operation if index
equals size()
in which case
collection
is added at the end. Otherwise, this is an O(index
+ m)
operation, as described in getNode(int)
. Here m represents the size of the
collection
. All collection
elements are added in iteration order.addAll
in interface java.util.List<T>
addAll
in class java.util.AbstractSequentialList<T>
index
- the index at which to add collection
collection
- the Collection
to add at index
true
if collection
contains any elements, else false
java.lang.IndexOutOfBoundsException
- if index
is less than zero or greater than size()
java.lang.NullPointerException
- if collection
is null
or contains any null
elementspublic void clear()
public boolean contains(java.lang.Object obj)
NodeList
contains the specified element.
Attempts to cast obj
to T, then calls findFirstNode(T)
and succeeds exactly if a NodeList.Node
was found. This is an O(n) operation.contains
in interface java.util.Collection<T>
contains
in interface java.util.Deque<T>
contains
in interface java.util.List<T>
contains
in class java.util.AbstractCollection<T>
obj
- the element to examinetrue
if obj
was found, else false
java.lang.ClassCastException
- if obj
cannot be cast to Tjava.lang.NullPointerException
- if obj
is null
public T get(int index)
NodeList
.
This is an O(index
) operation, as described in getNode(int)
.public boolean isEmpty()
NodeList
is empty.
This is an O(1) operation.public java.util.ListIterator<T> listIterator(int index)
ListIterator
over the elements in the NodeList
,
starting at the specified position.
The ListIterator
is positioned after the last element
if index
equals size()
. Otherwise, this is an
O(index
) operation, as described in getNode(int)
.listIterator
in interface java.util.List<T>
listIterator
in class java.util.AbstractSequentialList<T>
index
- the index of the first element to be returned by ListIterator.next()
ListIterator
for the NodeList
, starting at index
java.lang.IndexOutOfBoundsException
- if index
is less than zero or greater than size()
public T remove(int index)
NodeList
.
This is an O(index
) operation, as described in getNode(int)
.remove
in interface java.util.List<T>
remove
in class java.util.AbstractSequentialList<T>
index
- the index of the element to removeindex
java.lang.IndexOutOfBoundsException
- if index
is less than zero,
or equal to or greater than size()
public boolean remove(java.lang.Object obj)
NodeList
.
Returns removeFirstOccurrence(java.lang.Object)
. This is an O(n) operation.remove
in interface java.util.Collection<T>
remove
in interface java.util.Deque<T>
remove
in interface java.util.List<T>
remove
in class java.util.AbstractCollection<T>
obj
- the element to removetrue
if obj
was found and removed, else false
java.lang.ClassCastException
- if obj
cannot be cast to Tjava.lang.NullPointerException
- if obj
is null
protected void removeRange(int fromIndex, int toIndex)
NodeList
.
This is an O(index
) operation, as described in getNode(int)
,
followed by an O(m) operation where m is the number of elements to remove.removeRange
in class java.util.AbstractList<T>
fromIndex
- the index of the first element to remove (inclusive)toIndex
- the index of the last element to remove (exclusive)java.lang.IndexOutOfBoundsException
- if fromIndex
or toIndex
is less than zero or greater than size()
public T set(int index, T value)
NodeList
to the specified element.
This is an O(index
) operation, as described in getNode(int)
.
Calling set
will not cause existing iterators to throw
ConcurrentModificationException
as it involves no structural change.set
in interface java.util.List<T>
set
in class java.util.AbstractSequentialList<T>
index
- the index at which to store value
value
- the element to store at index
index
java.lang.IndexOutOfBoundsException
- if index
is less than zero,
or equal to or greater than size()
java.lang.NullPointerException
- if value
is null
public int size()
public void addFirst(T value)
NodeList
.
This is an O(1) operation.addFirst
in interface java.util.Deque<T>
value
- the element to addjava.lang.NullPointerException
- if value
is null
public void addLast(T value)
NodeList
.
This is an O(1) operation.addLast
in interface java.util.Deque<T>
value
- the element to addjava.lang.NullPointerException
- if value
is null
public java.util.Iterator<T> descendingIterator()
Iterator
over the elements in the NodeList
in reverse order, starting after the last element.
This is an O(1) operation.public T element()
NodeList
.
Returns getFirst()
. This is an O(1) operation.public T getFirst()
NodeList
.
This is an O(1) operation.public T getLast()
NodeList
.
This is an O(1) operation.public boolean offer(T value)
NodeList
.
Calls addLast(T)
with value
. Always succeeds as the
NodeList
is not capacity-restricted. This is an O(1) operation.public boolean offerFirst(T value)
NodeList
.
Calls addFirst(T)
with value
. Always succeeds as the
NodeList
is not capacity-restricted. This is an O(1) operation.offerFirst
in interface java.util.Deque<T>
value
- the element to addjava.lang.NullPointerException
- if value
is null
public boolean offerLast(T value)
NodeList
.
Calls addLast(T)
with value
. Always succeeds as the
NodeList
is not capacity-restricted. This is an O(1) operation.offerLast
in interface java.util.Deque<T>
value
- the element to addjava.lang.NullPointerException
- if value
is null
public T peek()
NodeList
.
Returns peekFirst()
. This is an O(1) operation.public T peekFirst()
NodeList
.
This is an O(1) operation.public T peekLast()
NodeList
.
This is an O(1) operation.public T poll()
NodeList
.
Returns pollFirst()
. This is an O(1) operation.public T pollFirst()
NodeList
.
This is an O(1) operation.public T pollLast()
NodeList
.
This is an O(1) operation.public T pop()
NodeList
.
Returns removeFirst()
. This is an O(1) operation.public void push(T value)
NodeList
.
Calls addFirst(T)
with value
. This is an O(1) operation.push
in interface java.util.Deque<T>
value
- the element to addjava.lang.NullPointerException
- if value
is null
public T remove()
NodeList
.
Returns removeFirst()
. This is an O(1) operation.public T removeFirst()
NodeList
.
This is an O(1) operation.public boolean removeFirstOccurrence(java.lang.Object obj)
NodeList
.
Attempts to cast obj
to T, then calls findFirstNode(T)
and finally remove(org.kynosarges.tektosyne.NodeList.Node<T>)
on success. This is an O(n) operation.removeFirstOccurrence
in interface java.util.Deque<T>
obj
- the element to removetrue
if obj
was found and removed, else false
java.lang.ClassCastException
- if obj
cannot be cast to Tjava.lang.NullPointerException
- if obj
is null
public T removeLast()
NodeList
.
This is an O(1) operation.public boolean removeLastOccurrence(java.lang.Object obj)
NodeList
.
Attempts to cast obj
to T, then calls findLastNode(T)
and finally remove(org.kynosarges.tektosyne.NodeList.Node<T>)
on success. This is an O(n) operation.removeLastOccurrence
in interface java.util.Deque<T>
obj
- the element to removetrue
if obj
was found and removed, else false
java.lang.ClassCastException
- if obj
cannot be cast to Tjava.lang.NullPointerException
- if obj
is null