ArrayListクラスについて

質問

java.util.ArrayListクラスは、
双方向に検索ができると本に書いてあったのですが、
どういう意味ですか？
具体例をまじえて教えて下さい。

回答No.3

hiraku-jp · ベストアンサー

ArrayListの実装がリストならいいんですが、実際は配列だからなぁ・・
その本の記述はあまり良くないかも。。

こういった順序付けされたコレクションの実装は、リストと配列（ベクトル）に分かれます。

配列実装のコレクションは内部に連続したメモリを確保します。連続しているので、インデックスを指定した参照（いきなり5番目の要素の取得等）が可能で、全般的に参照は高速ですが、要素を挿入・削除する場合（特に途中に、もしくは容量の変更が必要な）は遅くなります。

これに対してリスト実装のコレクションは要素と次の要素への参照からなります。これは頭からの順次アクセスは参照を辿って行うので遅くはありませんが、いきなり5番目、と言われても対応できません。（内部的に先頭から5番目まで辿るしかない）しかし、値を挿入する場合には、途中であっても参照を挿げ替えるだけなので高速です。また、連続した空間で無い為、容量の拡張も必要ありません。

で、普通は双方向リストと言うと、このリスト実装で、要素と前後双方への参照で構成され、双方向への順次アクセスが可能なものを言います。片方しか持っていなければ、片方へしか順次アクセスできないですよね？

で、本当は説明終わりたい所なんですが・・
ArrayListは先にも言ったとおり本当は配列実装です。（javaだとLinkedListなんかがリスト）
なんで、双方向の検索なんて本当は出来て当たり前なんですよね。連続してるんですから。

実際には（効率は無視すれば）リスト実装のようなインターフェースを持つ配列や、配列実装のようなインターフェースを持つリストが作れるわけで、ArrayListは前者なんですね。まぁこんな所でしょうか・・

より詳しく知りたい場合は、アルゴリズムとかデータ構造とかを調べてみて下さい。

お礼

回答ありがとうございます。
詳細に説明してくださって大変よく分かりました。
また、助けてください。

回答No.2

elder2

ArrayListの実装は配列(可変長)です。
例えば10個の配列だった場合、
0番目から順に1, 2, ・・・9番目へと検索は可能ですよね？
そして、それとは逆に、9番目から前に8, 7, ・・・0番目までの検索も可能ですよね？

このことが、双方向に検索が可能という意味です。

リンクリストの場合は前から順に後ろへたどることしかできませんので、
これは単方向のみにしか検索はできません。
ちなみに、java.util.LinkedListクラスは双方向リストですので、
ArrayListと同様に双方向に検索が可能です。

#見当違いでした？

お礼

回答ありがとうございました。
さらに理解が高まりました。

回答No.1

noname#25358

要素のゼロ番から順番に検索する .indexOf() メソッドと、最後から検索する .lastIndexOf() メソッドの両方がサポートされているのです。

　(0) abc
　(1) def
　(2) ghi
　(3) def
　(4) mno

　この例では、.indexOf("def") では 1 が、.lastIndexof("def") では 3 が返ります。

お礼

すぐにお返事いただいてありがとうございます。
少しイメージが沸きました。