## 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:
  java.lang.Iterable, java.util.Collection, java.util.List

    public class TreeList

extends java.util.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: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
Author:
  Joerg Schmuecker, Stephen Colebourne

Field Summary

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

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

Method Summary
`void` `add(int index, java.lang.Object obj)` Adds a new element to the list.
`void` `clear()` Clears the list, removing all entries.
`boolean` `contains(java.lang.Object object)` Searches for the presence of an object in the list.
`java.lang.Object` `get(int index)` Gets the element at the specified index.
`int` `indexOf(java.lang.Object object)` Searches for the index of an object in the list.
`java.util.Iterator` `iterator()` Gets an iterator over the list.
`java.util.ListIterator` `listIterator()` Gets a ListIterator over the list.
`java.util.ListIterator` `listIterator(int fromIndex)` Gets a ListIterator over the list.
`java.lang.Object` `remove(int index)` Removes the element at the specified index.
`java.lang.Object` `set(int index, java.lang.Object obj)` Sets the element at the specified index.
`int` `size()` Gets the current size of the list.
`java.lang.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(java.util.Collection coll)

  Constructs a new empty list that copies the specified list.

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

Method Detail

### get

    public java.lang.Object get(int index)

  Gets the element at the specified index.

  Specified by:
    `get` in interface `java.util.List`
  Specified by:
    `get` in class `java.util.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 `java.util.Collection`
  Specified by:
    `size` in interface `java.util.List`
  Specified by:
    `size` in class `java.util.AbstractCollection`
  Returns:
    the current size

### iterator

    public java.util.Iterator iterator()

  Gets an iterator over the list.

  Specified by:
    `iterator` in interface `java.lang.Iterable`
  Specified by:
    `iterator` in interface `java.util.Collection`
  Specified by:
    `iterator` in interface `java.util.List`
  Overrides:
    `iterator` in class `java.util.AbstractList`
  Returns:
    an iterator over the list

### listIterator

    public java.util.ListIterator listIterator()

  Gets a ListIterator over the list.

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

### listIterator

    public java.util.ListIterator listIterator(int fromIndex)

  Gets a ListIterator over the list.

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

### indexOf

    public int indexOf(java.lang.Object object)

  Searches for the index of an object in the list.

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

### contains

    public boolean contains(java.lang.Object object)

  Searches for the presence of an object in the list.

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

### toArray

    public java.lang.Object[] toArray()

  Converts the list into an array.

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

### add

    public void add(int index,
                    java.lang.Object obj)

  Adds a new element to the list.

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

### set

    public java.lang.Object set(int index,
                                java.lang.Object obj)

  Sets the element at the specified index.

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

### remove

    public java.lang.Object remove(int index)

  Removes the element at the specified index.

  Specified by:
    `remove` in interface `java.util.List`
  Overrides:
    `remove` in class `java.util.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 `java.util.Collection`
  Specified by:
    `clear` in interface `java.util.List`
  Overrides:
    `clear` in class `java.util.AbstractList`

Copyright © 2001-2008 The Apache Software Foundation. All Rights Reserved.