Linked-List 的数组实现

疑问出自 <Introduction to Algorithms, 2nd Edition>
        10.3 Implementing pointers and objects




如上图是linkedlist  9 -> 16 -> 4 -> 1 的数组形式实现
疑问：
为何需要长度为8的数组， key 确只有4个。
每个对象 （垂直的3元数组） 是怎么确定其在数组L中的位子，
阴影部分是干嘛的？

谢谢

评论

2 楼 freizl 2012-11-25  

Heart.X.Raid 写道

这是一种静态链表结构，链表中的每个结点都存放在一片连续的内存空间里(数组中)。

C的数组是不能动态生成的，必须在编译阶段就指定连续空间的大小。因此往往一开始就开辟一个足够大的空间来存放，如果空间不够再重新开辟。

数组长度8，只有4个key说明还可以加入新的链表结点，阴影部分用来存放以后再加入的新结点。这不是什么问题，你的数据结构还要好好的学学。

厉害厉害。多谢指点。

1 楼 Heart.X.Raid 2010-05-10  

这是一种静态链表结构，链表中的每个结点都存放在一片连续的内存空间里(数组中)。

C的数组是不能动态生成的，必须在编译阶段就指定连续空间的大小。因此往往一开始就开辟一个足够大的空间来存放，如果空间不够再重新开辟。

数组长度8，只有4个key说明还可以加入新的链表结点，阴影部分用来存放以后再加入的新结点。这不是什么问题，你的数据结构还要好好的学学。