Hatena::ブログ(Diary)

syttruの日記 このページをアンテナに追加 RSSフィード

2008-04-06

LinkedListとArrayListの違い

ジャンプ買いに行く前にお絵かきしたくなった。

間違ってたらごめんなさい><

f:id:syttru:20080407011246j:image

ArrayListは、単純にリストの各要素に対して番号を振るような感じ。

LinkedListは、リストの各要素に対して「前の要素」と「次の要素」という情報を付加する。


ArrayListは、リストの真ん中あたりにある要素の番号を指定して要素を引っ張り出してくるのが早い。

LinkedListは、頭から数えていかないととってこれない。


ArrayListは、リストの真ん中あたりにある要素を削除したり追加したりするときに、他の要素の番号を振りなおさないといけないので大変。

LinkedListは、リンク(図にある赤い糸)を切り貼りするだけで済む。


大量のデータをリストに入れる場合、真ん中あたりへの追加や削除が多そうだったらLinkedList。真ん中あたりを参照するのが多そうだったらArrayList。っていう感じで判断すれば良いと思う。


よしジャンプ買ってこよう

みずしまみずしま 2008/04/07 13:04 > 真ん中あたりへの追加や削除が多そうだったらLinkedList

そこはちょっと注意が必要だと思います。というのは、LinkedListでは「リンクを切り貼りするだけで済む」とは言っても、切り貼りするリンクにたどりつくのに、平均的にはリストの要素数に比例したコストがかかるため、単にjava.util.List<E>#remove(Object)やjava.util.List<E>#add(int,E)を使う場合は、早くなるとは限りません。リストの先頭付近でのみ挿入/削除が行われる場合以外でLinkedListのメリットが出てくるのは、LinkedListからIteratorを取得して、それに対して「リストから条件を満たす全要素を削除」などの、要素をたどりつつ挿入/削除の操作を行う場合です。

syttrusyttru 2008/04/08 03:17 あうあう…
いつもありがとうございます。
自分でも色々と調べてみたのですが、操作ミスで全部消えてしまいました。泣きたいです。
http://d.hatena.ne.jp/syttru/20080407/1207592114

akiravizakiraviz 2008/11/27 18:03 Mr.みずしまさん、素晴らしいです。
1.4向けのパフォ本に確かにこれらの比較が載っていて、大体の場合、ArrayListの方を使えばおkみたいな事が書いてありましたが、結論を拾い読みしただけなので、理由は知りませんでした。その理由は正しい感じがします。Thanks

kamyukamyu 2011/12/30 12:02 Javaの本を数冊所有していますが、これほどわかりやすい説明はありませんでした。感謝。
本を書いているエライ人は、どうして説明が下手なのか、うんざりです。他のことも、何冊目かでようやくわかった、ということが頻繁です。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

リンク元
Connection: close