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:
    Iterable, 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: 1713536 $ $Date: 2015-11-09 21:53:04 +0100 (Mon, 09 Nov 2015) $
  Author:
    Joerg Schmuecker, Stephen Colebourne

- - ### Field Summary

    - ### Fields inherited from class java.util.AbstractList

      `modCount`

  - ### Constructor Summary

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

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `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 `Collection`
      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 `Iterable`
      Specified by:
        `iterator` in interface `Collection`
      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 `Collection`
      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 `Collection`
      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 `Collection`
      Specified by:
        `clear` in interface `List`
      Overrides:
        `clear` in class `AbstractList`

Copyright © 2001–2015 The Apache Software Foundation. All rights reserved.