分享代码系列——vlist
vlist是一种列表的实现。结构如下图：
类似链接表的结构，但是，不是线性的。它的结构基于一种2的幂次扩展，第一个链接节点包含了列表的前一半数据，第二个包含了剩下一半的一半，依次递归。节点的基本结构不像LinkedList的节点是双端队列，每个VListCell包含了下个节点的指针mNext和前一个节点的指针mPrev，同时内置一个数组mElems用来存放当前节点的数据集合，包含一个数字指针指向当前数组元素的位置。举个例子，如果有个Vlist包含10个元素，分别是1-10的整数，而且是按升序顺序插入的，那么vlist的结构数据时这样的：
VList基于数组实现，在add操作时，每次会把元素插入到list的最前面一个节点内的mElems的最后一个位置，首先判断head，如果head的元素数组已经满了，那么就增加一个头节点并扩容其elems数组为2倍，然后插入到位置指针所指向的地方去，时间是O(1)的。而在get操作时，要首先定位第n个元素的位置，会进行一次locate定位操作，接着直接返回数组中的该locate位置即可。定位操作实质是二分的，但是因为VList本身就是一个单向的二分表，因此顺序判断即可，时间复杂度是平均O(1)和最坏情况O(log n)。对应get的set操作，复杂度和步骤完全一样。当然最最恶心的还是remove操作了，因为基于数组，且本身结构有意义（特定的），所以删除会复杂一些，首先一个O(log n)的locate定位，找到元素后，删掉之后，是把它之前的所有元素后移一位，当然这个移位操作并不是特别复杂，只要把当前节点的全部后移，然后如果当前节点有前驱节点，那么前驱的最后一个元素覆盖当前节点第一个元素，如此反复直到当前节点指针为空结束，时间复杂度是O(n)的。
我做了一个perf test来测试性能，发现这个不伦不类的list在arralist和linkedlist面前显得是脆弱的。那它的作用体现在哪里呢？简单的设计和良好的结构，满足add和get的平衡，对于list后半部分的数据的操作具有很好的性能，像个数组，但是又和其前半部分有快速的链接关系，对于其数组的不可变性也是最好的用于函数式编程的典范（来源于易做图的翻译）
源代码如下，继承了jdk中的AbstractList<T>：
1: public final class VList<T> extends AbstractList<T> {
2:
3: /**
4: * A single cell in the VList implementation.
5: */
6: private static final class VListCell<T> {
7: public final T[] mElems;
8: public final VListCell<T> mNext;
9:
10: /*
11: * This field is not mutable because when new elements are added/deleted
12: * from the main list, the previous pointer needs to be updated.
13: * However, next links never change because the list only grows in one
14: * direction.
15: */
16: public VListCell<T> mPrev;
17:
18: /*
19: * The number of unused elements in this cell. Alternatively, you can
20: * think of this as the index in the array in which the first used
21: * element appears. Both interpretations are used in this
22: * implementation.
23: */
24: public int mFreeSpace;
25:
26: /**
27: * Constructs a new VListCell with the specified number of elements and
28: * specified next element.
29: *
30: * @param numElems
31: * The number of elements this cell should have space for.
32: * @param next
33: * The cell in the list of cells that follows this one.
34: */
35: public VListCell(int numElems, VListCell<T> next) {
36: mElems = (T[]) new Object[numElems];
37: mNext = next;
38: mPrev = null;
39:
40: /* Update the next cell to point back to us. */
41: if (next != null)
42: next.mPrev = this;
43:
44: /* We have free space equal to the number of elements. */
45: mFreeSpace = numElems;
46: }
47: }
48:
49: /**
50: * A utility struct containing information about where an element is in the
51: * VList. Methods that need to manipulate individual elements of the list
52: * use this struct to communicate where in the list to look for that
53: * element.
54: */
55: private static final class VListLocation<T> {
56: public final VListCell<T> mCell;
57: public final int mOffset;
58:
59: public VListLocation(VListCell<T> cell, int offset) {
60: mCell = cell;
61: mOffset = offset;
62: }
63: }
64:
65: /*
66: * Pointer to the head of the VList, which contains the final elements of
67: * the list.
