Java Language
lijsten

Invoering

Syntaxis

• ls.add (E-element); // Voegt een element toe
• ls.remove (E-element); // Verwijdert een element
• voor (E-element: ls) {} // Itereert over elk element
• ls.toArray (nieuwe string [ls.length]); // Converteert een lijst met strings naar een reeks strings
• ls.get (int index); // Retourneert het element op de opgegeven index.
• ls.set (int index, E element); // Vervangt het element op een opgegeven positie.
• ls.isEmpty (); // Retourneert true als de array geen elementen bevat, anders wordt false geretourneerd.
• ls.indexOf (Object o); // Retourneert de index van de eerste locatie van het opgegeven element o of retourneert -1 als dit niet aanwezig is.
• ls.lastIndexOf (Object o); // Retourneert de index van de laatste locatie van het opgegeven element o of retourneert -1 als dit niet aanwezig is.
• ls.size (); // Retourneert het aantal elementen in de lijst.

Opmerkingen

List<String> list = new ArrayList<>();
list.add("world");
System.out.println(list.indexOf("world"));      // Prints "0"
// Inserting a new value at index 0 moves "world" to index 1
list.add(0, "Hello");
System.out.println(list.indexOf("world"));      // Prints "1"
System.out.println(list.indexOf("Hello"));      // Prints "0"

Een generieke lijst sorteren

De klasse Collections biedt twee standaard statische methoden om een lijst te sorteren:

• sort(List<T> list) toepassing op lijsten waar T extends Comparable<? super T> , en
• sort(List<T> list, Comparator<? super T> c) toepassing op lijsten van elk type.

Voor het toepassen van de eerstgenoemde moet de klasse van lijstelementen die worden gesorteerd worden gewijzigd, wat niet altijd mogelijk is. Het kan ook ongewenst zijn, want hoewel het standaard sorteren biedt, kunnen andere sorteeropdrachten in verschillende omstandigheden nodig zijn of is sorteren slechts een eenmalige taak.

Overweeg dat we een taak hebben voor het sorteren van objecten die instanties zijn van de volgende klasse:

public class User {
    public final Long id;
    public final String username;

    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return String.format("%s:%d", username, id);
    }
}

Om Collections.sort(List<User> list) , moeten we de klasse User aanpassen om de Comparable interface te implementeren. Bijvoorbeeld

public class User implements Comparable<User> {
    public final Long id;
    public final String username;

    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return String.format("%s:%d", username, id);
    }

    @Override
    /** The natural ordering for 'User' objects is by the 'id' field. */
    public int compareTo(User o) {
        return id.compareTo(o.id);
    }
}

(Terzijde: veel standaard Java-klassen zoals String , Long , Integer implementeren de Comparable interface. Dit maakt lijsten van die elementen standaard sorteerbaar en vereenvoudigt de implementatie van compare of compareTo in andere klassen.)

Met de bovenstaande aanpassing kunnen we eenvoudig een lijst met User sorteren op basis van de natuurlijke volgorde van de klassen. (In dit geval hebben we dat gedefinieerd als bestellen op basis van id waarden). Bijvoorbeeld:

List<User> users = Lists.newArrayList(
    new User(33L, "A"),
    new User(25L, "B"),
    new User(28L, ""));
Collections.sort(users);

System.out.print(users);
// [B:25, C:28, A:33]

Stel dat we User op name wilden sorteren in plaats van op id . Of stel dat we de klasse niet hebben kunnen wijzigen om Comparable te kunnen implementeren.

Dit is waar de sort met het argument Comparator nuttig is:

Collections.sort(users, new Comparator<User>() {
    @Override
    /* Order two 'User' objects based on their names. */
    public int compare(User left, User right) {
        return left.username.compareTo(right.username);
    }
});
System.out.print(users);
// [A:33, B:25, C:28]

Collections.sort(users, (l, r) -> l.username.compareTo(r.username));

users.sort((l, r) -> l.username.compareTo(r.username))

Een lijst maken

Uw lijst een type geven

Om een lijst te maken heeft u een type nodig (elke klasse, bijv. String ). Dit is het type van uw List . In de List worden alleen objecten van het opgegeven type opgeslagen. Bijvoorbeeld:

List<String> strings;

Kan "string1" , "hello world!" "string1" , "goodbye" , enz., maar het kan 9.2 echter niet opslaan:

List<Double> doubles;

Kan 9.2 opslaan, maar niet "hello world!" .

Initialiseren van uw lijst

Als je iets aan de bovenstaande lijsten probeert toe te voegen, krijg je een NullPointerException, omdat strings en doubles beide gelijk nul zijn !

Er zijn twee manieren om een lijst te initialiseren:

Optie 1: gebruik een klasse die List implementeert

