Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.commons.collections.list
Class TreeList

    java.lang.Object
      |
      +--java.util.AbstractCollection
            |
            +--java.util.AbstractList
                  |
                  +--org.apache.commons.collections.list.TreeList

All Implemented Interfaces:
  Collection, List

public class TreeList
extends AbstractList

A `List` implementation that is optimised for fast insertions and removals at any index in the list.

This list implementation utilises a tree structure internally to ensure that all insertions and removals are O(log n). This provides much faster performance than both an `ArrayList` and a `LinkedList` where elements are inserted and removed repeatedly from anywhere in the list.

The following relative performance statistics are indicative of this class:

                  get  add  insert  iterate  remove
     TreeList       3    5       1       2       1
     ArrayList      1    1      40       1      40
     LinkedList  5800    1     350       2     325

`ArrayList` is a good general purpose list implementation. It is faster than `TreeList` for most operations except inserting and removing in the middle of the list. `ArrayList` also uses less memory as `TreeList` uses one object per entry.

`LinkedList` is rarely a good choice of implementation. `TreeList` is almost always a good replacement for it, although it does use sligtly more memory.

Since:
  Commons Collections 3.1
Version:
  $Revision: 1.3 $ $Date: 2004/05/26 21:56:05 $
Author:
  Joerg Schmuecker, Stephen Colebourne

Field Summary

Fields inherited from class java.util.AbstractList
`modCount`

Constructor Summary
`TreeList()` Constructs a new empty list.
`TreeList(Collection coll)` Constructs a new empty list that copies the specified list.

Method Summary
`void` | `add(int index, Object obj)` Adds a new element to the list.
`void` | `clear()` Clears the list, removing all entries.
`boolean` | `contains(Object object)` Searches for the presence of an object in the list.
`Object` | `get(int index)` Gets the element at the specified index.
`int` | `indexOf(Object object)` Searches for the index of an object in the list.
`Iterator` | `iterator()` Gets an iterator over the list.
`ListIterator` | `listIterator()` Gets a ListIterator over the list.
`ListIterator` | `listIterator(int fromIndex)` Gets a ListIterator over the list.
`Object` | `remove(int index)` Removes the element at the specified index.
`Object` | `set(int index, Object obj)` Sets the element at the specified index.
`int` | `size()` Gets the current size of the list.
`Object[]` | `toArray()` Converts the list into an array.

Methods inherited from class java.util.AbstractList
`add, addAll, equals, hashCode, lastIndexOf, removeRange, subList`

Methods inherited from class java.util.AbstractCollection
`addAll, containsAll, isEmpty, remove, 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.List
`addAll, containsAll, isEmpty, remove, removeAll, retainAll, toArray`

Constructor Detail

### TreeList

    public TreeList()

  Constructs a new empty list.

### TreeList

    public TreeList(Collection coll)

  Constructs a new empty list that copies the specified list.

Parameters:
  `coll` - the collection to copy
Throws:
  `NullPointerException` - if the collection is null

Method Detail

### get

    public Object get(int index)

  Gets the element at the specified index.

  Specified by:
    `get` in interface `List`
  Specified by:
    `get` in class `AbstractList`
  Parameters:
    `index` - the index to retrieve
  Returns:
    the element at the specified index

### size

    public int size()

  Gets the current size of the list.

  Specified by:
    `size` in interface `List`
  Specified by:
    `size` in class `AbstractCollection`
  Returns:
    the current size

### iterator

    public Iterator iterator()

  Gets an iterator over the list.

  Specified by:
    `iterator` in interface `List`
  Overrides:
    `iterator` in class `AbstractList`
  Returns:
    an iterator over the list

### listIterator

    public ListIterator listIterator()

  Gets a ListIterator over the list.

  Specified by:
    `listIterator` in interface `List`
  Overrides:
    `listIterator` in class `AbstractList`
  Returns:
    the new iterator

### listIterator

    public ListIterator listIterator(int fromIndex)

  Gets a ListIterator over the list.

  Specified by:
    `listIterator` in interface `List`
  Overrides:
    `listIterator` in class `AbstractList`
  Parameters:
    `fromIndex` - the index to start from
  Returns:
    the new iterator

### indexOf

    public int indexOf(Object object)

  Searches for the index of an object in the list.

  Specified by:
    `indexOf` in interface `List`
  Overrides:
    `indexOf` in class `AbstractList`
  Returns:
    the index of the object, -1 if not found

### contains

    public boolean contains(Object object)

  Searches for the presence of an object in the list.

  Specified by:
    `contains` in interface `List`
  Overrides:
    `contains` in class `AbstractCollection`
  Returns:
    true if the object is found

### toArray

    public Object[] toArray()

  Converts the list into an array.

  Specified by:
    `toArray` in interface `List`
  Overrides:
    `toArray` in class `AbstractCollection`
  Returns:
    the list as an array

### add

    public void add(int index,
                    Object obj)

  Adds a new element to the list.

  Specified by:
    `add` in interface `List`
  Overrides:
    `add` in class `AbstractList`
  Parameters:
    `index` - the index to add before
    `obj` - the element to add

### set

    public Object set(int index,
                      Object obj)

  Sets the element at the specified index.

  Specified by:
    `set` in interface `List`
  Overrides:
    `set` in class `AbstractList`
  Parameters:
    `index` - the index to set
    `obj` - the object to store at the specified index
  Returns:
    the previous object at that index
  Throws:
    `IndexOutOfBoundsException` - if the index is invalid

### remove

    public Object remove(int index)

  Removes the element at the specified index.

  Specified by:
    `remove` in interface `List`
  Overrides:
    `remove` in class `AbstractList`
  Parameters:
    `index` - the index to remove
  Returns:
    the previous object at that index

### clear

    public void clear()

  Clears the list, removing all entries.

  Specified by:
    `clear` in interface `List`
  Overrides:
    `clear` in class `AbstractList`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2001-2004 Apache Software Foundation. All Rights Reserved.