Est-il connu de la mise en œuvre d'un indexés liste chaînée?

Mon instinct me dit qu'il ya pas de bonne façon de le réaliser, mais, à la différence de M. Stephen Colbert, je préfère faire confiance à une communauté de développeurs que mon intestin...

Est-il un moyen connu pour mettre en œuvre efficacement un "meilleur des deux mondes" de la liste, celui qui fournit l'accès aléatoire par l'indice de et O(1) insertion/retrait comme une liste chaînée?

Je pense que les deux résultats possibles: soit "Non, c'est impossible, pour des raisons évidentes..." ou "Euh, oui, cela a été fait; voir ici, ici et ici."

InformationsquelleAutor Dan Tao | 2009-11-11