List is een interface, wat betekent dat er geen constructor is, maar methoden die een klasse moet overschrijven. ArrayList is de meest gebruikte List , hoewel LinkedList ook gebruikelijk is. Dus initialiseren we onze lijst als volgt:

List<String> strings = new ArrayList<String>();

of

List<String> strings = new LinkedList<String>();

List<String> strings = new ArrayList<>();

List<String> strings = new LinkedList<>();

Optie 2: gebruik de collectiescollectie

De klasse Collections biedt twee handige methoden voor het maken van lijsten zonder een variabele List :

• emptyList() : geeft een lege lijst terug.
• singletonList(T) : maakt een lijst van type T en voegt het opgegeven element toe.

En een methode die een bestaande List gebruikt om gegevens in te vullen:

• addAll(L, T...) : voegt alle opgegeven elementen toe aan de lijst die wordt doorgegeven als de eerste parameter.

Voorbeelden:

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

List<Integer> l = Collections.emptyList();
List<Integer> l1 = Collections.singletonList(42);
Collections.addAll(l1, 1, 2, 3);

Positionele toegangsbewerkingen

De List API heeft acht methoden voor positionele toegangsbewerkingen:

• add(T type)
• add(int index, T type)
• remove(Object o)
• remove(int index)
• get(int index)
• set(int index, E element)
• int indexOf(Object o)
• int lastIndexOf(Object o)

Dus als we een lijst hebben:

List<String> strings = new ArrayList<String>();

En we wilden de strings toevoegen "Hallo wereld!" en "Tot ziens wereld!" we zouden het als zodanig doen:

strings.add("Hello world!");
strings.add("Goodbye world!");

En onze lijst zou de twee elementen bevatten. Laten we nu zeggen dat we "Programma starten!" bovenaan de lijst. We zouden dit als volgt willen doen:

strings.add(0, "Program starting!");

OPMERKING: Het eerste element is 0.

Als we nu de "Vaarwel-wereld!" Wilden verwijderen lijn, we kunnen het zo doen:

strings.remove("Goodbye world!");

En als we de eerste regel wilden verwijderen (in dit geval "Programma starten!"), Kunnen we dit als volgt doen:

strings.remove(0);

Notitie:

1. Het toevoegen en verwijderen van lijstelementen wijzigt de lijst en dit kan leiden tot een ConcurrentModificationException als de lijst gelijktijdig wordt herhaald.

2. Het toevoegen en verwijderen van elementen kan O(1) of O(N) afhankelijk van de lijstklasse, de gebruikte methode en of u een element aan het begin, aan het einde of in het midden van de lijst toevoegt / verwijdert.

Om een element van de lijst op een gespecificeerde positie op te halen, kunt u de E get(int index); methode van de List API. Bijvoorbeeld:

strings.get(0);

retourneert het eerste element van de lijst.

U kunt elk element op een opgegeven positie vervangen met behulp van de set(int index, E element); . Bijvoorbeeld:

strings.set(0,"This is a replacement");

Hiermee wordt de tekenreeks 'Dit is een vervanging' ingesteld als het eerste element van de lijst.

Opmerking: de ingestelde methode overschrijft het element op positie 0. Het voegt de nieuwe string niet toe op positie 0 en duwt de oude naar positie 1.

De int indexOf(Object o); geeft de positie terug van het eerste exemplaar van het object dat als argument is doorgegeven. Als het object niet voorkomt in de lijst, wordt de waarde -1 geretourneerd. Als vervolg op het vorige voorbeeld:

strings.indexOf("This is a replacement")

de 0 zal naar verwachting worden geretourneerd als we de String "Dit is een vervanging" in positie 0 van onze lijst plaatsen. In het geval dat er meer dan één exemplaar in de lijst voorkomt wanneer int indexOf(Object o); wordt genoemd, zoals vermeld, wordt de index van het eerste exemplaar geretourneerd. Door de int lastIndexOf(Object o) roepen int lastIndexOf(Object o) kunt u de index van het laatste exemplaar in de lijst ophalen. Dus als we nog een toevoegen: "Dit is een vervanging":

strings.add("This is a replacement");
strings.lastIndexOf("This is a replacement");

Deze keer wordt de 1 geretourneerd en niet de 0;

Herhalen van elementen in een lijst

Laten we bijvoorbeeld zeggen dat we een lijst van het type String hebben die vier elementen bevat: "hallo", "hoe", "zijn", "u?"

De beste manier om elk element te herhalen is door een lus voor elke lus te gebruiken:

public void printEachElement(List<String> list){
    for(String s : list){
        System.out.println(s);
    }
}

Welke zou afdrukken:

hello,
how
are
you?

Om ze allemaal op dezelfde regel af te drukken, kunt u een StringBuilder gebruiken:

