Di Jawa ada SortedSetdan SortedMapantarmuka. Keduanya termasuk dalam kerangka Java Collections dan menyediakan cara yang diurutkan untuk mengakses elemen.

Namun, dalam pemahaman saya tidak ada SortedListdi Jawa. Anda dapat menggunakannya java.util.Collections.sort()untuk mengurutkan daftar.

Adakah yang tahu mengapa itu dirancang seperti itu?

Daftar iterators menjamin pertama dan terutama bahwa Anda mendapatkan elemen daftar dalam urutan internal daftar (alias urutan penyisipan ). Lebih khusus itu dalam urutan Anda memasukkan elemen atau tentang bagaimana Anda memanipulasi daftar. Penyortiran dapat dilihat sebagai manipulasi struktur data, dan ada beberapa cara untuk menyortir daftar.

Saya akan memesan cara-cara dalam urutan kegunaan seperti yang saya pribadi melihatnya:

1. Pertimbangkan untuk menggunakan Setatau Bagkoleksi sebagai gantinya

CATATAN: Saya menempatkan opsi ini di bagian atas karena ini adalah apa yang biasanya ingin Anda lakukan.

Kumpulan yang diurutkan secara otomatis mengurutkan koleksi pada saat penyisipan , yang berarti ia melakukan penyortiran saat Anda menambahkan elemen ke dalam koleksi. Ini juga berarti Anda tidak perlu mengurutkannya secara manual.

Selain itu, jika Anda yakin tidak perlu khawatir tentang (atau memiliki) elemen duplikat, Anda bisa menggunakannya TreeSet<T>. Itu mengimplementasikan SortedSetdan NavigableSetantarmuka dan bekerja seperti yang mungkin Anda harapkan dari daftar:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Jika Anda tidak ingin pemesanan alami, Anda dapat menggunakan parameter konstruktor yang mengambil a Comparator<T>.

Atau, Anda dapat menggunakan Multiset (juga dikenal sebagai Tas ) , yaitu Setyang memungkinkan elemen duplikat, dan ada implementasi pihak ketiga. Terutama dari perpustakaan Jambu adaTreeMultiset , yang bekerja sangat mirip TreeSet.

2. Urutkan daftar Anda dengan Collections.sort()

Seperti disebutkan di atas, pengurutan List s adalah manipulasi struktur data. Jadi untuk situasi di mana Anda membutuhkan "satu sumber kebenaran" yang akan diurutkan dalam berbagai cara, maka mengurutkannya secara manual adalah cara yang harus ditempuh.

Anda dapat mengurutkan daftar Anda dengan java.util.Collections.sort()metode ini. Berikut ini contoh kode tentang caranya:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Menggunakan pembanding

Salah satu manfaat yang jelas adalah bahwa Anda dapat menggunakan Comparatordalam sortmetode. Java juga menyediakan beberapa implementasi untuk Comparatorseperti Collatoryang berguna untuk lokal string penyortiran sensitif. Ini salah satu contohnya:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Menyortir dalam lingkungan berbarengan

Namun perlu dicatat bahwa menggunakan sortmetode ini tidak ramah di lingkungan bersamaan, karena instance koleksi akan dimanipulasi, dan Anda sebaiknya mempertimbangkan untuk menggunakan koleksi yang tidak dapat diubah. Ini adalah sesuatu yang disediakan oleh Guava di Orderingkelas dan merupakan one-liner sederhana:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Bungkus daftar Anda dengan java.util.PriorityQueue

Meskipun tidak ada daftar yang diurutkan di Jawa, namun ada antrian yang diurutkan yang mungkin akan bekerja dengan baik untuk Anda. Itu java.util.PriorityQueuekelasnya.

Nico Haase menautkan di komentar ke pertanyaan terkait yang juga menjawab ini.

Dalam koleksi yang diurutkan Anda kemungkinan besar tidak ingin memanipulasi struktur data internal yang mengapa PriorityQueue tidak mengimplementasikan antarmuka Daftar (karena itu akan memberi Anda akses langsung ke elemen-elemennya).

Peringatan pada PriorityQueueiterator

The PriorityQueuekelas alat yang Iterable<E>dan Collection<E>antarmuka sehingga dapat mengulangi seperti biasa. Namun, iterator tidak dijamin untuk mengembalikan elemen dalam urutan yang diurutkan. Alih-alih (seperti yang ditunjukkan Alderath dalam komentar), Anda harus poll()mengantri sampai kosong.

Perhatikan bahwa Anda dapat mengonversi daftar ke antrian prioritas melalui konstruktor yang mengambil koleksi apa pun :

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Tulis SortedListkelas Anda sendiri

CATATAN: Anda tidak harus melakukan ini.

Anda bisa menulis kelas Daftar Anda sendiri yang mengurutkan setiap kali Anda menambahkan elemen baru. Ini bisa menjadi perhitungan yang berat tergantung pada implementasi Anda dan tidak ada gunanya , kecuali jika Anda ingin melakukannya sebagai latihan, karena dua alasan utama:

1. Itu melanggar kontrak yang List<E>dimiliki antarmuka karena addmetode harus memastikan bahwa elemen akan berada dalam indeks yang ditentukan pengguna.
2. Mengapa menemukan kembali roda? Anda harus menggunakan TreeSet atau Multisets sebagai gantinya seperti yang ditunjukkan pada poin pertama di atas.

