设计一种数据结构，结合了链表和数组的优点解决方案
设计一种数据结构，结合了链表和数组的优点讨论一下吧我的理解是这个数据结构必须有链表和数组的优点链表优
设计一种数据结构，结合了链表和数组的优点
讨论一下吧
我的理解是
这个数据结构必须有链表和数组的优点
链表优点：易于删除和插入元素
数组优点：直接定位， 可以折半查找（？？怀疑这点能不能实现）
有人说哈希链表？具体怎样，大家讨论吧?
[解决办法]
红黑树或跳跃链表应该差不多，也可以用数组模拟的双向链表来处理，不过最坏情况下，复杂度可能比较高，但平均复杂度应该还可以！
[解决办法]
直接定位与易于修改是冲突的,还要折半查找,相对折中的算法有B类树
[解决办法]
可以考虑一下堆的实现 。
其本质可以是数组。
但是利用下标0 是 1 与 2 的父亲指针
1是 3 和 4 的父亲指针
来实现类似于链表的结构。
我觉得这个非常强，曾经感慨了好久。
[解决办法]
哈希链表，嗯
或许这才是问题的实质，上面只是现象。
如果有一个函数。可以把 0-n都覆盖，且 1、1映射的话，该就是非常完美的数组链表了。
[解决办法]AVL TREE
[解决办法]AVL tree
易于删除和插入元素，并且直接定位， 可以折半查找
[解决办法]双层指针数组即可。
具体如下：
1）每个块内容是一个短的指针数组，按照升序排列好。另外就是这个块的摘要，就是第一个元素和最后一个元素的值。
2）上述这种块的指针形成的指针数组。也按照升序排列各个块的指针数组。
查询的时候，先用2分法，定位到块，然后块内部用2分法查询到相应内容。
插入的时候，先用2分法确定插入到哪个块，再用2分法插入值，如果块过大，则分裂成依次相邻的2个块。
删除的时候，先用2分法确定块，然后在块中删除，如果块的大小过小，则合并到相邻块去，或者把相邻块的一些元素移动过来，保持块的数量的均衡。
当然，这个算法比较复杂，但确实易于删除和插入，虽然比移动链表花费的时间长，但移动的总次数 最多<= 总块数 + 单独一个块中最多的元素数量。
比如 1000 * 1000的结构，这个算法是能适应的。
如果进一步海量，可以按照上述思想，把双层变成3层、4层。4层可以容纳1000 ^ 4个元素。
另外，这个结构的好处是方便组织内存与硬盘的交换，有些块可以把内容放到硬盘中，只把摘要放在内存中，确实需要再把该块内容从硬盘中进行加载。
[解决办法]哈希链表应该比较合适
[解决办法]觉得还是哈希链表比较好
另外，在指示头节点的指针数组中，再添加一个域，表示下一个哈希值，可以跳过那些空链。
[解决办法][解决办法]我开发的数据结构应该可以满足你的要求：
http://topic.csdn.net/u/20090818/15/73cfd34b-cdfd-4e5f-9cf2-e069137cce43.html?61140
