Есть ли в Java встроенный способ добавления элемента в алфавитный список?

Question

В библиотеке Java 5 уже есть метод для добавления элемента к алфавиту List?

Другими словами, скажем, у меня есть List<String> с тремя элементами {"apple","cat","tree"}, и яхотите добавить String "банан", сохраняя List в алфавитном порядке;Есть ли простой способ просто добавить его в List, чтобы List теперь имел четыре элемента {"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"

Обратите внимание, что время выполнения Big-O для add() и poll() равно O(logn).

Правка: PriorityQueue лучше всего, если вы хотите удалитьэлементы в порядке, но вам понадобится от TreeSet до итерации по коллекции по порядку.

Answer 2

есть SortedSet и SortedMap.Однако оба не могут поддерживать дубликаты.если это то, что вам нужно, используйте структуру данных Set.Ваш тип возврата должен быть List, тогда он использует Collections.list (set) для преобразования окончательного Set в Список.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

List - неупорядоченная коллекция.Хотя вы можете сортировать после добавления или правильно индексировать свои добавления, проще использовать коллекцию, созданную для поддержания порядка, например TreeSet.Это обеспечит упорядочение путем внесения изменений в набор, а также обеспечит сбалансированность набора для быстрого доступа.

Answer 4

Предполагая, что вы начинаете с пустого списка и добавляете в него элементы, сохраняя его в отсортированном порядке, вы

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);
}

пс.Collections.binarySearch () преобразуется в линейный поиск, если он не доступен для случайного поиска.

Answer 5

Попробуйте посмотреть на TreeSet. Если вы добавляете только строки, то String.compareTo () по умолчанию уже реализован.

В противном случае вы можете создать компаратор, чтобы сделать заказ для вас.

Answer 6

Самый простой способ сделать это, насколько я знаю, это добавить элемент, а затем использовать Collections.sort() в своем Списке. String s будет сортировать лексикографически. Collections.sort() работает с любым списком, содержащим элементы, которые реализуют интерфейс сравнения. Если вы хотите легко отсортировать список пользовательских объектов, убедитесь, что ваш T реализует Comparable.

РЕДАКТИРОВАТЬ: Конечно, как отмечали другие авторы, для этого есть более совершенные структуры данных. Однако, если вам абсолютно необходим List, это быстрый и грязный способ.

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 при этом всегда были отсортированы.