Suche…


Einführung

Eine Liste ist eine geordnete Sammlung von Werten. In Java sind Listen Teil des Java Collections Framework . Listen implementieren die Schnittstelle java.util.List , die java.util.Collection .

Syntax

  • ls.add (E-Element); // Fügt ein Element hinzu
  • ls.remove (E-Element); // Entfernt ein Element
  • for (E Element: ls) {} // Iteriert über jedes Element
  • ls.toArray (neuer String [ls.length]); // Konvertiert eine Liste von Strings in ein Array von Strings
  • ls.get (int index); // Gibt das Element am angegebenen Index zurück.
  • ls.set (int index, E-Element); // Ersetzt das Element an einer angegebenen Position.
  • ls.isEmpty (); // Gibt true zurück, wenn das Array keine Elemente enthält. Andernfalls wird false zurückgegeben.
  • ls.indexOf (Objekt o); // Liefert den Index der ersten Position des angegebenen Elements o oder, falls nicht vorhanden, -1.
  • ls.lastIndexOf (Objekt o); // Gibt den Index der letzten Position des angegebenen Elements zurück, o oder, falls nicht vorhanden, -1.
  • ls.size (); // Gibt die Anzahl der Elemente in der Liste zurück.

Bemerkungen

Eine Liste ist ein Objekt, in dem eine geordnete Wertesammlung gespeichert wird. "Bestellt" bedeutet, dass die Werte in einer bestimmten Reihenfolge gespeichert werden - ein Element steht an erster Stelle, einer an zweiter Stelle usw. Die einzelnen Werte werden üblicherweise als "Elemente" bezeichnet. Java-Listen bieten normalerweise diese Funktionen:

  • Listen können null oder mehr Elemente enthalten.
  • Listen können doppelte Werte enthalten. Mit anderen Worten, ein Element kann mehrmals in eine Liste eingefügt werden.
  • Listen speichern ihre Elemente in einer bestimmten Reihenfolge, das heißt, ein Element steht an erster Stelle, eines kommt an und so weiter.
  • Jedes Element hat einen Index , der seine Position innerhalb der Liste angibt. Das erste Element hat den Index 0, das nächste Element den Index 1 und so weiter.
  • Listen erlauben das Einfügen von Elementen am Anfang, am Ende oder an einem beliebigen Index innerhalb der Liste.
  • Beim Testen, ob eine Liste einen bestimmten Wert enthält, müssen Sie in der Regel jedes Element in der Liste überprüfen. Dies bedeutet, dass die Zeit zum Durchführen dieser Prüfung O (n) ist , proportional zur Größe der Liste.

Durch Hinzufügen eines Werts zu einer Liste an einem anderen Punkt als dem Ende werden alle folgenden Elemente nach "unten" oder "nach rechts" verschoben. Mit anderen Worten, durch Hinzufügen eines Elements am Index n wird das Element, das sich zuvor am Index n befand, zum Index n + 1 usw. verschoben. Zum Beispiel:

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"

Eine generische Liste sortieren

Die Collections Klasse bietet zwei statische Standardmethoden zum Sortieren einer Liste:

  • sort(List<T> list) gilt für Listen, bei denen T extends Comparable<? super T> und
  • sort(List<T> list, Comparator<? super T> c) anwendbar für Listen eines beliebigen Typs.

Die erstere Anwendung erfordert die Änderung der Klasse der zu sortierenden Listenelemente, was nicht immer möglich ist. Es kann auch unerwünscht sein, da es zwar die Standardsortierung vorsieht, andere Sortierreihenfolgen jedoch unter verschiedenen Umständen erforderlich sein können oder dass das Sortieren nur eine einmalige Aufgabe ist.

Angenommen, wir haben die Aufgabe, Objekte zu sortieren, die Instanzen der folgenden Klasse sind:

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

Um Collections.sort(List<User> list) , müssen Sie die User ändern, um die Comparable Schnittstelle zu implementieren. Zum Beispiel

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

(Nebenbei: Viele Standard-Java-Klassen wie String , Long und Integer implementieren die Comparable Schnittstelle. Dadurch werden Listen dieser Elemente standardmäßig sortierbar und die Implementierung von compare oder compareTo in anderen Klassen vereinfacht.)

Mit der obigen Änderung können Sie eine Liste von User auf einfache Weise anhand der natürlichen Reihenfolge der Klassen sortieren. (In diesem Fall haben wir das definiert, um anhand von id Werten zu ordnen). Zum Beispiel:

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]

Nehmen wir jedoch an, wir wollten User nach name und nicht nach id sortieren. Nehmen Sie alternativ an, dass wir die Klasse nicht so ändern konnten, dass sie Comparable implementiert.

