Overview | Package | Class | Tree | Deprecated | Index | Help
| J avolution v5.3 (J2SE 1.5+)
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## javolution.util
Class FastList<E>

    java.lang.Object
      javolution.util.FastCollection<E>
          javolution.util.FastList<E>

All Implemented Interfaces:
  java.io.Serializable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.List<E>, Realtime, Reusable, XMLSerializable

    public class FastList<E>

extends FastCollection<E>
implements java.util.List<E>, Reusable

This class represents a linked list with real-time behavior; smooth capacity increase and no memory allocation as long as the list size does not exceed its initial capacity.

All of the operations perform as could be expected for a doubly-linked list (`insertion`/`deletion` at the end of the list are nonetheless the fastest). Operations that index into the list will traverse the list from the begining or the end whichever is closer to the specified index. Random access operations can be significantly accelerated by `splitting` the list into smaller ones.

`FastList` (as for any `FastCollection` sub-class) supports thread-safe, fast iterations without using iterators.``

         FastList<String> list = new FastList<String>();
         for (FastList.Node<String> n = list.head(), end = list.tail(); (n = n.getNext()) != end;) {
             String value = n.getValue(); // No typecast necessary.
         }

`FastList` are fully `reusable`, they maintain internal pools of `nodes` objects. When a node is removed from its list, it is automatically restored to its pool.

Custom list implementations may override the `newNode()` method in order to return their own `FastList.Node` implementation (with additional fields for example).

Version:
  4.2, December 18, 2006
Author:
  Jean-Marie Dautelle
See Also:
  Serialized Form

Nested Class Summary
`static class` | `FastList.Node<E>` This class represents a `FastList` node; it allows for direct iteration over the list `values`.

Nested classes/interfaces inherited from class javolution.util.FastCollection
`FastCollection.Record`

Constructor Summary
`FastList()` Creates a list of small initial capacity.
`FastList(java.util.Collection<? extends E> values)` Creates a list containing the specified values, in the order they are returned by the collection's iterator.
`FastList(int capacity)` Creates a list of specified initial capacity; unless the list size reaches the specified capacity, operations on this list will not allocate memory (no lazy object creation).
`FastList(java.lang.String id)` Creates a persistent list associated to the specified unique identifier (convenience method).

Method Summary
`boolean` | `add(E value)` Appends the specified value to the end of this list (equivalent to `addLast(E)`).
`void` | `add(int index, E value)` Inserts the specified value at the specified position in this list.
`boolean` | `addAll(int index, java.util.Collection<? extends E> values)` Inserts all of the values in the specified collection into this list at the specified position.
`void` | `addBefore(FastList.Node<E> next, E value)` Inserts the specified value before the specified Node.
`void` | `addFirst(E value)` Inserts the specified value at the beginning of this list.
`void` | `addLast(E value)` Appends the specified value to the end of this list (fast).
`void` | `clear()` Removes all of the values from this collection (optional operation).
`boolean` | `contains(java.lang.Object value)` Indicates if this collection contains the specified value.
`void` | `delete(FastCollection.Record record)` Deletes the specified record from this collection.
`E` | `get(int index)` Returns the value at the specified position in this list.
`E` | `getFirst()` Returns the first value of this list.
`E` | `getLast()` Returns the last value of this list.
`FastComparator<? super E>` | `getValueComparator()` Returns the value comparator for this collection (default `FastComparator.DEFAULT`).
`FastList.Node<E>` | `head()` Returns the head record of this collection; it is the record such as `head().getNext()` holds the first collection value.
`int` | `indexOf(java.lang.Object value)` Returns the index in this list of the first occurrence of the specified value, or -1 if this list does not contain this value.
`java.util.Iterator<E>` | `iterator()` Returns a simple iterator over the elements in this list (allocated on the stack when executed in a `StackContext`).
`int` | `lastIndexOf(java.lang.Object value)` Returns the index in this list of the last occurrence of the specified value, or -1 if this list does not contain this value.
`java.util.ListIterator<E>` | `listIterator()` Returns a list iterator over the elements in this list (allocated on the stack when executed in a `StackContext`).
`java.util.ListIterator<E>` | `listIterator(int index)` Returns a list iterator from the specified position (allocated on the stack when executed in a `StackContext`).
`static
`<E> FastList<E>`
` | `newInstance()` Returns a new, preallocated or `recycled` list instance (on the stack when executing in a `StackContext`).
`protected FastList.Node<E>` | `newNode()` Returns a new node for this list; this method can be overriden by custom list implementation.
`static void` | `recycle(FastList instance)` Recycles a list `instance` immediately (on the stack when executing in a `StackContext`).
`E` | `remove(int index)` Removes the value at the specified position in this list.
`E` | `removeFirst()` Removes and returns the first value of this list.
`E` | `removeLast()` Removes and returns the last value of this list (fast).
`void` | `reset()` Resets the internal state of this object to its default values.
`E` | `set(int index, E value)` Replaces the value at the specified position in this list with the specified value.
`FastList<E>` | `setValueComparator(FastComparator<? super E> comparator)` Sets the comparator to use for value equality.
`int` | `size()` Returns the number of values in this collection.
`java.util.List<E>` | `subList(int fromIndex, int toIndex)` Returns a view of the portion of this list between the specified indexes (allocated from the "stack" when executing in a `StackContext`).
`FastList.Node<E>` | `tail()` Returns the tail record of this collection; it is the record such as `tail().getPrevious()` holds the last collection value.
`java.util.List<E>` | `unmodifiable()` Returns the unmodifiable view associated to this collection.
`E` | `valueOf(FastCollection.Record record)` Returns the collection value for the specified record.

