Java에 알파벳순 목록에 요소를 추가하는 기본 방법이 있습니까?

Question

자바 5 라이브러리에 이미 제공된 메소드가 알파벳 List에 요소를 추가합니까? 즉

, 나는이 List<String> 3 개 요소가 있다고 {"apple","cat","tree"}와 나는 String "바나나"를 추가 할 동안 알파벳 순서로 List을 유지; List에 간단하게 추가 할 수있는 쉬운 방법이 있습니까? List에는 이제 4 개의 요소 {"apple","banana","cat","tree"}이 있습니까?

Answer 1

PriorityQueue을 사용할 수 있습니다. 이들은 보유하고있는 객체의 비교 자에 따라 정렬됩니다. Strings는 기본적으로 (한 모든 단어의 대문자로 모두 동일합니다.) 당신이 원하는 결과를 얻을 첫 번째 다른 문자의 ASCII 값에 따라 분류되어

빠른 예 :

PriorityQueue<String> pq = new PriorityQueue<String>(); 
pq.add("banana"); 
pq.add("apple"); 
pq.add("orange"); 
pq.poll(); // Returns "apple" 
pq.poll(); // Returns "banana" 
pq.poll(); // Returns "orange" 

add()과 poll()의 Big-O 런타임은 모두 O(logn)입니다.

편집 : 당신이 순서대로 항목을 제거하려면 PriorityQueue 가장이지만, 당신이 TreeSet의 콜렉션으로 반복을 위해 필요합니다.

Answer 2

SortedSet 및 SortedMap이 있습니다. 그러나 두 가지 모두 지원할 수 없습니다. 이것이 필요한 경우 Set 데이터 구조를 사용하십시오. 반환 유형이 List이어야하고 Collections.list (set)를 사용하여 최종 세트를 List로 변환하십시오. javadoc 여기에 http://download.oracle.com/docs/cd/E17476_01/javase/1.4.2/docs/api/java/util/Collections.html#list(java.util.Enumeration)

Answer 3

제가 알고있는 가장 간단한 방법은 요소를 추가 한 다음 목록에 Collections.sort()을 사용하는 것입니다. String은 사전 편집 방식으로 정렬됩니다. Collections.sort()은 Compare 인터페이스를 구현하는 요소가 포함 된 목록에서 작동합니다. 사용자 정의 객체 목록을 쉽게 정렬하려면 T가 Comparable을 구현해야합니다.

편집 : 물론 다른 포스터가 지적한 것처럼 더 나은 데이터 구조가 있습니다. 그러나, 당신이 절대적으로 List을 필요로한다면 이것은 빠른 n 더러운 방법입니다.

Answer 4

직접 처리하려면 이진 검색을 사용하여 각 항목이 사전 순으로 추가 된 위치를 찾은 다음 해당 위치에 추가하면 정렬 된 순서로 목록이 유지됩니다. 편집 : List의 모든 기능을 원하면 항상 정렬 할 수 있기를 원할 수 있습니다.

Answer 5

TreeSet을 살펴보십시오. 문자열 만 추가하는 경우 기본 String.compareTo()가 이미 구현되어 있습니다.

그렇지 않으면 주문을 수행 할 비교기를 만들 수 있습니다. 당신을 가정

Answer 6

빈 목록으로 시작되고 순서 (링크 된 목록을 사용하는 경우) 당신이

1. 중 하나 선형 검색하여 삽입 점을 찾아 낼 것 또는 바이너리에서 그것을 유지하면서 그것에 요소를 추가 배열 목록을 사용하는 경우 검색하십시오. 삽입 지점에
2. , i라고 말하면 list를 사용합니다.add (i, element)

String element = "banana"; 
List<String> list = new ArrayList<String>(); 
int i = Collections.binarySearch(list, element); 
if (i < 0) { 
    list.add(-(i+1), element); 
} else { 
    list.add(i, element); 
} 

ps. Collections.binarySearch()는 임의로 검색 할 수없는 경우 선형 검색으로 저하됩니다.

Answer 7

필자가 작성한 addToSorted 함수는 기본적으로 Java에 의해 제공되지 않지만 매우 간단합니다. Collections.binarySearch 함수는 요소가 발견되면 값 >= 0을 반환하고 값을 찾을 수없는 경우 값을 < 0으로 반환합니다. 후자의 경우 삽입 위치를 반환합니다 (다소 음수가되도록 인코딩 됨).

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 

public class BinSort { 

    private static void addToSorted(List<String> list, String element) { 
    int index = Collections.binarySearch(list, element); 
    if (index < 0) 
     list.add(-(index + 1), element); 
    } 

    public static void main(String[] args) { 
    List<String> words = new ArrayList<String>(); 
    words.add("apple"); 
    words.add("cat"); 
    words.add("tree"); 
    addToSorted(words, "banana"); 
    System.out.println(words); 
    } 
} 

Answer 8

List은 정렬되지 않은 모음입니다. 추가를 추가하거나 적절한 색인을 작성한 후에 정렬 할 수 있지만 주문 유지를 위해 작성된 모음 (예 : TreeSet)을 사용하는 것이 더 쉽습니다. 그러면 세트 변경을 통한 주문이 보장되며 세트가 빠른 액세스를 위해 균형을 이루게됩니다.