Hier ist die sort mit dem Comparator Argument hilfreich:

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]
Java SE 8

In Java 8 können Sie ein Lambda anstelle einer anonymen Klasse verwenden. Letzteres reduziert sich auf einen Einliner:

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

Ferner fügt es Java 8 eine Standard - sort auf der List Schnittstelle, die noch mehr erleichtert das Sortieren.

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

Liste erstellen

Geben Sie Ihrer Liste einen Typ

Um eine Liste zu erstellen, benötigen Sie einen Typ (beliebige Klasse, z. B. String ). Dies ist der Typ Ihrer List . Die List speichert nur Objekte des angegebenen Typs. Zum Beispiel:

List<String> strings;

Kann "string1" speichern, "hello world!" "goodbye" usw., aber es kann keine 9.2 speichern:

List<Double> doubles;

Kann 9.2 speichern, aber nicht "hello world!" .

Initialisieren Sie Ihre Liste

Wenn Sie versuchen, etwas zu den obigen Listen hinzuzufügen, erhalten Sie eine NullPointerException, da strings und doubles beide gleich Null sind !

Es gibt zwei Möglichkeiten, eine Liste zu initialisieren:

Option 1: Verwenden Sie eine Klasse, die List implementiert

List ist eine Schnittstelle, was bedeutet, dass es keinen Konstruktor gibt, sondern Methoden, die eine Klasse überschreiben muss. ArrayList ist die am häufigsten verwendete List , obwohl LinkedList auch häufig ist. Also initialisieren wir unsere Liste so:

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

oder

List<String> strings = new LinkedList<String>();
Java SE 7

Ab Java SE 7 können Sie einen Diamantoperator verwenden :

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

oder

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

Option 2: Verwenden Sie die Collections-Klasse

Die Collections Klasse bietet zwei nützliche Methoden zum Erstellen von Listen ohne List Variable:

  • emptyList() : gibt eine leere Liste zurück.
  • singletonList(T) : erstellt eine Liste vom Typ T und fügt das angegebene Element hinzu.

Und eine Methode, die eine vorhandene List , um Daten einzugeben:

  • addAll(L, T...) : fügt der als ersten Parameter übergebenen Liste alle angegebenen Elemente hinzu.

Beispiele:

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

Positionszugriffsvorgänge

Die Listen-API verfügt über acht Methoden für Positionszugriffsvorgänge:

  • 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)

Wenn wir also eine Liste haben:

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

Und wir wollten die Zeichenfolgen "Hallo Welt!" und "Auf Wiedersehen Welt!" dazu würden wir es so machen:

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

Und unsere Liste würde die zwei Elemente enthalten. Nun wollen wir sagen, wir wollten "Programm starten!" an der Spitze der Liste. Wir würden das so machen:

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

HINWEIS: Das erste Element ist 0.

Nun, wenn wir die "Auf Wiedersehen Welt" entfernen wollten! Linie könnten wir es so machen:

strings.remove("Goodbye world!");

Und wenn wir die erste Zeile entfernen wollten (was in diesem Fall "Programmstart!" Wäre), könnten wir es so machen:

strings.remove(0);

Hinweis:

  1. Durch das Hinzufügen und Entfernen von Listenelementen wird die Liste geändert. Dies kann zu einer ConcurrentModificationException führen, wenn die Liste gleichzeitig durchlaufen wird.

  2. Das Hinzufügen und Entfernen von Elementen kann O(1) oder O(N) abhängig von der Listenklasse, der verwendeten Methode und davon, ob Sie ein Element am Anfang, am Ende oder in der Mitte der Liste hinzufügen oder entfernen.

Um ein Element der Liste an einer bestimmten Position abzurufen, können Sie den E get(int index); Methode der List API. Zum Beispiel:

strings.get(0);

gibt das erste Element der Liste zurück.

Sie können jedes Element an einer bestimmten Position ersetzen, indem Sie das set(int index, E element); . Zum Beispiel:

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

Dies setzt den String "Dies ist ein Ersatz" als erstes Element der Liste.

Hinweis: Die set-Methode überschreibt das Element an Position 0. Die neue Zeichenfolge wird nicht an Position 0 eingefügt und der alte an Position 1 verschoben.

Der int indexOf(Object o); gibt die Position des ersten Vorkommens des als Argument übergebenen Objekts zurück. Wenn das Objekt in der Liste nicht vorkommt, wird der Wert -1 zurückgegeben. In Fortsetzung des vorherigen Beispiels, wenn Sie anrufen:

strings.indexOf("This is a replacement")

