org.apache.commons.collections4.list

## Class TreeList<E>

- java.lang.Object
- - java.util.AbstractCollection<E>
  - - java.util.AbstractList<E>
    - - org.apache.commons.collections4.list.TreeList<E>

- All Implemented Interfaces:
    Iterable<E>, Collection<E>, List<E>

      public class TreeList<E>
      extends AbstractList<E>

  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 slightly more memory.

  Since:
    3.1
  Version:
    $Id: TreeList.java 1533984 2013-10-20 21:12:51Z tn $

- - ### Field Summary

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

      `modCount`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `TreeList()` Constructs a new empty list.
    `TreeList(Collection<? extends E> coll)` Constructs a new empty list that copies the specified collection.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `add(int index, E obj)` Adds a new element to the list.
    `boolean` | `addAll(Collection<? extends E> c)` Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's Iterator.
    `void` | `clear()` Clears the list, removing all entries.
    `boolean` | `contains(Object object)` Searches for the presence of an object in the list.
    `E` | `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<E>` | `iterator()` Gets an iterator over the list.
    `ListIterator<E>` | `listIterator()` Gets a ListIterator over the list.
    `ListIterator<E>` | `listIterator(int fromIndex)` Gets a ListIterator over the list.
    `E` | `remove(int index)` Removes the element at the specified index.
    `E` | `set(int index, E 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

      `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

      `containsAll, isEmpty, remove, removeAll, retainAll, toArray`

- - ### Constructor Detail

    - #### TreeList

          public TreeList()

      Constructs a new empty list.

    - #### TreeList

          public TreeList(Collection<? extends E> coll)

      Constructs a new empty list that copies the specified collection.
      Parameters:
        `coll` - the collection to copy
      Throws:
        `NullPointerException` - if the collection is null

  - ### Method Detail

    - #### get

          public E get(int index)

      Gets the element at the specified index.
      Specified by:
        `get` in interface `List<E>`
      Specified by:
        `get` in class `AbstractList<E>`
      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<E>`
      Specified by:
        `size` in interface `List<E>`
      Specified by:
        `size` in class `AbstractCollection<E>`
      Returns:
        the current size

    - #### iterator

          public Iterator<E> iterator()

      Gets an iterator over the list.
      Specified by:
        `iterator` in interface `Iterable<E>`
      Specified by:
        `iterator` in interface `Collection<E>`
      Specified by:
        `iterator` in interface `List<E>`
      Overrides:
        `iterator` in class `AbstractList<E>`
      Returns:
        an iterator over the list

    - #### listIterator

          public ListIterator<E> listIterator()

      Gets a ListIterator over the list.
      Specified by:
        `listIterator` in interface `List<E>`
      Overrides:
        `listIterator` in class `AbstractList<E>`
      Returns:
        the new iterator

    - #### listIterator

          public ListIterator<E> listIterator(int fromIndex)

      Gets a ListIterator over the list.
      Specified by:
        `listIterator` in interface `List<E>`
      Overrides:
        `listIterator` in class `AbstractList<E>`
      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<E>`
      Overrides:
        `indexOf` in class `AbstractList<E>`
      Parameters:
        `object` - the object to search
      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<E>`
      Specified by:
        `contains` in interface `List<E>`
      Overrides:
        `contains` in class `AbstractCollection<E>`
      Parameters:
        `object` - the object to check
      Returns:
        true if the object is found

    - #### toArray

          public Object[] toArray()

      Converts the list into an array.
      Specified by:
        `toArray` in interface `Collection<E>`
      Specified by:
        `toArray` in interface `List<E>`
      Overrides:
        `toArray` in class `AbstractCollection<E>`
      Returns:
        the list as an array

    - #### add

          public void add(int index,
                 E obj)

      Adds a new element to the list.
      Specified by:
        `add` in interface `List<E>`
      Overrides:
        `add` in class `AbstractList<E>`
      Parameters:
        `index` - the index to add before
        `obj` - the element to add

    - #### addAll

          public boolean addAll(Collection<? extends E> c)

      Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's Iterator.

      This method runs in O(n + log m) time, where m is the size of this list and n is the size of `c`.

      Specified by:
        `addAll` in interface `Collection<E>`
      Specified by:
        `addAll` in interface `List<E>`
      Overrides:
        `addAll` in class `AbstractCollection<E>`
      Parameters:
        `c` - the collection to be added to this list
      Returns:
        `true` if this list changed as a result of the call
      Throws:
        `NullPointerException`

    - #### set

          public E set(int index,
              E obj)

      Sets the element at the specified index.
      Specified by:
        `set` in interface `List<E>`
      Overrides:
        `set` in class `AbstractList<E>`
      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 E remove(int index)

      Removes the element at the specified index.
      Specified by:
        `remove` in interface `List<E>`
      Overrides:
        `remove` in class `AbstractList<E>`
      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<E>`
      Specified by:
        `clear` in interface `List<E>`
      Overrides:
        `clear` in class `AbstractList<E>`

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