| Methods Summary |
|---|
| public void | add(int index, java.lang.Object object)Inserts the object at the specified index. Note that this
method is an O(n) operation as it has to iterate through the nodes
in the list till the appropriate index is reached.
insertAt(index, object);
size++;
|
| public boolean | add(java.lang.Object object)Inserts the object at the end of the list.
last.insertBefore(nodeFactory.createDListNode(object));
size++;
return true;
|
| public boolean | addAll(java.util.Collection collection)Inserts the object at the specified index. Note that this
method is an O(n) operation as it has to iterate through the nodes
in the list till the appropriate index is reached.
Iterator iter = collection.iterator();
boolean added = false;
while (iter.hasNext()) {
add(iter.next());
added = true;
}
size += collection.size();
return added;
|
| public boolean | addAll(int index, java.util.Collection collection)Inserts the object at the specified index. Note that this
method is an O(n) operation as it has to iterate through the nodes
in the list till the appropriate index is reached.
DListNode node = getDListNodeAt(index);
Iterator iter = collection.iterator();
boolean added = iter.hasNext();
DListNode head = new DListNode(null);
DListNode last = head;
while (iter.hasNext()) {
last.insertAfter(nodeFactory.createDListNode(iter.next()));
last = last.next;
}
if (head != last) {
node.prev.next = head.next;
node.prev = last;
head.next.prev = node;
last.next = node;
}
size += collection.size();
return added;
|
| public void | addAsFirstNode(DListNode node)/
public DListNode createDListNode(Object object) {
return new DListNode(object);
}
public void destroyDListNode(DListNode node) {
}
public DListNodeFactory getDListNodeFactory() {
return this.nodeFactory;
}
public void setDListNodeFactory(DListNodeFactory nodeFactory) {
this.nodeFactory = nodeFactory;
}
/**
Add a DListNode as the first node in the list.
DListNode fNode = first.next;
node.next = fNode;
node.prev = first;
fNode.prev = first.next = node;
size++;
|
| public DListNode | addAsFirstObject(java.lang.Object object)Add an object as the first node in the list.
DListNode node = nodeFactory.createDListNode(object);
addAsFirstNode(node);
return node;
|
| public void | addAsLastNode(DListNode node)Add a DListNode as the last node in the list.
DListNode lNode = last.prev;
node.next = last;
node.prev = lNode;
lNode.next = last.prev = node;
size++;
|
| public DListNode | addAsLastObject(java.lang.Object obj)Add an object as the last node in the list.
DListNode node= nodeFactory.createDListNode(obj);
addAsLastNode(node);
return node;
|
| public void | clear()
first.next = last;
last.prev = first;
size = 0;
|
| public boolean | contains(java.lang.Object o)
return (indexOf(o) != -1);
|
| public boolean | containsAll(java.util.Collection collection)
Iterator iter = collection.iterator();
while (iter.hasNext()) {
Object o = iter.next();
if (indexOf(o) == -1) {
return false;
}
}
return true;
|
| public void | delink(DListNode node)
node.delink();
size--;
|
| public DListNode | delinkFirstNode()Removes the first DListNode from the list.
if (size > 0) {
DListNode node = first.next;
node.delink();
size--;
return node;
}
return null;
|
| public DListNode | delinkLastNode()Removes the last DListNode from the list.
if (size > 0) {
DListNode node = last.prev;
node.delink();
size--;
return node;
}
return null;
|
| public boolean | equals(java.lang.Object o)
if (o instanceof List) {
List list = (List) o;
if (list.size() != size()) {
return false;
}
Object myObj = null, otherObj = null;
DListNode node = first;
for (int i=0; i<size; i++) {
myObj = node.next.object;
otherObj = list.get(i);
if (! myObj.equals(otherObj)) {
return false;
}
node = node.next;
}
return true;
}
return false;
|
| public java.lang.Object | get(int index)Return the object at the specified index
DListNode node = getDListNodeAt(index);
return (node == null) ? null : node.object;
|
| public DListNode | getDListNode(java.lang.Object o)Obtains the DListNode that contains this object. The method relies on the
equals() method to identify objects in the list. Note that this
method is an O(n) operation as it has to iterate through the nodes
in the list till a match is found.
for (DListNode node = first.next; node != last; node = node.next) {
if (node.object.equals(o)) {
return node;
}
}
return null;
|
| public DListNode | getDListNodeAt(int index)Obtains the DListNode at the specified index. Note that this
method is an O(n) operation as it has to iterate through the nodes
in the list till a match is found.
if ((index < 0) || (index >= size)) {
throw new ArrayIndexOutOfBoundsException("DList size: " + size + "; index: " + index);
}
int mid = size >> 1; //Divide by 2!!
DListNode node = null;
if (index <= mid) {
node = first.next;
for (int i=0; i<index ; i++) {
node = node.next;
}
} else {
index = size - index - 1;
node = last.prev;
for (int i=0; i<index ; i++) {
node = node.prev;
}
}
return node;
|
| public DListNode | getFirstDListNode()
return (size == 0) ? null : first.next;
|
| public DListNode | getLastDListNode()
return (size == 0) ? null : last.prev;
|
| public DListNode | getNextNode(DListNode node)
DListNode nextNode = node.next;
return (nextNode == last) ? null : nextNode;
|
| public DListNode | getPreviousNode(DListNode node)
DListNode prevNode = node.prev;
return (prevNode == first) ? null : prevNode;
|
| public int | hashCode()
int hashCode = 1;
DListNode node = first;
Object myObj = null;
for (int i=0; i<size; i++) {
myObj = node.next.object;
hashCode = 31*hashCode + (myObj==null ? 0 : myObj.hashCode());
node = node.next;
}
return hashCode;
|
| public int | indexOf(java.lang.Object o)Obtains the index at which this object appears in the list. The method relies on the
equals() method to identify objects in the list. Note that this
method is an O(n) operation as it has to iterate through the nodes
in the list till a match is found.
int index = 0;
for (DListNode node = first.next; node != last; node = node.next) {
if (node.object.equals(o)) {
return index;
}
index++;
}
return -1;
|
| protected void | initDListWithNodes(DListNode firstNode, DListNode lastNode, DListNodeFactory factory)
first = firstNode;
last = lastNode;
first.next = last;
last.prev = first;
first.prev = last.next = null;
this.nodeFactory = (factory == null) ? this : factory;
|
| public DListNode | insertAt(int index, java.lang.Object object)Inserts the object at the specified index. Note that this
method is an O(n) operation as it has to iterate through the nodes
in the list till the appropriate index is reached.
if ((index < 0) || (index >= size)) {
return null;
}
int mid = size >> 1; //Divide by 2!!
DListNode node = null;
if (index <= mid) {
node = first.next;
for (int i=0; i<index ; i++) {
node = node.next;
}
} else {
index = size - index - 1;
node = last.prev;
for (int i=0; i<index ; i++) {
node = node.prev;
}
}
DListNode newNode = nodeFactory.createDListNode(object);
node.insertBefore(newNode);
size++;
return newNode;
|
| public boolean | isEmpty()Returns true if this list contains no elements.
return (this.size > 0);
|
| public java.util.Iterator | iterator()Returns an iterator for iterating the entries in the list. Each object returned
by the iterator.next() is the actual object added to the list.
return new DListIterator(first, last, false, 0);
|
| public int | lastIndexOf(java.lang.Object obj)Returns the index in this list of the last occurrence of the specified element,
or -1 if this list does not contain this element. More formally, returns the highest
index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.
int index = size - 1;
for (DListNode node = last.prev; node != first; node = node.prev) {
if (node.object.equals(obj)) {
return index;
}
index--;
}
return -1;
|
| public java.util.ListIterator | listIterator()Returns a list iterator of the elements in this list (in proper sequence).
retrieve the object.
return new DListIterator(first, last, true, 0);
|
| public java.util.ListIterator | listIterator(int index)Returns a list iterator of the elements in this list (in proper sequence), starting
at the specified position in this list. The specified index indicates the first element
that would be returned by an initial call to the next method. An initial call to the
previous method would return the element with the specified index minus one.
return new DListIterator(first, last, true, index);
|
| public java.util.Iterator | nodeIterator()Returns an iterator for iterating the entries in the list. Each object returned
by the iterator.next() is an instance of DListNode. Use DListNode.object to
retrieve the object.
return new DListIterator( first, last, true, 0);
|
| public java.lang.Object | remove(int index)Removes the element at the specified position in this list (optional operation).
Shifts any subsequent elements to the left (subtracts one from their indices).
DListNode node = getDListNodeAt(index);
node.delink();
size--;
Object object = node.object;
destroyDListNode(node);
return object;
|
| public boolean | remove(java.lang.Object object)Removes the first occurrence in this list of the specified element (optional operation).
If this list does not contain the element, it is unchanged. More formally,
removes the element with the lowest index i such that
(o==null ? get(i)==null : o.equals(get(i))) (if such an element exists).
DListNode node = getDListNode(object);
if (node == null) {
return false;
} else {
node.delink();
destroyDListNode(node);
size--;
return true;
}
|
| public boolean | removeAll(java.util.Collection collection)
Iterator iter = collection.iterator();
boolean removed = false;
while (iter.hasNext()) {
if (remove(iter.next())) {
size--;
removed = true;
}
}
return removed;
|
| public java.lang.Object | removeFirstObject()Removes the first object from the list.
DListNode node = delinkFirstNode();
if (node == null) {
return null;
} else {
Object object = node.object;
destroyDListNode(node);
return object;
}
|
| public java.lang.Object | removeLastObject()Removes the last object from the list.
DListNode node = delinkLastNode();
if (node == null) {
return null;
} else {
Object object = node.object;
destroyDListNode(node);
return object;
}
|
| public boolean | retainAll(java.util.Collection collection)
boolean removed = false;
DListNode node = first;
DListNode dnode = null;
while (node.next != last) {
dnode = node.next;
if (collection.contains(dnode.object)) {
dnode.delink();
destroyDListNode(dnode);
size--;
removed = true;
} else {
node = node.next;
}
}
return removed;
|
| public java.lang.Object | set(int index, java.lang.Object object)Return the object at the specified index
DListNode node = getDListNodeAt(index);
Object oldObject = (node == null) ? null : node.object;
node.object = object;
return oldObject;
|
| public int | size()Obtain the size of the list.
return size;
|
| public java.util.List | subList(int fromIndex, int toIndex)Returns a view of the portion of this list between the specified fromIndex,
inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the
returned list is empty.) The returned list is backed by this list, so changes
in the returned list are reflected in this list, and vice-versa. The returned list supports
all of the optional list operations supported by this list.
This method eliminates the need for explicit range operations (of the sort
that commonly exist for arrays). Any operation that expects a list can be used as a
range operation by passing a subList view instead of a whole list. For example,
the following idiom removes a range of elements from a list:
list.subList(from, to).clear();
Similar idioms may be constructed for indexOf and lastIndexOf, and all of the
algorithms in the Collections class can be applied to a subList.
The semantics of this list returned by this method become undefined if the backing
list (i.e., this list) is structurally modified in any way other than via the
returned list. (Structural modifications are those that change the size of this
list, or otherwise perturb it in such a fashion that iterations in progress may yield
incorrect results.)
System.out.println("subList(" + fromIndex + ", " + toIndex + ")");
DListNode startNode = getDListNodeAt(fromIndex);
System.out.println("nodeAt(" + fromIndex + "): " + startNode.object);
DListNode toNode = getDListNodeAt(toIndex);
System.out.println("nodeAt(" + toIndex + "): " + toNode.object);
return new DList(startNode.prev, toNode, toIndex - fromIndex, nodeFactory);
|
| public java.lang.Object[] | toArray()Returns an array containing all of the elements in this collection. If the collection
makes any guarantees as to what order its elements are returned by its iterator, this
method must return the elements in the same order.
The returned array will be "safe" in that no references to it are maintained by this
collection. (In other words, this method must allocate a new array even if this
collection is backed by an array). The caller is thus free to modify the returned array.
Object[] array = new Object[size];
int index = 0;
for (DListNode node = first.next; node != last; node = node.next) {
array[index++] = node.object;
}
return array;
|
| public java.lang.Object[] | toArray(java.lang.Object[] array)Returns an array containing all of the elements in this collection whose runtime type
is that of the specified array. If the collection fits in the specified array, it is
returned therein. Otherwise, a new array is allocated with the runtime type of the
specified array and the size of this collection.
If this collection fits in the specified array with room to spare (i.e., the
array has more elements than this collection), the element in the array immediately
following the end of the collection is set to null. This is useful in determining
the length of this collection only if the caller knows that this collection does
not contain any null elements.)
If this collection makes any guarantees as to what order its elements are returned
by its iterator, this method must return the elements in the same order.
Like the toArray method, this method acts as bridge between array-based and
collection-based APIs. Further, this method allows precise control over the runtime
type of the output array, and may, under certain circumstances, be used to save allocation costs.
Suppose l is a List known to contain only strings. The following code can be
used to dump the list into a newly allocated array of String:
String[] x = (String[]) v.toArray(new String[0]);
if (array.length < size) {
array = (Object[]) java.lang.reflect.Array.newInstance(array.getClass().getComponentType(), size);
}
int index = 0;
for (DListNode node = first.next; node != last; node = node.next) {
array[index++] = node.object;
}
if (array.length > size) {
array[size] = null;
}
return array;
|