Methods inherited from class javolution.util.FastCollection
`addAll, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString, toText`

Methods inherited from class java.lang.Object
`clone, finalize, getClass, notify, notifyAll, wait, wait, wait`

Methods inherited from interface java.util.List
`addAll, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray`

Constructor Detail

### FastList

    public FastList()

  Creates a list of small initial capacity.

### FastList

    public FastList(java.lang.String id)

  Creates a persistent list associated to the specified unique identifier (convenience method).

  Parameters:
    `id` - the unique identifier for this map.
  Throws:
    `java.lang.IllegalArgumentException` - if the identifier is not unique.
  See Also:
    `PersistentContext.Reference`

### FastList

    public FastList(int capacity)

  Creates a list of specified initial capacity; unless the list size reaches the specified capacity, operations on this list will not allocate memory (no lazy object creation).

  Parameters:
    `capacity` - the initial capacity.

### FastList

    public FastList(java.util.Collection<? extends E> values)

  Creates a list containing the specified values, in the order they are returned by the collection's iterator.

  Parameters:
    `values` - the values to be placed into this list.

Method Detail

### newInstance

    public static <E> FastList<E> newInstance()

  Returns a new, preallocated or `recycled` list instance (on the stack when executing in a `StackContext`).

  Returns:
    a new, preallocated or recycled list instance.

### recycle

    public static void recycle(FastList instance)

  Recycles a list `instance` immediately (on the stack when executing in a `StackContext`).

### add

    public final boolean add(E value)

  Appends the specified value to the end of this list (equivalent to `addLast(E)`).

  Specified by:
    `add` in interface `java.util.Collection<E>`
  Specified by:
    `add` in interface `java.util.List<E>`
  Overrides:
    `add` in class `FastCollection<E>`
  Parameters:
    `value` - the value to be appended to this list.
  Returns:
    `true` (as per the general contract of the `Collection.add` method).

### get

    public final E get(int index)

  Returns the value at the specified position in this list.

  Specified by:
    `get` in interface `java.util.List<E>`
  Parameters:
    `index` - the index of value to return.
  Returns:
    the value at the specified position in this list.
  Throws:
    `java.lang.IndexOutOfBoundsException` - if `(index < 0) || (index >= size())`

### set

    public final E set(int index,
                       E value)

  Replaces the value at the specified position in this list with the specified value.

  Specified by:
    `set` in interface `java.util.List<E>`
  Parameters:
    `index` - the index of value to replace.
    `value` - the value to be stored at the specified position.
  Returns:
    the value previously at the specified position.
  Throws:
    `java.lang.IndexOutOfBoundsException` - if `(index < 0) || (index >= size())`

### add

    public final void add(int index,
                          E value)

  Inserts the specified value at the specified position in this list. Shifts the value currently at that position (if any) and any subsequent values to the right (adds one to their indices).

  Specified by:
    `add` in interface `java.util.List<E>`
  Parameters:
    `index` - the index at which the specified value is to be inserted.
    `value` - the value to be inserted.
  Throws:
    `java.lang.IndexOutOfBoundsException` - if `(index < 0) || (index > size())`

