每个程序员都应该掌握的数据结构 – Unrolled List

Unrolled List

链表是我们每个程序员都烂熟于胸的一个数据结构，它有很多优点，递归的结构，动态的节点内存分配适应不确定长度的情况，但是它的这些特性决定了它会导致内存的碎片化，访问的冗余化——总是先访问指针，再访问指针指向的内存内容，所以如果长度确定，那么数组显然是更好的选择，数组能够保持连续的内存分配，更快的访问速度。

Unrolled List就是这样一个折中的实现，它在标准链表的节点存储了一个不定长数组来保存部分原来需要link来迭代访问的后续节点，增加了操作的复杂性，比如每个节点应该如何决定存多少个值，每个节点要存相同数量的值吗，扩展的思考能带来一些轻微不同的实现，但总体来说它比原来的链表具有更小的内存用量，更好的效率，在动态增长方面又强于数组。可能标准的C++程序员会建议直接使用vector，很好的效率，动态的增长，也是非常不错的选择，这个系列的目的在于我们能不能从一些数据结构的设计来思考一些更抽象范围内的设计思路。比如在复杂性和效率之间的折中，在空间与时间之间的折中。

template < typename T >

struct UnrolledListNode{

    T* items;

    int items_length;

    UnrolledListNode* next;

}

以上。