GapList -

[actual]

Tomas Mauch developed a List implementation called GapList which looks to have LinkedList-like performance for get/add first/last elements and  ArrayList like performance for random access. I haven't tried it out myself but it looks interesting.

If you need a bit of a boost but still want to deal with a List like interface, this might be worth a look. Code and javadocs are here.