public void printAsLine(List<String> list){
    StringBuilder builder = new StringBuilder();
    for(String s : list){
        builder.append(s);
    }
    System.out.println(builder.toString());
}

Zal afdrukken:

hello, how are you?

Als alternatief kunt u elementindexering gebruiken (zoals beschreven in Toegang tot element op ith Index uit ArrayList ) om een lijst te herhalen. Waarschuwing: deze aanpak is inefficiënt voor gekoppelde lijsten.

Elementen uit lijst B verwijderen die aanwezig zijn in lijst A

Laten we aannemen dat u 2 lijsten A en B hebt en dat u alle elementen uit B die u in A hebt wilt verwijderen, de methode in dit geval is

 List.removeAll(Collection c);

#Voorbeeld:

public static void main(String[] args) {
    List<Integer> numbersA = new ArrayList<>();
    List<Integer> numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));
    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);

    numbersB.removeAll(numbersA);
    System.out.println("B cleared: " + numbersB);
    }

dit wordt afgedrukt

A: [1, 3, 4, 7, 5, 2]

B: [13, 32, 533, 3, 4, 2]

B gewist: [13, 32, 533]

Zoeken naar gemeenschappelijke elementen tussen 2 lijsten

Stel dat u twee lijsten hebt: A en B en dat u de elementen moet vinden die in beide lijsten voorkomen.

U kunt dit doen door gewoon de methode List.retainAll() roepen.

Voorbeeld:

public static void main(String[] args) {
    List<Integer> numbersA = new ArrayList<>();
    List<Integer> numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));

    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);
    List<Integer> numbersC = new ArrayList<>();
    numbersC.addAll(numbersA);
    numbersC.retainAll(numbersB);

    System.out.println("List A : " + numbersA);
    System.out.println("List B : " + numbersB);
    System.out.println("Common elements between A and B: " + numbersC);

}

Converteer een lijst met gehele getallen naar een lijst met tekenreeksen

List<Integer> nums = Arrays.asList(1, 2, 3);
List<String> strings = nums.stream()
    .map(Object::toString)
    .collect(Collectors.toList());

Dat is:

1. Maak een stream uit de lijst
2. Wijs elk element toe met Object::toString
3. Verzamel de String in een List met Collectors.toList()

Element maken, toevoegen en verwijderen uit een ArrayList

ArrayList is een van de ingebouwde datastructuren in Java. Het is een dynamische array (waarbij de grootte van de gegevensstructuur niet eerst moest worden aangegeven) voor het opslaan van elementen (objecten).

Het strekt zich AbstractList klasse en implementeert List interface. Een ArrayList kan dubbele elementen bevatten waarin de ArrayList wordt gehandhaafd. Opgemerkt moet worden dat de klasse ArrayList niet-gesynchroniseerd is, dus wees voorzichtig bij het omgaan met gelijktijdigheid met ArrayList . ArrayList biedt willekeurige toegang omdat de array op indexbasis werkt. Manipulatie is langzaam in ArrayList vanwege verschuiving die vaak optreedt wanneer een element uit de arraylijst wordt verwijderd.

Een ArrayList kan als volgt worden gemaakt:

List<T> myArrayList = new ArrayList<>();

Waar T ( Generiek ) het type is dat wordt opgeslagen in ArrayList .

Het type van de ArrayList kan elk object zijn. Het type kan geen primitief type zijn (gebruik in plaats daarvan hun wrapper-klassen ).

Gebruik de methode add() om een element toe te voegen aan de ArrayList :

myArrayList.add(element);

Of om een item toe te voegen aan een bepaalde index:

myArrayList.add(index, element); //index of the element should be an int (starting from 0)

Gebruik de methode remove() om een item uit de ArrayList remove() :

myArrayList.remove(element);

Of om een item uit een bepaalde index te verwijderen:

myArrayList.remove(index); //index of the element should be an int (starting from 0)

Ter vervanging van een lijstelement

Dit voorbeeld is over het vervangen van een List element waarborgt dat het vervangingselement zich op dezelfde positie als het element dat wordt vervangen.

Dit kan met behulp van deze methoden:

• set (int index, T type)
• int indexOf (T type)

Overweeg een ArrayList met de elementen "Programma starten!", "Hallo wereld!" en "Tot ziens wereld!"

List<String> strings = new ArrayList<String>();
strings.add("Program starting!");
strings.add("Hello world!");
strings.add("Goodbye world!");

Als we de index kennen van het element dat we willen vervangen, kunnen we set als volgt gebruiken:

strings.set(1, "Hi world");

Als we de index niet kennen, kunnen we deze eerst zoeken. Bijvoorbeeld:

int pos = strings.indexOf("Goodbye world!");
if (pos >= 0) {
    strings.set(pos, "Goodbye cruel world!");
}

Opmerkingen:

