一般传统链表的物理结构，是由指针把一个一个的节点相互连接而成：
view sourceprint?1 struct node
2 {
3 DataType data;
4 node* previous;
5 node* next;
6 }
其特点是按需分配节点，灵活动态增长。
但是此外，还有另外一种方式是使用数组实现链表，这里所有的node都在预先分配好的数组中，不使用指针，而是用数组下标来指向前一个、下一个元素：
view sourceprint?1 struct node
2 {
3 DataType data;
4 int previous;
5 int next;
6 }
其特点是预先分配节点，并且如果需要链表长度随需增加，需要reallocation ,和vector类似。
下面就我自己的一些了解，谈一下其优缺点与应用。
数组作链表有哪些优点
能要省些内存吗？不见得；速度要快吗？没看出来，那么为什么要使用这种不那么直观的方式来实现链表呢？
数组的内存布局比较紧凑，能占些局部性原理的光 在不提供指针的语言中实现链表结构，如vb等 进程间通信，使用index比使用指针是要靠谱 - 一个进程中的指针地址在另外一个进程中是没有意义的 对一些内存奇缺应用，当其值类型为整型，且值域与数组index相符时，可以将next指针与data复用，从而节省一些内存
实现与应用
Id allocator
这里第一个例子针对上面第四点展开，其主要的应用在于ID的分配与回收，比如数据库表中的每条记录都需要一个unique id，当你增增减减若干次之后，然后新建一个表项，你该分配给它哪个id呢？
维持一个id，每增加一行就加1，删行不回收id --- 这样id会无限增加，太浪费了 每次分配都遍历一遍，找到最小的那个还没被用过的id --- 这样太浪费时间了
一个比较合理的做法是维护一个“可用ID”的链表，每次增加就从链表中拿一个，每次删除就把被删的ID链接到链表中，但是，对于传统链表结构而言，其节点的定义类似于：
view sourceprint?1 struct idnode
2 {
3 int availableID;
4 idnode* next;
5 };
这里，因为链表的值的类型与值域都与数组的index相符，我们可以复用其值和next，从而只需一个int数组，而不是一个idnode数组，数组中某个元素的值代表的即是链表节点的值，也是链表的下一个节点下标。下面是一个idallocator的实现，主要提供allocate和free两个函数用来满足上述要求：
view sourceprint?01 const static char LIST_END = -1;
02 template < typename integer>
03 class idallocator
04 {
05 public:
06 idallocator(int _num): num(_num)
07 {
08 array = new integer[num];
09 // Initialize the linked list. Initially, it is a full linked list with all elements linked one after another.
10 head = 0;
11 for (integer i = 0; i < num; i++)
12 {
13 array[i] = i + 1;
14 }
15 array[num-1] = LIST_END;
16 count = num;
17 }
18 ~idallocator()
19 {
20 delete [] array;
21 }
22 integer allocate() // pop_front, remove a node from the front
23 {
24 int id = head;
25 if(id != LIST_END)
26 {
27 head = array[head];
28 count--;
29 }
30 return id;
31 }
32 // push_front, add a new node to the front
33 void free(const integer& id)
34 {
35 array[id] = head;
36 count++;
37 head = id;
38 }
39 // push_front, add a new node to the front
40 bool free_s(const integer& id)
41 {
42 // make sure this id is not in the list before we add it
43 if(exist(id)) return false;
44 free(id);
45 return true;
46 }
47 size_t size()
48 {
49 return count;
50 }
51 private:
52 bool exist(const integer& id)
53 {
54 int i = head;
55 while (i != LIST_END)
56 {
57 if(i == id) return true;
58 i = array[i];
59 }
60 return false;
61 }
62 private:
63 integer* array;
64 int num;// totall number of the array
65 int count;// number in the linked list
66 int head;// index of the head of the linked list
67 };
Double linked list
用数组实现链表，大多数情况下，是与传统链表类似的，无非是在添加、删除节点后，调整previous，next域的指向。但是有一点，当我在添加一个新的节点时，如何从数组中拿到一个还未被使用过的节点呢？这里有两种方法：
如果你看懂了上面的id allocator，你也许已经意识到，使用上面那个idallocator类就可以简单的实现这个需求 另外一种方法，其实原理上也类似，就是在这个double linked list类中维护两个链表，一个是已使用的，一个是未使用的
第一种因为借助于一个工具类，实现看起来会简洁很多，但是idallocator会消耗额外的内存，因此第二种方法相对来讲会比较好。
