C/C++数组作链表

一般传统链表的物理结构，是由指针把一个一个的节点相互连接而成：

1

struct 

node 

2 { 
3 DataType data; 
4 node* 

previous; 

5 node* 

next; 

6 }

其特点是按需分配节点，灵活动态增长。

但是此外，还有另外一种方式是使用数组实现链表，这里所有的  node  都在预
先分配好的数组中，不使用指针，而是用数组下标来指向前一个、下一个元素：

1

struct 

node 

2 { 
3 DataType 

data; 

4

int

 previous; 

5

int

 next; 

6 }

其特点是预先分配节点，并且如果需要链表长度随需增加，需要  reallocation 
,和  vector  类似。

下面就我自己的一些了解，谈一下其优缺点与应用。

数组作链表有哪些优点

能要省些内存吗？不见得；速度要快吗？没看出来，那么为什么要使用这种

 

不那么直观的方式来实现链表呢？

•

 

数组的内存布局比较紧凑，能占些局部性原理的光