2009网易笔试一道题目

今天刚去网易笔试了，有一道题目不是很懂，上网查了下，但是没找到啥答案，特发贴到此，真诚的希望各位高手给指点一二，小弟我不胜感激。注明我是学java的。 
设计一种改进型的链表结构来优化随机定位操作的性能？给出设计思路及改进后随机定位操作的时间复杂度？

解决方案 »

  1.   

    链表有双向和单向链表之分，-->->->->->->->类似这样的结构。随机选择的意思是指通过下表查找数据，类似数组的a[2]这样去访问数组元素。这样的访问叫做随机访问。
      

  2.   

    在list里添加个Map可以吗？用Map来实际存贮键值对，需要查找的时候只要在Map里查找键值对就行了，复杂度应该是O(Nlog2N)
      

  3.   

    应该像LinkdeHashMap 一样的数据结构！！！
    既有链式 也的hashcode随机存储  的存储结构...读写都不慢！
      

  4.   

    http://blog.csdn.net/romandion/archive/2008/05/09/2421370.aspx这是C语言的实现方式，我看了一下
    笔者是用B树的方式来组织索引
    定位到某一个节点时，先通过索引找到那一段链表的头节点，再去遍历那一段链表只是这篇文章没有提到当链表更新时，如何更新索引看看大家有没有更好的方案
      

  5.   

    我觉得应该不会让用Map，那样还要list干嘛……我还是觉得用索引好一点
    嗯，其实重点是要建个索引，至于用什么方式建索引，那要看实际情况
    PS:由于B tree的叶子结点存储的是链表的各段子链表的头结点，所以如果更新链表的时候没有改动这些头结点就不必更新索引，麻烦的是那些改动了头结点引用的更新