連結リストの挿入は O(1) ってのに異論はないんだけど、挿入場所が分かっていなければ O(1) じゃなくて O(n) になるってのは忘れられがち・・・というか、下手したら認識されてさえいない。 例えば List#add(int index, E element) の効率だけど、これは index の場所を見つけるまで先頭、もしくは末尾からシーケンシャルな走査が必要なため、O(1) じゃなくて O(n) となる。 Sun の実装は、 public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } public Entry<E> entry(int index) { if (index < 0 || index >= size) throw new Ind