Es wird erwartet, dass die 0 zurückgegeben wird, wenn wir den String "Dies ist ein Ersatz" an Position 0 unserer Liste setzen. Wenn es mehr als ein Vorkommen in der Liste gibt, wenn int indexOf(Object o); aufgerufen wird, dann wird wie erwähnt der Index des ersten Vorkommens zurückgegeben. Durch Aufruf des int lastIndexOf(Object o) Sie den Index des letzten Vorkommens in der Liste abrufen. Wenn wir also ein weiteres "Dies ist ein Ersatz" hinzufügen:

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

Diesmal wird die 1 zurückgegeben und nicht die 0;

Elemente in einer Liste durchlaufen

Nehmen wir als Beispiel an, wir haben eine Liste des Typs String, die vier Elemente enthält: "Hallo", "Wie", "Wie", "Sie", "Sie?"

Die beste Möglichkeit, jedes Element zu durchlaufen, ist die Verwendung einer for-each-Schleife:

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

Was würde drucken:

hello,
how
are
you?

Um sie alle in derselben Zeile zu drucken, können Sie einen StringBuilder verwenden:

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

Wird drucken:

hello, how are you?

Alternativ können Sie die Elementindizierung (wie unter Zugriff auf Element unter Index von ArrayList auf Element beschrieben) verwenden, um eine Liste zu durchlaufen. Warnung: Dieser Ansatz ist für verknüpfte Listen ineffizient.

Entfernen von Elementen aus der Liste B, die in der Liste A vorhanden sind

Nehmen wir an, Sie haben 2 Listen A und B, und Sie möchten alle Elemente, die Sie in A haben, von B entfernen. Die Methode in diesem Fall ist

 List.removeAll(Collection c);

#Beispiel:

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

Dies wird gedruckt

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

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

B gelöscht: [13, 32, 533]

Suche nach gemeinsamen Elementen zwischen 2 Listen

Angenommen, Sie haben zwei Listen: A und B, und Sie müssen die Elemente finden, die in beiden Listen vorhanden sind.

Sie können dies tun, indem Sie einfach die Methode List.retainAll() .

Beispiel:

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

}

Konvertieren Sie eine Liste ganzer Zahlen in eine Liste von Zeichenfolgen

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

Das ist:

  1. Erstellen Sie einen Stream aus der Liste
  2. Ordnen Sie jedes Element mithilfe von Object::toString
  3. Sammeln Sie die String Werte mithilfe von Collectors.toList() in einer List

Element aus einer ArrayList erstellen, hinzufügen und entfernen

ArrayList ist eine der integrierten Datenstrukturen in Java. Es ist ein dynamisches Array (bei dem die Größe der Datenstruktur nicht zuerst deklariert werden musste) zum Speichern von Elementen (Objekten).

Es erweitert die AbstractList Klasse und implementiert die List Schnittstelle. Eine ArrayList kann doppelte Elemente enthalten, in denen die Einfügungsreihenfolge beibehalten wird. Es sollte beachtet werden, dass die Klasse ArrayList nicht synchronisiert ist. Beim Umgang mit Parallelität mit ArrayList ist daher Vorsicht geboten. ArrayList ermöglicht den Direktzugriff, da das Array auf der Indexbasis arbeitet. Die Bearbeitung in ArrayList ist langsam, da das Verschieben häufig auftritt, wenn ein Element aus der Array-Liste entfernt wird.

Eine ArrayList kann wie folgt erstellt werden:

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

Dabei ist T ( Generics ) der Typ, der in ArrayList gespeichert wird.

Der Typ der ArrayList kann ein beliebiges Objekt sein. Der Typ kann kein primitiver Typ sein (verwenden Sie stattdessen die Wrapper-Klassen ).

Um der ArrayList ein Element hinzuzufügen, verwenden Sie die add() Methode:

myArrayList.add(element);

Oder um einen Artikel zu einem bestimmten Index hinzuzufügen:

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

Um ein Element aus der ArrayList zu entfernen, verwenden Sie die remove() Methode:

myArrayList.remove(element);

Oder um ein Element aus einem bestimmten Index zu entfernen:

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

Direkter Austausch eines Listenelements

In diesem Beispiel wird ein List Element ersetzt, wobei sichergestellt wird, dass sich das Ersatzelement an derselben Position wie das Element befindet, das ersetzt wird.

Dies kann mit diesen Methoden geschehen:

  • set (int index, T typ)
  • int indexOf (T-Typ)

Betrachten Sie eine ArrayList mit den Elementen "Programm wird gestartet!", "Hallo Welt!" und "Auf Wiedersehen Welt!"

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

