ArrayListとLinkedListの違い その3
こないだ書いたのが消えてしまったのでもう一度書き直します。
コンカレントなんとかエクセプション
Iteratorで回すループの中でListの要素を削除した追加したりすると、コンカレントなんとかエクセプションが飛んでくるので、「Iteratorでループするときは削除しちゃらめぇ」と思いこんでました。
なので、条件を指定してリストから要素を削除するような場合、以下のようなコードを書いてたのです。
// 3で割り切れる数を排除する public void rejectMultipleOf3(List<Integer> list) { // 3で割り切れる要素のインデックスを入れるリスト List<Integer> multipleOf3IndexList = new ArrayList<Integer>(); // 3で割り切れる要素のインデックスを集める for(int i=0; i<list.size(); i++){ int num = list.get(i); if(num % 3 == 0){ multipleOf3IndexList.add(i); } } // 3で割り切れる要素を消していく // 頭からやると途中で順番が狂ってしまうのでお尻からやる for(int i=multipleOf3IndexList.size()-1; i>=0; i--) { int multipleOf3Index = multipleOf3IndexList.get(i); list.remove(multipleOf3Index); } }
長いですね。イヤですね。メンテしたくないですね。
Iteratorは削除ができる
コレクションのソースを見ていて気がついたのですが、Iteratorインターフェースに「remove()」というメソッドがありました。
これを使うと、Iteratorが現在指している要素を、元のリストから削除できるようです。
つまり、上のソースは
// 3で割り切れる数を排除する public static void rejectMultipleOf3(List<Integer> list) { for(Iterator<Integer> iter = list.iterator(); iter.hasNext(); ) { int i = iter.next(); if(i % 3 == 0){ iter.remove(); } } }
こんなに簡単に書くことができたんですね。初めて知りました。今までこれを知らなかったことが残念です。
LinkedListが返すIteratorはもっと便利
LinkedList#iterator()が返すイテレーターはListIteratorというインターフェースを実装しています。これはふつうのIteratorインターフェースよりも便利な代物で、hasPrevious() と previous() という巻き戻しのメソッドや。現在の位置に要素を追加するadd()メソッド、現在の位置の要素を置き換えるset()メソッドが使えます。
使い方はこんな感じ
// 3で割り切れる数の直後に「-1」を追加する public static void addAfterMultipleOf3(List<Integer> list) { for(Iterator<Integer> iter = list.iterator(); iter.hasNext(); ) { ListIterator<Integer> listIter = (ListIterator<Integer>)iter; int i = listIter.next(); if(i % 3 == 0){ listIter.add(-1); } } }
// 3で割り切れる数を「0」に置き換える public static void replaceMultipleOf3(List<Integer> list) { for(Iterator<Integer> iter = list.iterator(); iter.hasNext(); ) { ListIterator<Integer> listIter = (ListIterator<Integer>)iter; int i = listIter.next(); if(i % 3 == 0){ listIter.set(0); } } }
長い…
ここからやっと本題
さっきの「3で割り切れる数を排除する」メソッドに、ArrayListとLinkedListを渡して実行して比較してみたわけです。
LinkedListに100万個の数字を入れて回したところ、0.1秒で終わりましたが、ArrayListで試してみたらパソコンがものすごい唸り声をあげて江東区が壊滅しそうになったので途中でやめました。
ArrayListの名誉のために、参照だけの処理も作って比較してみました。
// 0番目、3番目、6番目、、、のように3の倍数の位置にある要素を集めて返す public static List<Integer> selectMultipleOf3(List<Integer> list) { List<Integer> result = new LinkedList<Integer>(); for(int i=0; i<list.size(); i++ ) { if(i % 3 == 0){ result.add(list.get(i)); } } return result; }
こっちはさっきと逆の結果。ArrayListが0.1秒で終わり、LinkedListは帰らぬ人となってしまいました。