Collections.rotate(list, -1);が妙に遅い

LinkedListに、10000件の文字列の要素を追加して、
10000回のローテーションを実行してみたら、

Collections.rotate(list, -1);

おもったより時間かかる。単位は、ミリ秒。

ローテーション java.util.LinkedList:7274

ローテーションする時間を調べてみたら、
java.util.LinkedListがjava.util.ArrayListよりおそい。

ローテーション java.util.LinkedList:7394

ローテーション java.util.ArrayList:2060

アルゴリズムとデータ構造の教科書的な知識では、
こういう操作は、ArrayListよりLinkedListのほうが速いはず。

ためしに、LinkedListのローテーションについて、

Collections.rotate(list, -1);

をやめて、

list.addLast(list.removeFirst());

としてみた。すると劇的に実行時間が改善。

ローテーション java.util.LinkedList:1

ローテーション java.util.ArrayList:2076

来週、ソースコードをなおさねば。
本番では、1万件どころか10万件でローテーションする想定なのさ。