当前位置:编程学习 > JAVA >>

分享代码系列——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后半部分的数据的操作具有很好的性能,像个数组,但是又和其前半部分有快速的链接关系,对于其数组的不可变性也是最好的用于函数式编程的典范(来源于wikipedia的翻译)
源代码如下,继承了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.补充:软件开发 , Java ,

CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,