Verzameling gesorteerd in Java

Ik ben een beginner in Java. Geef aan welke collectie(s) kunnen/moeten worden gebruikt voor het bijhouden van een gesorteerde lijst in Java. Ik heb Mapen Setgeprobeerd, maar ze waren niet wat ik zocht.

Antwoord 1, autoriteit 100%

Dit komt erg laat, maar er is een klasse in de JDK die alleen bedoeld is om een ​​gesorteerde lijst te hebben. Het heet (enigszins niet in orde met de andere Sorted*interfaces) “java.util.PriorityQueue“. Het kan ofwel Comparable<?>s sorteren of een Comparatorgebruiken.

Het verschil met een Listgesorteerd met Collections.sort(...)is dat dit te allen tijde een gedeeltelijke volgorde behoudt, met O(log(n )) invoegprestaties, door gebruik te maken van een heap-gegevensstructuur, terwijl het invoegen in een gesorteerde ArrayListO(n) is (dwz met binair zoeken en verplaatsen).

In tegenstelling tot een Listondersteunt PriorityQueueechter geen geïndexeerde toegang (get(5)), de enige manier om toegang tot items in een hoop is om ze een voor een te verwijderen(vandaar de naam PriorityQueue).

Antwoord 2, autoriteit 28%

TreeMap en TreeSet geven u een herhaling van de inhoud in gesorteerde volgorde. Of u kunt een ArrayList gebruiken en Collections.sort() gebruiken om deze te sorteren. Al die klassen staan ​​in java.util

Antwoord 3, autoriteit 18%

Als u een gesorteerde lijstwilt behouden die u vaak zult wijzigen(dwz een structuur die niet alleen gesorteerd is, maar ook duplicaten toestaat en waarvan de elementen efficiënt kunnen worden waarnaar wordt verwezen door index), gebruik dan een ArrayList, maar als u een element moet invoegen, gebruik dan altijd Collections.binarySearch() om de indexte bepalen waaraan u een bepaald element toevoegt. De laatste methode vertelt je de index die je moet invoegen om je lijst in gesorteerde volgorde te houden.

Antwoord 4, autoriteit 17%

Gebruik TreeMultisetklasse. Guavaheeft een spectaculaire verzamelings-API.

Een probleem met het leveren van een implementatie van List die de gesorteerde volgorde handhaaft, is de belofte die in de JavaDocs van de add()-methode wordt gedaan.

Antwoord 5, autoriteit 6%

U wilt de SortedSetimplementaties, namelijk TreeSet.

Antwoord 6, autoriteit 6%

Er zijn een paar opties. Ik raad TreeSet aan als je geen duplicaten wilt en de objecten die je invoegt vergelijkbaar zijn.

Je kunt hiervoor ook de statische methoden van de klasse Collections gebruiken.

Zie Collecties#sort(java.util.List)en TreeSetvoor meer info.

Antwoord 7, autoriteit 5%

Als je alleen een lijst wilt sorteren, gebruik dan een soort Lijsten gebruik Collecties.sort(). Als u er zeker van wilt zijn dat elementen in de lijst uniek en altijd gesorteerd zijn, gebruikt u een SortedSet.

Antwoord 8, autoriteit 3%

Wat ik heb gedaan is het implementeren van List met een interne instantie met alle gedelegeerde methoden.

public class ContactList implements List<Contact>, Serializable {
    private static final long serialVersionUID = -1862666454644475565L;
    private final List<Contact> list;
public ContactList() {
    super();
    this.list = new ArrayList<Contact>();
}
public ContactList(List<Contact> list) {
    super();
    //copy and order list
    List<Contact>aux= new ArrayList(list);
    Collections.sort(aux);
    this.list = aux;
}
public void clear() {
    list.clear();
}
public boolean contains(Object object) {
    return list.contains(object);
}

Daarna heb ik een nieuwe methode “putOrdered” geïmplementeerd die in de juiste positie wordt ingevoegd als het element niet bestaat of wordt vervangen voor het geval het bestaat.

public void putOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
        list.add(index, contact);
    }else{
        list.set(index, contact);
    }
}

