Without much research here, wouldn't an AVL tree do what you would like to do? It is optimized (I believe; I hope I'm remembering the correct algorithm) for this type of thing; most often used items are moved to the top, and it is self-balancing too (I believe).