Namun, jika Anda ingin melakukannya sebagai latihan di sini adalah contoh kode untuk Anda mulai, menggunakan AbstractListkelas abstrak:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Perhatikan bahwa jika Anda belum mengganti metode yang Anda butuhkan, maka implementasi default dari AbstractListakan membuang UnsupportedOperationException.

Karena konsep Daftar tidak sesuai dengan konsep koleksi yang diurutkan secara otomatis. Inti dari Daftar adalah bahwa setelah memanggil list.add(7, elem), panggilan ke list.get(7)akan kembali elem. Dengan daftar yang diurutkan secara otomatis, elemen dapat berakhir pada posisi yang sewenang-wenang.

Karena semua daftar sudah "diurutkan" berdasarkan urutan item yang ditambahkan (pemesanan FIFO), Anda dapat "resor" dengan urutan lain, termasuk pemesanan elemen secara alami, menggunakan java.util.Collections.sort().

EDIT:

Daftar sebagai struktur data didasarkan pada apa yang menarik adalah urutan di mana barang-barang dimasukkan.

Set tidak memiliki informasi itu.

Jika Anda ingin memesan dengan menambahkan waktu, gunakan List. Jika Anda ingin memesan dengan kriteria lain, gunakan SortedSet.

Set dan Map adalah struktur data non-linear. Daftar adalah struktur data linier.

Struktur data pohon SortedSetdan SortedMapantarmuka mengimplementasikan TreeSetdan TreeMapmasing-masing menggunakan algoritma implementasi pohon Merah-Hitam yang digunakan. Jadi itu memastikan bahwa tidak ada item duplikat (atau kunci jika Map)

• List sudah mempertahankan koleksi tertata dan struktur data berbasis indeks, pohon bukanlah struktur data berbasis indeks.
• Tree menurut definisi tidak boleh mengandung duplikat.
• Dalam Listkita dapat memiliki duplikat, jadi tidak ada TreeList(yaitu tidak SortedList).
• Daftar mempertahankan elemen dalam urutan penyisipan. Jadi jika kita ingin mengurutkan daftar kita harus menggunakan java.util.Collections.sort(). Ini mengurutkan daftar yang ditentukan ke dalam urutan menaik, sesuai dengan urutan alami unsur-unsurnya.

JavaFX SortedList

Meskipun butuh beberapa saat, Java 8 memang memiliki diurutkan List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Seperti yang Anda lihat di javadocs, itu adalah bagian dari koleksi JavaFX , dimaksudkan untuk memberikan tampilan yang diurutkan pada ObservableList.

Pembaruan: Perhatikan bahwa dengan Java 11, toolkit JavaFX telah pindah ke luar JDK dan sekarang menjadi perpustakaan yang terpisah. JavaFX 11 tersedia sebagai SDK yang dapat diunduh atau dari MavenCentral. Lihat https://openjfx.io

Untuk setiap pendatang baru, per April 2015, Android sekarang memiliki kelas SortedList di perpustakaan dukungan, yang dirancang khusus untuk bekerja dengannya RecyclerView. Inilah posting blog tentang itu.

Poin lainnya adalah kompleksitas waktu operasi penyisipan. Untuk memasukkan daftar, orang mengharapkan kompleksitas O (1). Tetapi ini tidak dapat dijamin dengan daftar yang diurutkan.

Dan poin yang paling penting adalah bahwa daftar tidak berasumsi tentang elemen mereka. Misalnya, Anda dapat membuat daftar hal-hal yang tidak diterapkan equalsatau compare.

Pikirkan seperti ini: Listantarmuka memiliki metode seperti add(int index, E element),set(int index, E element) . Kontraknya adalah bahwa sekali Anda menambahkan elemen pada posisi X Anda akan menemukannya di sana kecuali Anda menambahkan atau menghapus elemen sebelumnya.

Jika implementasi daftar apa pun akan menyimpan elemen dalam urutan selain berdasarkan indeks, metode daftar di atas tidak masuk akal.

Baris pertama dalam API Daftar mengatakan itu adalah koleksi yang dipesan (juga dikenal sebagai urutan). Jika Anda mengurutkan daftar, Anda tidak dapat mempertahankan pesanan, jadi tidak ada TreeList di Jawa.
Seperti kata API, Daftar Java terinspirasi dari Sequence dan lihat properti sequence http://en.wikipedia.org/wiki/Sequence_(mathematics )

Itu tidak berarti bahwa Anda tidak dapat mengurutkan daftar, tetapi Java ketat dengan definisinya dan tidak menyediakan versi daftar yang diurutkan secara default.

Jika Anda mencari cara untuk mengurutkan elemen, tetapi juga dapat mengaksesnya dengan indeks secara efisien, Anda dapat melakukan hal berikut:

1. Gunakan daftar akses acak untuk penyimpanan (mis. ArrayList)
2. Pastikan selalu disortir

Kemudian untuk menambah atau menghapus elemen yang bisa Anda gunakan Collections.binarySearchuntuk mendapatkan indeks penyisipan / penghapusan. Karena daftar Anda menerapkan akses acak, Anda dapat secara efisien mengubah daftar dengan indeks yang ditentukan.

Contoh:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}

Pertimbangkan untuk menggunakan indeks-pohon-peta . Ini TreeSet JDK yang disempurnakan yang menyediakan akses ke elemen dengan indeks dan menemukan indeks elemen tanpa iterasi atau daftar tersembunyi yang mendasari yang mendukung pohon. Algoritma ini didasarkan pada pembaruan bobot dari perubahan node setiap kali ada perubahan.