Als je herhaalde elementen wilt toestaan, implementeer dan gewoon addOrdered (of beide).

public void addOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
    }
    list.add(index, contact);
}

Als u invoegingen wilt vermijden, kunt u ook een uitzondering voor bewerkingen en niet-ondersteunde bewerkingen gebruiken voor de methoden “add” en “set”.

public boolean add(Contact object) {
    throw new UnsupportedOperationException("Use putOrdered instead");
}

… en ook U moet voorzichtig zijn met ListIterator-methoden omdat ze uw interne lijst kunnen wijzigen. In dit geval kunt u een kopie van de interne lijst retourneren of opnieuw een uitzondering maken.

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}

Antwoord 9, autoriteit 3%

De meest efficiënte manier om een ​​gesorteerde lijst te implementeren zoals u wilt, is door een indexeerbare skiplist te implementeren zoals hier: Wikipedia: indexeerbare skiplist.
Het zou toelaten om toevoegingen/verwijderingen in O(log(n)) te hebben en zou tegelijkertijd geïndexeerde toegang mogelijk maken. En het zou ook duplicaten toestaan.

Skiplist is een behoorlijk interessante en, zou ik zeggen, ondergewaardeerde datastructuur.
Helaas is er geen geïndexeerde skiplist-implementatie in de Java-basisbibliotheek, maar u kunt een van de open source-implementaties gebruiken of deze zelf implementeren. Er zijn reguliere Skiplist-implementaties zoals ConcurrentSkipListSeten ConcurrentSkipListMap

Antwoord 10, autoriteit 2%

TreeSet zou niet werken omdat ze geen duplicaten toestaan ​​en ze bieden geen methode om elementen op een specifieke positie op te halen. PriorityQueue zou niet werken omdat het niet toestaat om elementen op een specifieke positie op te halen, wat een basisvereiste is voor een lijst.
Ik denk dat je je eigen algoritme moet implementeren om een ​​gesorteerde lijst in Java bij te houden met O (logn) invoegtijd, tenzij je geen duplicaten nodig hebt.
Misschien zou een oplossing het gebruik van een TreeMap kunnen zijn waarbij de sleutel een subklasse van het item is die de equals-methode overschrijft, zodat duplicaten zijn toegestaan.

11

Voor set kunt u bomenet gebruiken. Bomenet bestellingen zijn elementen op basis van een natuurlijke bestellingen of elke sorteervolgorde die is doorgegeven aan de vergelijkbare voor die specifieke object.
Gebruik voor kaart TreMap. Treemap biedt het sorteren over sleutels. Om een ​​object toe te voegen als een sleutel tot het TREEMAP, moet deze klasse een vergelijkbare interface implementeren die in de beurt krachten om te implementeren vergelijken met () methode die de definitie van de sorteervolgorde bevat.
http://techmastertutorial.in/java-collection-impl.html

12

Wat u wilt is een binaire zoekboom. Het onderhoudt gesorteerde volgorde tijdens het aanbieden van logaritmische toegang voor zoekopdrachten, verhuizingen en inserties (tenzij u een gedegenereerde boom hebt – dan is het lineair). Het is vrij eenvoudig te implementeren en u kunt het zelfs de lijstinterface uitvoeren, maar dan wordt de indextoegang ingewikkeld.

Tweede aanpak is om een ​​arrayclist te hebben en vervolgens een implementatie van een bubbelzaken. Omdat u één element per keer invoegt of verwijdert, zijn de toegangstijden voor inserties en verhuizingen lineair. Zoekopdrachten zijn logaritmische en indextoegangsconstante (TIJD KUNNEN VERSCHILLEND VOOR LACHEDELLAGEN). De enige code die u nodig hebt is 5, misschien 6 regels bubble sorteren.

13

U kunt Arrayclist en TreMap gebruiken, zoals u zei dat u ook herhaalde waarden wilt, dan kunt u geen bomenet gebruiken, hoewel het ook wordt gesorteerd, maar u moet de comparator definiëren.

14

Gebruik TreeSetdie elementen in gesorteerde volgorde geeft. Of gebruik Collection.sort()voor externe sortering met Comparator().