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 람다 함수를 사용하는 한 줄짜리 구현을 사용할 수 있습니다. 인터페이스는 기능적 인터페이스이며 호출할 단일 메서드가 있습니다. 람다는 인터페이스에 있는 매개변수 수를 직접 사용합니다. 위 코드의 한 줄짜리 Java 8 표현은 아래와 같습니다.

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

목록의 요소를 비교하는 실제 명령문은 collator 클래스입니다. 이 클래스는 본질적으로 추상적이며 메서드의 프로토타입을 정의합니다. 구현은 이를 확장하는 추상 클래스에 있습니다.

collator 클래스는 로케일 구분 문자열을 비교합니다. getInstance 메소드는 현재 기본 Locale 값으로 인스턴스를 가져옵니다. compare 기능은 Collator를 기반으로 값을 비교하고 더 크거나 작거나 같은 값을 기반으로 +1, -1 또는 0을 반환합니다.

위 코드의 출력은 아래와 같습니다. 두 번째 줄은 출력을 정렬된 형태로 나타냅니다. 키보드의 ASCII 문자 시퀀스에 따라 대문자는 작은 알파벳(a-z)보다 높은 범위(A-Z)에 속합니다. 따라서 두 번째 줄의 결과 목록은 대문자 bb를 먼저 인쇄한 다음 대문자 알파벳이 있으므로 bB를 인쇄합니다.

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