|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.model.list.DoubleLinkedList<E>
E
- Base element type stored with the nodes.public class DoubleLinkedList<E>
Maintain doubly-linked list of entities.
If no Comparator is provided when the DoubleLinkedList
object was constructed,
then insert degrades to append.
Note that using append(E) voids the sorted property of this list that can be maintained by insert(E) and users should not use both of these methods on the same object.
Field Summary | |
---|---|
static java.util.Comparator |
prePend
Force all inserts to be 'prepend' |
Constructor Summary | |
---|---|
DoubleLinkedList()
Construct double linked list with no comparator (defaults to append on insert). |
|
DoubleLinkedList(java.util.Comparator<E> comp)
Construct double linked list with comparator. |
Method Summary | |
---|---|
void |
concat(DoubleLinkedList<E> list)
Concatenate the two lists. |
E |
contains(E e)
Determine membership by returning element if found. |
DoubleNode<E> |
first()
Return first element in list. |
void |
insert(E e)
Insert an entity based upon the comparator. |
boolean |
isEmpty()
Return whether the list is empty. |
java.util.Iterator<E> |
iterator()
Return iterator to elements in the list. |
DoubleNode<E> |
last()
Return last element in list. |
boolean |
remove(DoubleNode<E> node)
Given DoubleNode already known to exist in the list, remove it. |
boolean |
remove(E e)
This will remove given element known to already be in the list. |
E |
removeFirst()
Remove first element without altering sort order. |
E |
removeLast()
Remove last element without altering sort order. |
int |
size()
Return size of the list. |
java.lang.String |
toString()
Useful string for debugging. |
void |
validate()
If links have been manually modified, then we must validate the size is properly set and there is no circular link. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public static java.util.Comparator prePend
Constructor Detail |
---|
public DoubleLinkedList()
public DoubleLinkedList(java.util.Comparator<E> comp)
If the comparator always returns '+1' on all inputs, then this list will prepend on insert. If the comparator always returns '-1' on all inputs, then this list will append on insert.
The comparator compares E o1 and E o2 where o1 points to the value already in the list, and o2 points to the value that desires to be added. While compare return -1, the pointer in the list will advance. Once compare returns +1, then the value will be inserted just ahead of the node pointed to when the comparison is invoked.
To have an ascending list, therefore, you must make sure that your compare returns a negative number while o1 is < o2, and returns a positive number while o1 is > o2. Note that when o1.equals(o2), then pointer will advance so this newly added item will appear after other items that .equals() that object.
Comparator comparator = new Comparator() {
public int compare(E o1, E o2) {
return o1.compareTo(o2);
}
};
comp
- The comparator function. If null, then we default to prePend
.Method Detail |
---|
public DoubleNode<E> first()
public DoubleNode<E> last()
public boolean isEmpty()
public int size()
public java.util.Iterator<E> iterator()
iterator
in interface java.lang.Iterable<E>
public void validate()
This method, typically, is never called unless the user is performing some advanced pointer modifications.
public void insert(E e)
If there is no comparator selected, then insert becomes a simple 'append'.
e
- The Element to be inserted.public E contains(E e)
Check for membership using E.equals(E) rather than the default == method. Note, however, the the remove(E) method removes solely based on ==. By definition, contains(null) is false.
e
- element to be soughtpublic void concat(DoubleLinkedList<E> list)
If list is null, then no operation (or error) occurs. Note that concatenating list A to B does not affect the passed in list parameter. Thus you may end up with some interesting intermingled objects if you are not careful.
list
- List to be appended to the end.public boolean remove(DoubleNode<E> node)
USE WITH CARE! Then ask yourself if you really need to use it!
Sanity Check: Make sure that you remove a node that already exists within the list! No check is made to ensure that the given node already exists within the list.
node
- the node to be snipped out of the list.public boolean remove(E e)
Comparison based solely on '=='. This is safer than removing a node.
e
- the element to be removed from the list.public E removeFirst()
public E removeLast()
public java.lang.String toString()
toString
in class java.lang.Object
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |