連結リストは挿入する前後で矢印を入れ替えるだけなのに対して，Array の場合はその先にある奴を丸ごと移動しないといけないから遅いんじゃないかと思います．

移動のためのコピーが速いか、連結リストで先頭からたどるのが速いかで言えば、たどる方が速い可能性はありますが、係数の差でオーダーとしてはどちらも O(N) ですね。 (edited)