Package org.apache.commons.collections.list

Class TreeList

java.lang.Object
java.util.AbstractCollection<E>
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

  • Constructor Details

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

    • 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 Collection
      Specified by:
      iterator in interface Iterable
      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