1. De set bewerking veroorzaakt geen ConcurrentModificationException .
2. De set bewerking is snel ( O(1) ) voor ArrayList maar langzaam ( O(N) ) voor een LinkedList .
3. Een indexOf zoeken op een ArrayList of LinkedList is langzaam ( O(N) ).

Een lijst ongewijzigd maken

De klasse Collecties biedt een manier om een lijst niet te wijzigen:

List<String> ls = new ArrayList<String>();
List<String> unmodifiableList = Collections.unmodifiableList(ls);

Als u een niet-wijzigbare lijst met één item wilt, kunt u het volgende gebruiken:

List<String> unmodifiableList = Collections.singletonList("Only string in the list");

Objecten verplaatsen in de lijst

Met de klasse Collecties kunt u objecten op verschillende manieren in de lijst verplaatsen (ls is de lijst):

Een lijst omkeren:

Collections.reverse(ls);

Roterende posities van elementen in een lijst

De rotatiemethode vereist een geheel getalargument. Dit is het aantal plaatsen om het langs de lijn te verplaatsen. Een voorbeeld hiervan is hieronder:

List<String> ls = new ArrayList<String>();
ls.add(" how");
ls.add(" are");
ls.add(" you?");
ls.add("hello,");
Collections.rotate(ls, 1);

for(String line : ls) System.out.print(line);
System.out.println();

Dit zal afdrukken "hallo, hoe gaat het?"

Elementen in een lijst door elkaar schudden

Met dezelfde bovenstaande lijst kunnen we de elementen in een lijst in willekeurige volgorde plaatsen:

Collections.shuffle(ls);

We kunnen het ook een java.util.Random-object geven dat het gebruikt om objecten willekeurig op plekken te plaatsen:

Random random = new Random(12); 
Collections.shuffle(ls, random);

Klassen die Lijst uitvoeren - Voors en tegens

De List -interface wordt geïmplementeerd door verschillende klassen. Elk van hen heeft zijn eigen manier om het met verschillende strategieën te implementeren en verschillende voor- en nadelen te bieden.

Klassen die lijst implementeren

Dit zijn alle public klassen in Java SE 8 die de interface java.util.List implementeren:

1. Abstracte klassen:
   • AbstractList
   • AbstractSequentialList
2. Concrete klassen:
   • ArrayList
   • AttributeList
   • CopyOnWriteArrayList
   • LinkedList
   • RoleList
   • RoleUnresolvedList
   • stack
   • Vector

Voors en tegens van elke implementatie in termen van tijdcomplexiteit

ArrayList

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList is een resizable-array-implementatie van de lijstinterface. ArrayList slaat de lijst op in een array en biedt methoden (naast de methoden die de List- interface implementeren) voor het manipuleren van de grootte van de array.

Initialiseer ArrayList van Integer met maat 100

List<Integer> myList = new ArrayList<Integer>(100); // Constructs an empty list with the specified initial capacity.

- PROS:

De operaties size, isEmpty, get , set , iterator en listIterator worden in constante tijd uitgevoerd. Het ophalen en instellen van elk element van de lijst heeft dus dezelfde tijdkosten :

int e1 = myList.get(0);  //   \
int e2 = myList.get(10); //    | => All the same constant cost => O(1)
myList.set(2,10);        //   /

- CONS:

Het implementeren van een array (statische structuur) die elementen toevoegt over de grootte van de array heeft grote kosten, omdat een nieuwe toewijzing moet worden gedaan voor de hele array. Uit documentatie :

De toevoegbewerking wordt uitgevoerd in geamortiseerde constante tijd, dat wil zeggen dat het toevoegen van n elementen O (n) tijd vereist

Het verwijderen van een element vereist O (n) tijd.

AttributeList

Komt eraan

CopyOnWriteArrayList

Komt eraan

LinkedList

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList wordt geïmplementeerd door een dubbel gekoppelde lijst, een gekoppelde gegevensstructuur die bestaat uit een reeks opeenvolgend gekoppelde records, knooppunten genoemd.

Iitialize LinkedList van Integer

List<Integer> myList = new LinkedList<Integer>(); // Constructs an empty list.

- PROS:

Het toevoegen of verwijderen van een element vooraan of achteraan heeft een constante tijd.

myList.add(10);  // \
myList.add(0,2); //  | => constant time => O(1)
myList.remove(); // /

- CONS: Uit documentatie :

Bewerkingen die in de lijst worden geïndexeerd, doorlopen de lijst vanaf het begin of het einde, afhankelijk van welke het dichtst bij de opgegeven index ligt.

Bewerkingen zoals:

myList.get(10);    // \
myList.add(11,25); //  | => worst case done in O(n/2)
myList.set(15,35); // /

RoleList

Komt eraan

RoleUnresolvedList

Komt eraan

stack

Komt eraan

Vector

Komt eraan