ソート済みのリストに、新しい要素をソート順での適切な位置に挿入したい。
そのとき、適切な挿入位置をどう求めるかというと、二分探索アルゴリズムを使えば良いのではないか、ということは思いつく。
しかし、わざわざ自分でアルゴリズムを書くのは面倒である。。
実は、JavaではCollectionsクラスにbinarySearchというメソッドがあるのでそれを使える。
例えば、リストに要素を挿入するためのメソッドを以下のように書いてみた。
※リストはあらかじめソート済みであること
public static <T extends Comparable<? super T>>void insert(LinkedList<T> list, T element){
int idx = Collections.binarySearch(list, element);
if( idx < 0 ){
// 0より下の場合はリスト内に要素が無い。
// (-(挿入ポイント)-1) という値なので本来の挿入ポイントを求める
idx = -idx -1;
}
if( list.size() <= idx ){
// リストのサイズ以上の位置ならばリストの最後尾に追加
list.addLast(element);
}
else{
list.add(idx,element);
}
}
binarySearchメソッドは、コレクションの中に要素がすでにあるならばその位置を、無い場合は(-(挿入ポイント) - 1)という値を返す。
そのため、5行目からの処理で正しい挿入位置を計算し直している。
そして、このメソッドは以下のように使う。
public class Main {
public static <T extends Comparable<? super T>>void insert(LinkedList<T> list, T element){
// 実装は上記。省略
}
public static <Ｔ> void printList(List<Ｔ> list){
for(Ｔ elem : list){
System.out.println(elem);
}
}
/**
* @param args
*/
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<String>();
list.add("bar");
list.add("foo");
list.add("hoge");
list.add("piyo");
printList(list);
System.out.println("--");
insert(list,"abc");
insert(list,"foo");
insert(list,"zxcv");
insert(list,"jjj");
printList(list);
}
}
実行すると以下のように表示される。
bar
foo
hoge
piyo
--
abc
bar
foo
foo
hoge
jjj
piyo
zxcv
二分探索のようなメジャーなアルゴリズムは、最近の高級言語ならばすでに標準で実装されている場合が多い。
自作する前に、まずはAPIドキュメントを探してみると良いだろう。