### addAll

    public final boolean addAll(int index,
                                java.util.Collection<? extends E> values)

  Inserts all of the values in the specified collection into this list at the specified position. Shifts the value currently at that position (if any) and any subsequent values to the right (increases their indices).

  Specified by:
    `addAll` in interface `java.util.List<E>`
  Parameters:
    `index` - the index at which to insert first value from the specified collection.
    `values` - the values to be inserted into this list.
  Returns:
    `true` if this list changed as a result of the call; `false` otherwise.
  Throws:
    `java.lang.IndexOutOfBoundsException` - if `(index < 0) || (index > size())`

### remove

    public final E remove(int index)

  Removes the value at the specified position in this list. Shifts any subsequent values to the left (subtracts one from their indices). Returns the value that was removed from the list.

  Specified by:
    `remove` in interface `java.util.List<E>`
  Parameters:
    `index` - the index of the value to removed.
  Returns:
    the value previously at the specified position.
  Throws:
    `java.lang.IndexOutOfBoundsException` - if `(index < 0) || (index >= size())`

### indexOf

    public final int indexOf(java.lang.Object value)

  Returns the index in this list of the first occurrence of the specified value, or -1 if this list does not contain this value.

  Specified by:
    `indexOf` in interface `java.util.List<E>`
  Parameters:
    `value` - the value to search for.
  Returns:
    the index in this list of the first occurrence of the specified value, or -1 if this list does not contain this value.

### lastIndexOf

    public final int lastIndexOf(java.lang.Object value)

  Returns the index in this list of the last occurrence of the specified value, or -1 if this list does not contain this value.

  Specified by:
    `lastIndexOf` in interface `java.util.List<E>`
  Parameters:
    `value` - the value to search for.
  Returns:
    the index in this list of the last occurrence of the specified value, or -1 if this list does not contain this value.

### iterator

    public java.util.Iterator<E> iterator()

  Returns a simple iterator over the elements in this list (allocated on the stack when executed in a `StackContext`).

  Specified by:
    `iterator` in interface `java.lang.Iterable<E>`
  Specified by:
    `iterator` in interface `java.util.Collection<E>`
  Specified by:
    `iterator` in interface `java.util.List<E>`
  Overrides:
    `iterator` in class `FastCollection<E>`
  Returns:
    an iterator over this list values.

### listIterator

    public java.util.ListIterator<E> listIterator()

  Returns a list iterator over the elements in this list (allocated on the stack when executed in a `StackContext`).

  Specified by:
    `listIterator` in interface `java.util.List<E>`
  Returns:
    an iterator over this list values.

### listIterator

    public java.util.ListIterator<E> listIterator(int index)

  Returns a list iterator from the specified position (allocated on the stack when executed in a `StackContext`). The specified index indicates the first value that would be returned by an initial call to the `next` method. An initial call to the `previous` method would return the value with the specified index minus one.

  Specified by:
    `listIterator` in interface `java.util.List<E>`
  Parameters:
    `index` - index of first value to be returned from the list iterator (by a call to the `next` method).
  Returns:
    a list iterator over the values in this list starting at the specified position in this list.
  Throws:
    `java.lang.IndexOutOfBoundsException` - if the index is out of range `

        (index < 0 || index > size())

    `.

### subList

    public final java.util.List<E> subList(int fromIndex,
                                           int toIndex)

  Returns a view of the portion of this list between the specified indexes (allocated from the "stack" when executing in a `StackContext`). If the specified indexes are equal, the returned list is empty. The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa. 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 values 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 the 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).

  Specified by:
    `subList` in interface `java.util.List<E>`
  Parameters:
    `fromIndex` - low endpoint (inclusive) of the subList.
    `toIndex` - high endpoint (exclusive) of the subList.
  Returns:
    a view of the specified range within this list.
  Throws:
    `java.lang.IndexOutOfBoundsException` - if `

        (fromIndex < 0 ||
                  toIndex > size || fromIndex < toIndex)

    `

### getFirst

    public final E getFirst()

  Returns the first value of this list.

  Returns:
    this list's first value.
  Throws:
    `java.util.NoSuchElementException` - if this list is empty.

### getLast

    public final E getLast()

  Returns the last value of this list.

  Returns:
    this list's last value.
  Throws:
    `java.util.NoSuchElementException` - if this list is empty.

### addFirst

    public final void addFirst(E value)

  Inserts the specified value at the beginning of this list.

  Parameters:
    `value` - the value to be inserted.

### addLast

    public void addLast(E value)

  Appends the specified value to the end of this list (fast).

  Parameters:
    `value` - the value to be inserted.