Wenn wir den Index des Elements kennen, das wir ersetzen möchten, können Sie set wie folgt verwenden:

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

Wenn wir den Index nicht kennen, können wir ihn zuerst suchen. Zum Beispiel:

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

Anmerkungen:

  1. Die set Operation verursacht keine ConcurrentModificationException .
  2. Die set Operation ist schnell ( O(1) ) für ArrayList aber langsam ( O(N) ) für eine LinkedList .
  3. Eine indexOf Suche in einer ArrayList oder LinkedList ist langsam ( O(N) ).

Eine Liste unveränderlich machen

Die Collections-Klasse bietet eine Möglichkeit, eine Liste unveränderbar zu machen:

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

Wenn Sie eine unveränderbare Liste mit einem Element wünschen, können Sie Folgendes verwenden:

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

Objekte in der Liste verschieben

Mit der Collections-Klasse können Sie Objekte in der Liste mit verschiedenen Methoden verschieben (ls ist die Liste):

Liste umkehren:

Collections.reverse(ls);

Rotierende Positionen von Elementen in einer Liste

Die Rotationsmethode erfordert ein ganzzahliges Argument. Dies ist, wie viele Punkte Sie entlang der Linie verschieben müssen. Ein Beispiel dafür ist unten:

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

Dies wird gedruckt "Hallo, wie geht es dir?"

Elemente in einer Liste mischen

Mit der gleichen Liste oben können wir die Elemente in einer Liste mischen:

Collections.shuffle(ls);

Wir können ihm auch ein java.util.Random-Objekt geben, mit dem Objekte zufällig in Spots platziert werden:

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

Klassen zur Implementierung von List - Vor- und Nachteile

Die List Schnittstelle wird von verschiedenen Klassen implementiert. Jeder von ihnen hat seinen eigenen Weg, um ihn mit unterschiedlichen Strategien umzusetzen und verschiedene Vor- und Nachteile zu bieten.


Klassen, die List implementieren

Dies sind alle public Klassen in Java SE 8, die die Schnittstelle java.util.List implementieren:

  1. Abstrakte Klassen:
    • AbstractList
    • AbstractSequentialList
  2. Konkrete Klassen:
    • Anordnungsliste
    • Attributliste
    • CopyOnWriteArrayList
    • LinkedList
    • Rollenliste
    • RoleUnresolvedList
    • Stapel
    • Vektor

Vor- und Nachteile jeder Implementierung im Hinblick auf die Komplexität der Zeit

Anordnungsliste

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

ArrayList ist eine anpassbare Array-Implementierung der List-Schnittstelle. Wenn Sie die Liste in einem Array speichern, bietet ArrayList (zusätzlich zu den Methoden, die die List- Schnittstelle implementieren) Methoden zum Ändern der Größe des Arrays.

Initialisieren Sie ArrayList of Integer mit der Größe 100

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

- PROS:

Die Operationen size, isEmpty, get , set , iterator und listIterator werden in konstanter Zeit ausgeführt. Das Erhalten und Einstellen jedes Elements der Liste hat also die gleichen Zeitkosten :

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

- CONS:

Die Implementierung mit einem Array (statische Struktur) für das Hinzufügen von Elementen über die Größe des Arrays hinaus ist mit hohen Kosten verbunden, da für das gesamte Array eine neue Zuordnung vorgenommen werden muss. Jedoch aus der Dokumentation :

Die Hinzufügungsoperation wird in einer amortisierten konstanten Zeit ausgeführt, das heißt, das Hinzufügen von n Elementen erfordert O (n) Zeit

Das Entfernen eines Elements erfordert O (n) Zeit.


Attributliste

Auf kommen


CopyOnWriteArrayList

Auf kommen


LinkedList

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

LinkedList wird durch eine doppelt verknüpfte Liste implementiert, eine verknüpfte Datenstruktur, die aus einem Satz sequentiell verknüpfter Datensätze besteht, die als Knoten bezeichnet werden.

Initialisieren Sie LinkedList of Integer

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

- PROS:

Das Hinzufügen oder Entfernen eines Elements vor oder nach dem Ende der Liste hat eine konstante Zeit.

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

- CONS: Aus der Dokumentation :

Operationen, die in die Liste aufgenommen werden, durchlaufen die Liste vom Anfang oder vom Ende, je nachdem, welcher Punkt näher am angegebenen Index liegt.

Operationen wie:

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

Rollenliste

Auf kommen


RoleUnresolvedList

Auf kommen


Stapel

Auf kommen


Vektor

Auf kommen




Modified text is an extract of the original Stack Overflow Documentation
Lizenziert unter CC BY-SA 3.0
Nicht angeschlossen an Stack Overflow