Class TreeList<E>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractList<E>
-
- org.apache.commons.collections4.list.TreeList<E>
-
- All Implemented Interfaces:
java.lang.Iterable<E>
,java.util.Collection<E>
,java.util.List<E>
public class TreeList<E> extends java.util.AbstractList<E>
AList
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 aLinkedList
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 thanTreeList
for most operations except inserting and removing in the middle of the list.ArrayList
also uses less memory asTreeList
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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
TreeList.AVLNode<E>
Implements an AVLNode which keeps the offset updated.(package private) static class
TreeList.TreeListIterator<E>
A list iterator over the linked list.
-
Field Summary
Fields Modifier and Type Field Description private TreeList.AVLNode<E>
root
The root node in the AVL treeprivate int
size
The current size of the list
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(int index, E obj)
Adds a new element to the list.boolean
addAll(java.util.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.private void
checkInterval(int index, int startIndex, int endIndex)
Checks whether the index is valid.void
clear()
Clears the list, removing all entries.boolean
contains(java.lang.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(java.lang.Object object)
Searches for the index of an object in the list.java.util.Iterator<E>
iterator()
Gets an iterator over the list.java.util.ListIterator<E>
listIterator()
Gets a ListIterator over the list.java.util.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.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
containsAll, isEmpty, remove, removeAll, retainAll, toArray, toString
-
-
-
-
Field Detail
-
root
private TreeList.AVLNode<E> root
The root node in the AVL tree
-
size
private int size
The current size of the list
-
-
Constructor Detail
-
TreeList
public TreeList()
Constructs a new empty list.
-
TreeList
public TreeList(java.util.Collection<? extends E> coll)
Constructs a new empty list that copies the specified collection.- Parameters:
coll
- the collection to copy- Throws:
java.lang.NullPointerException
- if the collection is null
-
-
Method Detail
-
get
public E get(int index)
Gets the element at the specified index.
-
size
public int size()
Gets the current size of the list.
-
iterator
public java.util.Iterator<E> iterator()
Gets an iterator over the list.
-
listIterator
public java.util.ListIterator<E> listIterator()
Gets a ListIterator over the list.
-
listIterator
public java.util.ListIterator<E> listIterator(int fromIndex)
Gets a ListIterator over the list.
-
indexOf
public int indexOf(java.lang.Object object)
Searches for the index of an object in the list.
-
contains
public boolean contains(java.lang.Object object)
Searches for the presence of an object in the list.
-
toArray
public java.lang.Object[] toArray()
Converts the list into an array.
-
add
public void add(int index, E obj)
Adds a new element to the list.
-
addAll
public boolean addAll(java.util.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 interfacejava.util.Collection<E>
- Specified by:
addAll
in interfacejava.util.List<E>
- Overrides:
addAll
in classjava.util.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:
java.lang.NullPointerException
-
remove
public E remove(int index)
Removes the element at the specified index.
-
clear
public void clear()
Clears the list, removing all entries.
-
checkInterval
private void checkInterval(int index, int startIndex, int endIndex)
Checks whether the index is valid.- Parameters:
index
- the index to checkstartIndex
- the first allowed indexendIndex
- the last allowed index- Throws:
java.lang.IndexOutOfBoundsException
- if the index is invalid
-
-