Does Java have a built-in way to add an element to an alphabetical List?

Is there a method already provided in the Java 5 library to add an element to an alphabetical List?

In other words, say I have a List<String> with three elements {"apple","cat","tree"} and I want to add the String "banana" while keeping the List in alphabetical order; is there an easy way to simply add it开发者_C百科 to the List, so that the List now has four elements {"apple","banana","cat","tree"}?

---

You can use a PriorityQueue. These are sorted according to the comparator of the objects they hold. Strings are, by default, sorted according to the ASCII values of the first differing character, which will give the results you want (as long as the capitalization of all the words is all the same.)

Quick example:

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"

Note that the Big-O runtime of both add() and poll() is O(logn).

Edit: PriorityQueue is best if you want to remove the items in order, but you will need a TreeSet to iterate over the collection in order.

---

there is SortedSet and SortedMap. However both cant support duplicates. if this is what you need then use the Set data structure. You your return type need to be List then he use Collections.list(set) to conver the final Set to the List. javadoc here http://download.oracle.com/docs/cd/E17476_01/javase/1.4.2/docs/api/java/util/Collections.html#list(java.util.Enumeration)

---

Try looking at TreeSet. If you're adding strings only, then the default String.compareTo() is already implemented.

Otherwise, you can build a comparator to do the ordering for you.

---

List is an unordered collection. While you can sort after adding or properly index your adds, it's easier to use a collection that's built to maintain an order, like a TreeSet. That will ensure ordering through changes to the set and will also ensure the set is balanced for fast access.

---

Assuming you are starting with an empty list and you add elements to it while keeping it in sorted order you would

1. find the insertion point by either linear search (if you use a linked list) or binary search if you use an array list
2. at the insertion point, say i, you would use list.add(i, element)

e.g.

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() will degrade to a linear search when it is not randomly searchable.

---

The simplest way to do so that I know is to add the element, then use Collections.sort() on your List. Strings will sort lexicographically. Collections.sort() works on any List containing elements that implement the Compare interface. If you want to sort a list of custom objects easily, make sure your T implements Comparable.

EDIT: Of course, as other posters have pointed out, there are better data structures for this. However, if you absolutely need a List this is the fast-n-dirty way.

---

If you want to do it yourself, you could binary search to find the location where each item would be added in alphabetical order and then add it to that position, which will keep the list in sorted order. Edit: You might want to do this if you want all of the functionality of a List while still having it always sorted.

---

The addToSorted function I wrote is not provided by default by Java, but is still very simple. The Collections.binarySearch function returns either a value >= 0 if the element is found or a value < 0 if the value is not found. In the latter case, it returns the insertion position (somewhat encoded so that it is always negative).

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