Java でリンクリストを並べ替える

Java のリンクリストは、ユーザーがメモリ内に動的配列を作成できるようにするデータ構造またはコレクションです。リストには、事前定義されたサイズは含まれていません。ノードを動的に作成し、値と次のノードへの参照を単一のメモリアドレスに格納します。リスト要素は値を順番に保持するか、リストは要素が挿入される挿入順序を維持します。

並べ替えは、データ構造内の要素を明確な順序で配置する方法として定義されます。配置は、要件に応じて、昇順または降順のいずれかになります。リストコレクションを並べ替えるには、さまざまな方法があることに注意してください。

以下は、配列内の要素を並べ替えるためのコードブロックです。

import java.text.Collator;
import java.util.Comparator;
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("ab");
    list.add("bb");
    list.add("aA");
    list.add("bB");
    System.out.println(list);
    list.sort(new Comparator<String>() {
      @Override
      public int compare(String s1, String s2) {
        return Collator.getInstance().compare(s1, s2);
      }
    });
    System.out.println(list);
  }
}

上記のコードブロックでは、リストは new キーワードを使用してインスタンス化されます。キーワードは、String データ型のリンクリストをインスタンス化し、コンストラクターを内部的に呼び出します。次に、リストインスタンスは add メソッドを呼び出してリスト内の要素を入力します。挿入順序を確認するために値が出力されます。

sort メソッドは List インターフェースにあります。この関数は、パラメーターとして指定されたコンパレーターに基づいてリストをソートします。コンパレータは、渡された要素のリストを比較するために使用されます。

考慮すべき点は、渡された値をソートし、それらが同じタイプでなければならないことを確認することです。値が同じタイプでない場合、または要素が比較できない場合、クラスは ClassCastException をスローします。

ソートの内部実装は、十分に効率的で、log n 時間で比較を行う merge sort コマンドを使用して行われます。そのため、compare メソッドをオーバーライドする new Comparator インスタンスが形成されます。実装は、メソッドをオーバーライドして実装を提供する従来の方法です。

代わりに、Java 8 ラムダ関数を使用したワンライナー実装を使用できます。このインターフェースは機能インターフェースであり、呼び出すメソッドは 1つだけです。ラムダは、インターフェースに存在するパラメーターの数を直接受け取ります。上記のコードのワンライナーJava 8 表現を以下に示します。

list.sort((o1, o2) -> Collator.getInstance().compare(o1, o2));

リスト内の要素を比較するための実際のステートメントは、collator クラスです。このクラスは本質的に抽象的であり、メソッドのプロトタイプを定義します。実装は、それらを拡張する抽象クラスに存在します。

collator クラスは、ロケールに依存する文字列を比較します。getInstance メソッドは、現在のデフォルトのロケール値でインスタンスを取得します。compare 関数は、collator に基づいて値を比較し、より大きい、小さい、または等しい値に基づいて、+1、-1、または 0 を返します。

上記のコードの出力を以下に示します。2 行目は、出力を配置された形式で表しています。キーボードの文字の ASCII シーケンスに従って、大文字は小さいアルファベット（a-z）よりも高い範囲（A-Z）にあります。したがって、2 行目の結果のリストは、大文字のアルファベットが含まれているため、最初に小さな大文字と小文字の bb を出力し、次に bB を出力します。

[ab, bb, aA, bB][aA, ab, bb, bB]