Package 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 optimized 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

- ## Field Summary

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

  `modCount`

- ## Constructor Summary

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

- ## Method Summary

  Modifier and Type
  Method
  Description
  `void`
  `add(int index, E obj)`
  Adds a new element to the list.
  `boolean`
  `addAll(Collection<? extends E> c)`
  Appends all 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.Collection

  `parallelStream, removeIf, stream`

  ### Methods inherited from interface java.lang.Iterable

  `forEach`

  ### Methods inherited from interface java.util.List

  `containsAll, isEmpty, remove, removeAll, replaceAll, retainAll, sort, spliterator, toArray`

- ## Constructor Details

  - ### 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 Details

  - ### 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 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`

  - ### 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>`

  - ### 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

  - ### 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

  - ### 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

  - ### iterator

    public Iterator<E> iterator()
    Gets an iterator over the list.
    Specified by:
      `iterator` in interface `Collection<E>`
    Specified by:
      `iterator` in interface `Iterable<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

  - ### 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

  - ### 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

  - ### 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

  - ### 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