どんな非負整数Mに対して
と自分で書いている
当然与える情報はMである

各Mに対応するポインタを保持するなら
挿入時にそのテーブルを更新しなきゃならないから
O(1)では出来ない