Java データ構造

Java のデータ構造で使いそうなものを自分なりにまとめたメモ。
標準ライブラリの他に、Guava 等もまとめの対象です。

java.util.List

• 順序を持つ
• 重複要素を許可

ArrayList

• 内部的には配列
• 挿入、削除はその要素以降の要素の再配置が行われるため遅い
• 追加やget(index)は速い

LinkedList

• 数珠つなぎ構造
• get(index)は遅い
• 挿入、削除が速い

org.apache.commons.collections4.list.TreeList

• 挿入、削除が速い
• 追加やget(index)も速いが、ArrayList には劣る
• 挿入・削除が多い場合は LinkedList より TreeList を選択したほうが大抵良いらしい。
• AVL tree で実装されている

java.util.Set

• 重複要素を持たない
• 順序を保証しない

HashSet

• 順序を保持しない

TreeSet

• ソートされた順序を保持する。自然順序か指定された Comparator の昇順。
• Red-Black tree で実装されている

LinkedHashSet

• 順序は挿入順

java.util.Map

• key と value が対になった要素を持つ。
• key の重複は許可されない。
• 順序を保証しない

HashMap

• 順序を保持しない

TreeMap

• key がソートされた順序を保持する。自然順序か指定された Comparator の昇順。
• Red-Black tree で実装されている

LinkedHashMap

• key の順序は挿入順。アクセス順にすることもできる。

com.google.common.collect.BiMap

• value もユニークである Map
• BiMap#inverse で key と value を入れ替えることができる
• HashBiMap、EnumHashBiMap、EnumBiMap がある

com.google.common.collect.Multiset (Bag)

• 重複を許可した Set のようなもの
• 重複要素の数をカウントするのに便利
• Bag と呼ばれるものと同じ。org.apache.commons.collections4.Bag など。
• Set のように扱えるが Set は継承していない
• HashMultiset、TreeMultiset、LinkedHashMultiset、EnumMultiset がある

com.google.common.collect.Multimap

• key 重複を許可した Map のようなもの
• Map に似ているが key - value が1対多
• Map<key, Collection<value>> の扱いやすい版
• Map は継承していない
• ListMultimap系、SetMultimap系 などがある

com.google.common.collect.Table

• Table<row, column, value> というテーブル構造
• key が2次元になった Map のようなもの
• Map<key1, Map<key2, value>> の扱いやすい版
• ArrayTable、HashBasedTable、TreeBasedTable がある

stack

• 先入れ後出し(First-In Last-Out, FILO)のデータ構造
• java.util.Stack や、java.util. Deque の様々な実装を stack として使用できる

queue

• 先入れ先出し (First-In First-Out, FIFO)のデータ構造
• PriorityQueue, BlockingQueue など、java.util.Queue の様々な派生がある