### removeFirst

    public final E removeFirst()

  Removes and returns the first value of this list.

  Returns:
    this list's first value before this call.
  Throws:
    `java.util.NoSuchElementException` - if this list is empty.

### removeLast

    public final E removeLast()

  Removes and returns the last value of this list (fast).

  Returns:
    this list's last value before this call.
  Throws:
    `java.util.NoSuchElementException` - if this list is empty.

### addBefore

    public final void addBefore(FastList.Node<E> next,
                                E value)

  Inserts the specified value before the specified Node.

  Parameters:
    `next` - the Node before which this value is inserted.
    `value` - the value to be inserted.

### head

    public final FastList.Node<E> head()

  Description copied from class: `FastCollection`
  Returns the head record of this collection; it is the record such as `head().getNext()` holds the first collection value.

  Specified by:
    `head` in class `FastCollection<E>`
  Returns:
    the head record.

### tail

    public final FastList.Node<E> tail()

  Description copied from class: `FastCollection`
  Returns the tail record of this collection; it is the record such as `tail().getPrevious()` holds the last collection value.

  Specified by:
    `tail` in class `FastCollection<E>`
  Returns:
    the tail record.

### valueOf

    public final E valueOf(FastCollection.Record record)

  Description copied from class: `FastCollection`
  Returns the collection value for the specified record.

  Specified by:
    `valueOf` in class `FastCollection<E>`
  Parameters:
    `record` - the record whose current value is returned.
  Returns:
    the current value.

### delete

    public final void delete(FastCollection.Record record)

  Description copied from class: `FastCollection`
  Deletes the specified record from this collection.

  Implementation must ensure that removing a record from the collection does not affect in any way the records preceding the record being removed (it might affect the next records though, e.g. in a list collection, the indices of the subsequent records will change).

  Specified by:
    `delete` in class `FastCollection<E>`
  Parameters:
    `record` - the record to be removed.

### contains

    public final boolean contains(java.lang.Object value)

  Description copied from class: `FastCollection`
  Indicates if this collection contains the specified value.

  Specified by:
    `contains` in interface `java.util.Collection<E>`
  Specified by:
    `contains` in interface `java.util.List<E>`
  Overrides:
    `contains` in class `FastCollection<E>`
  Parameters:
    `value` - the value whose presence in this collection is to be tested.
  Returns:
    `true` if this collection contains the specified value;`false` otherwise.

### size

    public final int size()

  Description copied from class: `FastCollection`
  Returns the number of values in this collection.

  Specified by:
    `size` in interface `java.util.Collection<E>`
  Specified by:
    `size` in interface `java.util.List<E>`
  Specified by:
    `size` in class `FastCollection<E>`
  Returns:
    the number of values.

### clear

    public final void clear()

  Description copied from class: `FastCollection`
  Removes all of the values from this collection (optional operation).

  Specified by:
    `clear` in interface `java.util.Collection<E>`
  Specified by:
    `clear` in interface `java.util.List<E>`
  Overrides:
    `clear` in class `FastCollection<E>`

### setValueComparator

    public FastList<E> setValueComparator(FastComparator<? super E> comparator)

  Sets the comparator to use for value equality.

  Parameters:
    `comparator` - the value comparator.
  Returns:
    `this`

### getValueComparator

    public FastComparator<? super E> getValueComparator()

  Description copied from class: `FastCollection`
  Returns the value comparator for this collection (default `FastComparator.DEFAULT`).

  Overrides:
    `getValueComparator` in class `FastCollection<E>`
  Returns:
    the comparator to use for value equality (or ordering if the collection is ordered)

### unmodifiable

    public java.util.List<E> unmodifiable()

  Description copied from class: `FastCollection`
  Returns the unmodifiable view associated to this collection. Attempts to modify the returned collection result in an `UnsupportedOperationException` being thrown. The view is always a `FastCollection` instance.

  Overrides:
    `unmodifiable` in class `FastCollection<E>`
  Returns:
    the unmodifiable view over this collection.

### newNode

    protected FastList.Node<E> newNode()

  Returns a new node for this list; this method can be overriden by custom list implementation.

  Returns:
    a new node.

### reset

    public void reset()

  Description copied from interface: `Reusable`
  Resets the internal state of this object to its default values.

  Specified by:
    `reset` in interface `Reusable`

Overview | Package | Class | Tree | Deprecated | Index | Help
| J avolution v5.3 (J2SE 1.5+)
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2005 - 2009 Javolution.