Algorithm
Development Kit 1.0

algs.model.list
Class DoubleLinkedList<E>

java.lang.Object
  extended by algs.model.list.DoubleLinkedList<E>
Type Parameters:
E - Base element type stored with the nodes.
All Implemented Interfaces:
java.lang.Iterable<E>

public class DoubleLinkedList<E>
extends java.lang.Object
implements java.lang.Iterable<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.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

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

prePend

public static java.util.Comparator prePend
Force all inserts to be 'prepend'

Constructor Detail

DoubleLinkedList

public DoubleLinkedList()
Construct double linked list with no comparator (defaults to append on insert).


DoubleLinkedList

public DoubleLinkedList(java.util.Comparator<E> comp)
Construct double linked list with comparator.

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);
       }
    };
 

Parameters:
comp - The comparator function. If null, then we default to prePend.
Method Detail

first

public DoubleNode<E> first()
Return first element in list.


last

public DoubleNode<E> last()
Return last element in list.


isEmpty

public boolean isEmpty()
Return whether the list is empty.


size

public int size()
Return size of the list.


iterator

public java.util.Iterator<E> iterator()
Return iterator to elements in the list.

Specified by:
iterator in interface java.lang.Iterable<E>

validate

public void validate()
If links have been manually modified, then we must validate the size is properly set and there is no circular link.

This method, typically, is never called unless the user is performing some advanced pointer modifications.


insert

public void insert(E e)
Insert an entity based upon the comparator.

If there is no comparator selected, then insert becomes a simple 'append'.

Parameters:
e - The Element to be inserted.

contains

public E contains(E e)
Determine membership by returning element if found.

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.

Parameters:
e - element to be sought

concat

public void concat(DoubleLinkedList<E> list)
Concatenate the two lists.

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.

Parameters:
list - List to be appended to the end.

remove

public boolean remove(DoubleNode<E> node)
Given DoubleNode already known to exist in the list, remove it.

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.

Parameters:
node - the node to be snipped out of the list.

remove

public boolean remove(E e)
This will remove given element known to already be in the list.

Comparison based solely on '=='. This is safer than removing a node.

Parameters:
e - the element to be removed from the list.

removeFirst

public E removeFirst()
Remove first element without altering sort order.


removeLast

public E removeLast()
Remove last element without altering sort order.


toString

public java.lang.String toString()
Useful string for debugging.

Overrides:
toString in class java.lang.Object

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.