E
- element typeT
- linked list entry typepublic abstract class AbstractLinkedList<E,T extends LinkedListEntry<E,T>> extends AbstractSmartCollection<E> implements SmartSequence<E>
This class implements the base functionality for dealing with linked lists of elements implementing the LinkedListEntry
interface. It provides the logic for the basic operations (esp. the (re-/un-)linking of elements),
but not how entries into the lists are created. Therefore, it can be used by both intrusive and non-intrusive linked
lists.
IntrusiveLinkedList
,
DefaultLinkedList
Constructor and Description |
---|
AbstractLinkedList() |
Modifier and Type | Method and Description |
---|---|
protected T |
castRef(ElementReference ref)
Helper function for casting a general
ElementReference to the specific linked list entry type. |
E |
choose()
Retrieves an arbitrary element from the collection.
|
ElementReference |
chooseRef()
Retrieves the reference to an arbitrary element from the collection.
|
void |
clear() |
void |
concat(AbstractLinkedList<? extends E,? extends T> other)
Concatenates two linked lists.
|
E |
get(ElementReference ref)
Retrieves an element by its reference.
|
E |
getBack()
Retrieves the last element in the list.
|
protected T |
getBackEntry()
Retrieves the last entry in the list, or
null if the list is empty. |
@Nullable ElementReference |
getBackReference()
Retrieves a reference to the last element in the list.
|
E |
getFront()
Retrieves the first element in the list.
|
protected T |
getFrontEntry()
Retrieves the first entry in the list, or
null if the list is empty. |
@Nullable ElementReference |
getFrontReference()
Retrieves a reference to the first element in the list.
|
ElementReference |
insertAfter(E element,
ElementReference ref)
Inserts the given element after the element referenced by the specified reference.
|
protected void |
insertAfterEntry(T e,
T insertPos)
Inserts a new entry after a given one.
|
ElementReference |
insertBefore(E element,
ElementReference ref)
Inserts the given element before the element referenced by the specified reference.
|
protected void |
insertBeforeEntry(T e,
T insertPos)
Inserts a new entry before a given one.
|
boolean |
isEmpty() |
Iterator<E> |
iterator() |
protected abstract T |
makeEntry(E element)
Creates (if necessary) a
LinkedListEntry for the given element. |
E |
popBack()
Retrieves and removes the last element in the list.
|
protected T |
popBackEntry()
Removes and returns the last entry in the list.
|
E |
popFront()
Retrieves and removes the first element in the list.
|
protected T |
popFrontEntry()
Removes and returns the first entry in the list.
|
@Nullable ElementReference |
pred(ElementReference ref)
Retrieves the reference to the preceding element, or
null if the given reference references the
first element in the list. |
ElementReference |
pushBack(E element)
Adds an element at the end of the list.
|
protected void |
pushBackEntry(T e)
Adds an entry at the end of the list.
|
ElementReference |
pushFront(E element)
Adds an element at the beginning of the list.
|
protected void |
pushFrontEntry(T e)
Adds an entry at the beginning of the list.
|
ElementReference |
referencedAdd(E elem)
Adds an element to the collection, returning a reference to the newly added element.
|
Iterator<ElementReference> |
referenceIterator()
Retrieves an iterator for iterating over the references of elements in this collection.
|
void |
remove(ElementReference elem)
Removes an element (by its reference) from the collection.
|
protected void |
removeEntry(T entry)
Removes an entry from the list.
|
void |
replace(ElementReference ref,
E newElement)
Replaces the element referenced by the given reference with the specified element.
|
protected void |
replaceEntry(T oldEntry,
T newEntry)
Replaces an entry in the list.
|
int |
size() |
@Nullable ElementReference |
succ(ElementReference ref)
Retrieves the reference to the succeeding element, or
null if the given reference references the
last element in the list. |
void |
swap(AbstractLinkedList<E,T> other)
Swaps the contents of two linked lists with the same entry types.
|
add, addAll, addAll, deepClear, find, quickClear, references, remove
addAll, contains, containsAll, removeAll, retainAll, toArray, toArray, toString
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
addAll, addAll, deepClear, find, quickClear, references, remove
add, addAll, contains, containsAll, equals, hashCode, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray
protected T getFrontEntry()
null
if the list is empty.null
.protected T getBackEntry()
null
if the list is empty.null
.public void concat(AbstractLinkedList<? extends E,? extends T> other)
other
- the list to append,public E choose()
SmartCollection
choose
in interface SmartCollection<E>
choose
in class AbstractSmartCollection<E>
public ElementReference chooseRef()
SmartCollection
NoSuchElementException
is thrown.chooseRef
in interface SmartCollection<E>
chooseRef
in class AbstractSmartCollection<E>
public Iterator<E> iterator()
iterator
in interface Iterable<E>
iterator
in interface Collection<E>
iterator
in class AbstractSmartCollection<E>
public E get(ElementReference ref)
SmartCollection
If the reference belongs to another collection, the behavior is undefined.
get
in interface SmartCollection<E>
ref
- the element's reference.public ElementReference referencedAdd(E elem)
SmartCollection
referencedAdd
in interface SmartCollection<E>
elem
- the element to be added.public void remove(ElementReference elem)
SmartCollection
If the reference does not belong to this collection, the behavior is undefined.
remove
in interface SmartCollection<E>
elem
- the reference to the element to be removed.protected void removeEntry(T entry)
entry
- the entry to remove.public Iterator<ElementReference> referenceIterator()
SmartCollection
referenceIterator
in interface SmartCollection<E>
public void replace(ElementReference ref, E newElement)
SmartCollection
replace
in interface SmartCollection<E>
ref
- the reference of the element to be replaced.newElement
- the replacement.protected void replaceEntry(T oldEntry, T newEntry)
oldEntry
- the entry to be replaced.newEntry
- the replacement entry.protected abstract T makeEntry(E element)
LinkedListEntry
for the given element. For intrusive linked lists, e.g., the
argument itself is returned.element
- the element for which to retrieve an entry.protected void pushBackEntry(T e)
e
- the entry to add.public int size()
size
in interface Collection<E>
size
in class AbstractCollection<E>
@EnsuresQualifierIf(qualifier=org.checkerframework.checker.nullness.qual.NonNull.class, expression={"this.head","this.last"}, result=false) public boolean isEmpty()
isEmpty
in interface Collection<E>
isEmpty
in class AbstractCollection<E>
public void clear()
clear
in interface Collection<E>
clear
in class AbstractCollection<E>
public E getBack()
NoSuchElementException
will be thrown.public @Nullable ElementReference getBackReference()
null
is returned.null
.public E getFront()
NoSuchElementException
will be thrownpublic @Nullable ElementReference getFrontReference()
null
is returned.null
.public E popBack()
NullPointerException
may be
thrown.protected T popBackEntry()
null
is returned.null
.public E popFront()
NullPointerException
may be
thrown.protected T popFrontEntry()
null
is returned.null
.public ElementReference pushBack(E element)
element
- the element to add.public ElementReference pushFront(E element)
element
- the element to add.protected void pushFrontEntry(T e)
e
- the entry to add.public @Nullable ElementReference pred(ElementReference ref)
SmartSequence
null
if the given reference references the
first element in the list.pred
in interface SmartSequence<E>
ref
- the referenceprotected T castRef(ElementReference ref)
ElementReference
to the specific linked list entry type.ref
- the reference.public @Nullable ElementReference succ(ElementReference ref)
SmartSequence
null
if the given reference references the
last element in the list.succ
in interface SmartSequence<E>
ref
- the referencepublic ElementReference insertBefore(E element, ElementReference ref)
SmartSequence
insertBefore
in interface SmartSequence<E>
element
- the element to be added.ref
- reference to the element before which the new element is to be inserted.protected void insertBeforeEntry(T e, T insertPos)
e
- the entry to add.insertPos
- the entry before which to add the new one.public ElementReference insertAfter(E element, ElementReference ref)
SmartSequence
insertAfter
in interface SmartSequence<E>
element
- the element to be added.ref
- reference to the element after which the new element is to be inserted.protected void insertAfterEntry(T e, T insertPos)
e
- the entry to add.insertPos
- the entry before which to add the new one.public void swap(AbstractLinkedList<E,T> other)
other
- the other list to swap contents with.Copyright © 2020. All rights reserved.