T
- type of list element.public class BlockList<T>
extends java.util.AbstractList<T>
Unlike ArrayList
, this type does not need to reallocate the
internal array in order to expand the capacity of the list. Access to any
element is constant time, but requires two array lookups instead of one.
To handle common usages, add(Object)
and iterator()
use
internal code paths to amortize out the second array lookup, making addition
and simple iteration closer to one array operation per element processed.
Similar to ArrayList
, adding or removing from any position except the
end of the list requires O(N) time to copy all elements between the
modification point and the end of the list. Applications are strongly
encouraged to not use this access pattern with this list implementation.
Modifier and Type | Class and Description |
---|---|
private class |
BlockList.MyIterator |
Modifier and Type | Field and Description |
---|---|
private static int |
BLOCK_BITS |
private static int |
BLOCK_MASK |
(package private) static int |
BLOCK_SIZE |
(package private) T[][] |
directory |
(package private) int |
size |
private int |
tailBlkIdx |
private T[] |
tailBlock |
private int |
tailDirIdx |
Constructor and Description |
---|
BlockList()
Initialize an empty list.
|
BlockList(int capacity)
Initialize an empty list with an expected capacity.
|
Modifier and Type | Method and Description |
---|---|
void |
add(int index,
T element) |
boolean |
add(T element) |
void |
addAll(BlockList<T> src)
Quickly append all elements of another BlockList.
|
void |
addAll(T[] src,
int srcIdx,
int srcCnt)
Quickly append all elements from an array.
|
void |
clear() |
T |
get(int index) |
java.util.Iterator<T> |
iterator() |
private static <T> T[] |
newBlock() |
private static <T> T[][] |
newDirectory(int size) |
T |
remove(int index) |
private void |
resetTailBlock() |
T |
set(int index,
T element) |
int |
size() |
(package private) static int |
toBlockIndex(int index) |
(package private) static int |
toDirectoryIndex(int index) |
addAll, equals, hashCode, indexOf, lastIndexOf, listIterator, listIterator, removeRange, subList
addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
private static final int BLOCK_BITS
static final int BLOCK_SIZE
private static final int BLOCK_MASK
T[][] directory
int size
private int tailDirIdx
private int tailBlkIdx
private T[] tailBlock
public BlockList()
public BlockList(int capacity)
capacity
- number of elements expected to be in the list.public int size()
public void clear()
public T get(int index)
public void addAll(BlockList<T> src)
src
- the list to copy elements from.public void addAll(T[] src, int srcIdx, int srcCnt)
src
- the source array.srcIdx
- first index to copy.srcCnt
- number of elements to copy.public boolean add(T element)
public void add(int index, T element)
public T remove(int index)
private void resetTailBlock()
public java.util.Iterator<T> iterator()
static final int toDirectoryIndex(int index)
static final int toBlockIndex(int index)
private static <T> T[][] newDirectory(int size)
private static <T> T[] newBlock()