プログラミング

Javaの主要標準ライブラリ [競技プログラミング/コーディングテスト]

就活のコーディングテストが近づいてきたのでJavaのよく使う標準ライブラリを思い出そうという記事。以下のような人には参考になる記事かもしれません。

  • むかしJavaを触っていて久しぶりに触るという人
  • Javaで競技プログラミングやコーディングテストをやってみようという人

Collectionインターフェイス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/Collection.html

みんな大好きCollectionsインターフェイス。ListやDequeやSetとかが含まれます。size(), isEmpty(), add(e), remove(o)などが共通して使えます。

Listインターフェイス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/List.html

可変長配列です。主に使用するクラスはArrayListとLinkedListの2種類です。

ArrayListクラス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayList.html

各要素が順序番号を持っている配列として実装されています。よってランダムアクセスがO(1)と早い代わりに、配列の末尾以外に要素を追加・削除するのがO(n)と遅いです。従ってadd(e), get(index)あたりをよく使いますが、add(index, e)はあまり使いません。

LinkedListクラス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/LinkedList.html

前後の要素同士がリンク情報で繋がっている線形リストとして実装されています。よってランダムアクセスがO(n)と遅い代わりに、配列の末尾以外にも要素を追加・削除するのがO(1)と早いです。従ってadd(index, e), addFirst(e)あたりをよく使いますが、get(index)はあまり使いません。

配列とListを変換するのは意外と面倒です。

配列をArrays.asList()でListにするとき、asListで返ってくるリストは長さ固定で、それを回避するためにそのリストをArrayListのコンストラクタに渡すという工程が必要になります。またasListの引数にプリミティブ型の配列を渡すと配列そのものがリストの要素のなってしまいます。

ListをtoArray()で配列にするとき、toArray()が返すのはObject型配列なので引数に欲しい型の配列を渡してやる必要があります。またその型は元のListの型と同じでなければなりません。型も変更したいときはStream()などを使うことになります。

(参考:【Java】Arrays.asList()で注意すべき点【Java】 ArrayListを配列に変換する

Dequeインターフェイス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/Deque.html

双方向キューです。スタックもキューもこれでOKです。主に使用するクラスは前述のLinkedListとArrayDequeです。

ArrayDequeクラス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html

配列と先端と終端を指す2つのポインタとして実装されています。offerFirst(e), offerLast(e)が挿入、peekFirst(), peekLast()が取得、removeFirst(), removeLast()が削除、pollFirst(), pollLast()が取得&削除です。

Setインターフェイス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/Set.html

重複要素のない集合です。主に使用するクラスはHashSetとTreeSetです。

HashSetクラス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/HashSet.html

ハッシュ表として実装されています。よって大きな容量が必要で、順序を保持しません。またadd(e)やcontains(e)など基本操作はO(1)と高速です。

TreeSetクラス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/TreeSet.html

二分木として実装されています。よって順序を保持します。また基本操作はO(log n)とHashSetには劣ります。

Java9からはSet.of(e1, e2…)というイミュータブル(変更不能)なSetを作成するメソッドが追加されている。便利。

https://docs.oracle.com/javase/9/docs/api/java/util/Set.html

PriorityQueueクラス

https://docs.oracle.com/javase/jp/8/docs/api/java/util/PriorityQueue.html

優先度つきキューです。優先度ヒープとして実装されています。初期化の際にラムダ式などを用いて順序を指定できます。引数なしだと最小ヒープで、Collections.reverseOrder()を指定すると最大ヒープになる。offer(e)で挿入、poll()で取得&削除。

Mapインターフェイス

https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/HashMap.html

キーとバリューを対応させるマップです。主に使用するクラスはHashMapです。

HashMapクラス

https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/HashMap.html

ハッシュテーブルとして実装されています。keyに使うクラスはequalsとhashCodeが実装されている必要があります。いろいろとメソッドが多いので整理しておきます。

put(key, value) 要素を追加します。対応は上書きされます。
putIfAbsent(key, value) 様相を追加します。対応が既に存在する場合は上書きしません。
get(key) keyに対応するvalueを取得します
getOrDefault(key, defaultValue) keyに対応するvalueを取得します。keyがないときはdefaultValueを返します
remove(key) keyの対応を削除します
entrySet() 対応全体のSetビューを取得します。以下のような使い方をします。

for(Map.Entry<V,V> item: map.entrySet()){
item.getKey();
item.getValue();
}

keySet() key全体のCollectionビューを取得します。
values() value全体のCollectionビューを取得します。

Stringクラス

https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/HashMap.html

文字列を表す。長さを取得するのがlength()なのが罠。よく使うメソッドはCharAr(index), equals(o), split(regix), substring(index), toCharArray(), valueOf(i)あたり。

文字列を結合するには+やStringBuilderを使用する。String配列やListを結合するならjoinが便利。

List<String> list = Arrays.asList(“a”, “b”, “c”);
String str = String.join(“”, list);

Arrays/Collections/Mathクラス

https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/Arrays.html

https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/Collections.html

https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/lang/Math.html

Arraysは配列、CollectionsはCollection、Mathは数学に関する便利なメソッドが集められています。ソートとか二分探索とか累乗とかmax, minとかいろいろ。

その他

これら以外にもStreamとかScannerとかもわりと使いますが、主要かと言われると微妙なのでここでは割愛。

参考