- All Implemented Interfaces:
Externalizable
,Serializable
,Iterable<T>
,Collection<T>
,List<T>
,SequencedCollection<T>
Using this implementation allows you to get java.util.LinkedList behavior (a doubly linked list, with Iterators that support insert and delete operations) without incurring the overhead of creating Node wrapper objects for every element in your list.
The requirement to achieve this time/space gain is that the Objects stored in the List implement the TLinkable interface.
The limitations are that you cannot put the same object into more than one list or more than once in the same list. You must also ensure that you only remove objects that are actually in the list. That is, if you have an object A and lists l1 and l2, you must ensure that you invoke List.remove(A) on the correct list. It is also forbidden to invoke List.remove() with an unaffiliated TLinkable (one that belongs to no list): this will destroy the list you invoke it on.
Created: Sat Nov 10 15:25:10 2001
- Version:
- $Id: TLinkedList.java,v 1.15 2009/03/31 19:43:14 robeden Exp $
- Author:
- Eric D. Friedman
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected final class
A ListIterator that supports additions and deletions. -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected T
the head of the listprotected int
the number of elements in the listprotected T
the tail of the listFields inherited from class java.util.AbstractList
modCount
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
Inserts linkable at index index in the list.boolean
Appends linkable to the end of the list.void
Inserts newElement into the list immediately after current.void
Inserts newElement into the list immediately before current.void
Inserts linkable at the head of the list.void
Adds linkable to the end of the list.void
clear()
Empties the list.boolean
A linear search for o in the list.boolean
forEachValue
(TObjectProcedure<T> procedure) Executes procedure for each entry in the list.get
(int index) getFirst()
Returns the head of the listgetLast()
Returns the tail of the list.Return the node following the given node.getPrevious
(T current) Return the node preceding the given node.protected void
Implementation of index-based list insertions.listIterator
(int index) Returns an iterator positioned at index.void
boolean
Removes the specified element from the list.Remove and return the first element in the list.Remove and return the last element in the list.int
size()
Returns the number of elements in the list.Object[]
toArray()
Copies the list's contents into a native array.Object[]
Copies the list to a native array, destroying the next/previous links as the copy is made.void
Methods inherited from class java.util.AbstractSequentialList
addAll, iterator, remove, set
Methods inherited from class java.util.AbstractList
equals, hashCode, indexOf, lastIndexOf, listIterator, removeRange, subList
Methods inherited from class java.util.AbstractCollection
addAll, containsAll, isEmpty, removeAll, retainAll, toArray, toString
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArray
Methods inherited from interface java.util.List
addAll, containsAll, isEmpty, removeAll, replaceAll, retainAll, reversed, sort, spliterator, toArray
-
Field Details
-
_head
the head of the list -
_tail
the tail of the list -
_size
protected int _sizethe number of elements in the list
-
-
Constructor Details
-
TLinkedList
public TLinkedList()Creates a newTLinkedList
instance.
-
-
Method Details
-
listIterator
Returns an iterator positioned at index. Assuming that the list has a value at that index, calling next() will retrieve and advance the iterator. Assuming that there is a value before index in the list, calling previous() will retrieve it (the value at index - 1) and move the iterator to that position. So, iterating from front to back starts at 0; iterating from back to front starts at size().- Specified by:
listIterator
in interfaceList<T extends TLinkable>
- Specified by:
listIterator
in classAbstractSequentialList<T extends TLinkable>
- Parameters:
index
- anint
value- Returns:
- a
ListIterator
value
-
size
public int size()Returns the number of elements in the list. -
add
Inserts linkable at index index in the list. All values > index are shifted over one position to accommodate the new addition. -
add
Appends linkable to the end of the list. -
addFirst
Inserts linkable at the head of the list. -
addLast
Adds linkable to the end of the list. -
clear
public void clear()Empties the list. -
toArray
Copies the list's contents into a native array. This will be a shallow copy: the Tlinkable instances in the Object[] array have links to one another: changing those will put this list into an unpredictable state. Holding a reference to one element in the list will prevent the others from being garbage collected unless you clear the next/previous links. Caveat programmer! -
toUnlinkedArray
Copies the list to a native array, destroying the next/previous links as the copy is made. This list will be emptied after the copy (as if clear() had been invoked). The Object[] array returned will contain TLinkables that do not hold references to one another and so are less likely to be the cause of memory leaks.- Returns:
- an
Object[]
value
-
contains
A linear search for o in the list. -
get
-
getFirst
Returns the head of the list -
getLast
Returns the tail of the list. -
getNext
Return the node following the given node. This method exists for two reasons:- It's really not recommended that the methods implemented by TLinkable be called directly since they're used internally by this class.
- This solves problems arising from generics when working with the linked objects directly.
NOTE: this should only be used with nodes contained in the list. The results are undefined with anything else.
-
getPrevious
Return the node preceding the given node. This method exists for two reasons:- It's really not recommended that the methods implemented by TLinkable be called directly since they're used internally by this class.
- This solves problems arising from generics when working with the linked objects directly.
NOTE: this should only be used with nodes contained in the list. The results are undefined with anything else.
-
removeFirst
Remove and return the first element in the list.- Specified by:
removeFirst
in interfaceList<T extends TLinkable>
- Specified by:
removeFirst
in interfaceSequencedCollection<T extends TLinkable>
- Returns:
- an
Object
value
-
removeLast
Remove and return the last element in the list.- Specified by:
removeLast
in interfaceList<T extends TLinkable>
- Specified by:
removeLast
in interfaceSequencedCollection<T extends TLinkable>
- Returns:
- an
Object
value
-
insert
Implementation of index-based list insertions.- Parameters:
index
- anint
valuelinkable
- an object of type TLinkable
-
remove
Removes the specified element from the list. Note that it is the caller's responsibility to ensure that the element does, in fact, belong to this list and not another instance of TLinkedList.- Specified by:
remove
in interfaceCollection<T extends TLinkable>
- Specified by:
remove
in interfaceList<T extends TLinkable>
- Overrides:
remove
in classAbstractCollection<T extends TLinkable>
- Parameters:
o
- a TLinkable element already inserted in this list.- Returns:
- true if the element was a TLinkable and removed
-
addBefore
Inserts newElement into the list immediately before current. All elements to the right of and including current are shifted over.- Parameters:
current
- aTLinkable
value currently in the list.newElement
- aTLinkable
value to be added to the list.
-
addAfter
Inserts newElement into the list immediately after current. All elements to the left of and including current are shifted over.- Parameters:
current
- aTLinkable
value currently in the list.newElement
- aTLinkable
value to be added to the list.
-
forEachValue
Executes procedure for each entry in the list.- Parameters:
procedure
- aTObjectProcedure
value- Returns:
- false if the loop over the values terminated because the procedure returned false for some value.
-
writeExternal
- Specified by:
writeExternal
in interfaceExternalizable
- Throws:
IOException
-
readExternal
- Specified by:
readExternal
in interfaceExternalizable
- Throws:
IOException
ClassNotFoundException
-