Java Language
Listy

Wprowadzenie

Składnia

• ls.add (element E); // Dodaje element
• ls.remove (element E); // Usuwa element
• for (element E: ls) {} // Iteruje po każdym elemencie
• ls.toArray (new String [ls.length]); // Konwertuje listę ciągów znaków na tablicę ciągów znaków
• ls.get (indeks wewnętrzny); // Zwraca element o określonym indeksie.
• ls.set (indeks wewnętrzny, element E); // Zastępuje element w określonej pozycji.
• ls.isEmpty (); // Zwraca true, jeśli tablica nie zawiera żadnych elementów, w przeciwnym razie zwraca false.
• ls.indexOf (Object o); // Zwraca indeks pierwszej lokalizacji określonego elementu o lub, jeśli nie jest obecny, zwraca -1.
• ls.lastIndexOf (Object o); // Zwraca indeks ostatniej lokalizacji określonego elementu o lub, jeśli nie jest obecny, zwraca -1.
• ls.size (); // Zwraca liczbę elementów na liście.

Uwagi

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"

Sortowanie ogólnej listy

Klasa Collections oferuje dwie standardowe metody statyczne do sortowania listy:

• sort(List<T> list) dotyczy list, na których T extends Comparable<? super T> i
• sort(List<T> list, Comparator<? super T> c) dotyczy list dowolnego typu.

Zastosowanie tego pierwszego wymaga zmiany klasy sortowanych elementów listy, co nie zawsze jest możliwe. Może to być również niepożądane, ponieważ chociaż zapewnia domyślne sortowanie, inne porządki sortowania mogą być wymagane w różnych okolicznościach lub sortowanie jest jednorazowym zadaniem.

Rozważmy, że mamy zadanie sortowania obiektów, które są instancjami następującej klasy:

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

Aby korzystać z Collections.sort(List<User> list) , musimy zmodyfikować klasę User aby wdrożyć interfejs Comparable . Na przykład

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

(Na marginesie: wiele standardowych klas Javy takie jak String , Long , Integer wdrożyć Comparable interfejs To sprawia, że wykazy tych elementów sortable domyślnie i upraszcza wdrażanie. compare lub compareTo w innych klasach).

Dzięki powyższej modyfikacji możemy łatwo sortować listę obiektów User na podstawie naturalnego uporządkowania klas. (W tym przypadku zdefiniowaliśmy, że będzie to porządek oparty na wartościach id ). Na przykład:

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]

Załóżmy jednak, że chcieliśmy sortować obiekty User według name a nie id . Ewentualnie załóżmy, że nie byliśmy w stanie zmienić klasy, aby uczynić ją implementacją Comparable .

W tym przypadku przydatna jest metoda sort z argumentem Comparator :

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

Tworzenie listy

Podanie typu listy

Do utworzenia listy potrzebny jest typ (dowolna klasa, np. String ). To jest typ twojej List . List będzie przechowywać tylko obiekty określonego typu. Na przykład:

List<String> strings;

Może przechowywać "string1" , "hello world!" , "goodbye" itp., ale nie można zapisać wersji 9.2 , jednak:

List<Double> doubles;

Może przechowywać 9.2 , ale nie "hello world!" .

Inicjalizacja listy

Jeśli spróbujesz dodać coś do powyższych list, otrzymasz NullPointerException, ponieważ zarówno strings i doubles są równe null !

Istnieją dwa sposoby inicjowania listy:

Opcja 1: Użyj klasy, która implementuje listę

List jest interfejsem, co oznacza, że nie ma konstruktora, a raczej metody, które klasa musi zastąpić. ArrayList jest najczęściej używaną List , choć LinkedList jest również powszechna. Inicjujemy naszą listę w następujący sposób:

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

lub

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

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

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

Opcja 2: użyj klasy Kolekcje

Klasa Collections zapewnia dwie przydatne metody tworzenia list bez zmiennej List :

• emptyList() : zwraca pustą listę.
• singletonList(T) : tworzy listę typu T i dodaje określony element.

I metoda wykorzystująca istniejącą List do wypełnienia danych:

• addAll(L, T...) : dodaje wszystkie określone elementy do listy przekazanej jako pierwszy parametr.

Przykłady:

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

Pozycyjne operacje dostępu

Interfejs API listy ma osiem metod operacji dostępu pozycyjnego:

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

Więc jeśli mamy listę:

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

I chcieliśmy dodać ciąg „Hello world!” i „Do widzenia świat!” zrobilibyśmy to w ten sposób:

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

Nasza lista zawierałaby dwa elementy. Powiedzmy teraz, że chcieliśmy dodać „Uruchamianie programu!” na początku listy. Zrobilibyśmy to w ten sposób:

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

UWAGA: Pierwszym elementem jest 0.

Teraz, jeśli chcielibyśmy usunąć „Świat do widzenia!” linia, możemy to zrobić w następujący sposób:

strings.remove("Goodbye world!");

A jeśli chcielibyśmy usunąć pierwszy wiersz (który w tym przypadku byłby „Program startujący!”, Moglibyśmy to zrobić w następujący sposób:

strings.remove(0);

Uwaga:

1. Dodanie i usunięcie elementów listy modyfikuje listę, a to może prowadzić do ConcurrentModificationException jeśli lista jest iterowana jednocześnie.

2. Dodawanie i usuwanie elementów może być O(1) lub O(N) zależności od klasy listy, zastosowanej metody oraz tego, czy dodajesz / usuwasz element na początku, na końcu czy na środku listy.

Aby pobrać element listy z określonej pozycji, możesz użyć E get(int index); metoda interfejsu API listy. Na przykład:

strings.get(0);

zwróci pierwszy element listy.

Możesz zastąpić dowolny element w określonej pozycji za pomocą set(int index, E element); . Na przykład:

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

Spowoduje to ustawienie ciągu „To zamiennik” jako pierwszego elementu listy.

Uwaga: Ustawiona metoda nadpisze element w pozycji 0. Nie doda nowego łańcucha w pozycji 0 i nie popchnie starego do pozycji 1.

The int indexOf(Object o); zwraca pozycję pierwszego wystąpienia obiektu przekazanego jako argument. Jeśli na liście nie ma żadnych obiektów, zwracana jest wartość -1. Kontynuując poprzedni przykład, jeśli zadzwonisz:

strings.indexOf("This is a replacement")

Oczekuje się, że wartość 0 zostanie zwrócona, ponieważ ustawiamy ciąg „To jest zamiennik” na pozycji 0 naszej listy. W przypadku, gdy na liście występuje więcej niż jedno wystąpienie, gdy int indexOf(Object o); nazywa się wtedy, jak wspomniano, indeks pierwszego wystąpienia zostanie zwrócony. Przez wywołanie int lastIndexOf(Object o) możesz pobrać indeks ostatniego wystąpienia na liście. Więc jeśli dodamy kolejne „To jest zamiennik”:

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

Tym razem 1 zostanie zwrócone, a nie 0;

Iterowanie po elementach na liście

Na przykład załóżmy, że mamy Listę typu String, która zawiera cztery elementy: „hello”, „how”, „are”, „you?”

Najlepszym sposobem na iterację każdego elementu jest użycie pętli dla każdego:

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

Które wydrukuje:

hello,
how
are
you?

Aby wydrukować je wszystkie w tym samym wierszu, możesz użyć StringBuilder:

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

Wydrukuje:

hello, how are you?

Alternatywnie można użyć indeksowania elementów (zgodnie z opisem w temacie Uzyskiwanie dostępu do elementu i-tego indeksu z ArrayList ) w celu iteracji listy. Ostrzeżenie: takie podejście jest nieskuteczne w przypadku list połączonych.

Usuwanie elementów z listy B, które są obecne na liście A

Załóżmy, że masz 2 listy A i B i chcesz usunąć z B wszystkie elementy, które masz w A , w tym przypadku metodą jest

 List.removeAll(Collection c);

#Przykład:

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

to zostanie wydrukowane

Odp .: [1, 3, 4, 7, 5, 2]

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

B rozliczone: [13, 32, 533]

Znajdowanie wspólnych elementów między 2 listami

Załóżmy, że masz dwie listy: A i B i musisz znaleźć elementy, które istnieją na obu listach.

Możesz to zrobić, po prostu wywołując metodę List.retainAll() .

Przykład:

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

}

Konwertuj listę liczb całkowitych na listę ciągów znaków

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

To jest:

1. Utwórz strumień z listy
2. Odwzoruj każdy element za pomocą Object::toString
3. Zbierz wartości String do List za pomocą Collectors.toList()

Tworzenie, dodawanie i usuwanie elementu z ArrayList

ArrayList jest jedną z wbudowanych struktur danych w Javie. Jest to tablica dynamiczna (w której wielkość struktury danych nie musi być deklarowana jako pierwsza) do przechowywania elementów (obiektów).

Rozszerza klasę AbstractList i implementuje interfejs List . ArrayList może zawierać zduplikowane elementy, w których zachowuje porządek wstawiania. Należy zauważyć, że klasa ArrayList nie jest zsynchronizowana, dlatego należy zachować ostrożność podczas obsługi współbieżności z ArrayList . ArrayList umożliwia losowy dostęp, ponieważ tablica działa na podstawie indeksu. Manipulacja jest powolna w ArrayList powodu przesunięcia, które często występuje, gdy element jest usuwany z listy tablic.

ArrayList można utworzyć w następujący sposób:

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

Gdzie T ( Generics ) to typ, który będzie przechowywany w ArrayList .

Typ ArrayList może być dowolnym obiektem. Typ nie może być typem pierwotnym (zamiast tego użyj ich klas opakowań ).

Aby dodać element do ArrayList , użyj metody add() :

myArrayList.add(element);

Lub dodać element do określonego indeksu:

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

Aby usunąć element z ArrayList , użyj metody remove() :

myArrayList.remove(element);

Lub usunąć element z określonego indeksu:

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

Zastąpienie w miejscu elementu List

Ten przykład dotyczy zastąpienia elementu List , zapewniając jednocześnie, że element zastępujący znajduje się w tej samej pozycji co element, który jest zastępowany.

Można to zrobić za pomocą następujących metod:

• zestaw (indeks wewnętrzny, typ T)
• int indexOf (typ T)

Rozważ ArrayList zawierającą elementy „Program start!”, „Hello world!” i „Do widzenia świat!”

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

Jeśli znamy indeks elementu, który chcemy zastąpić, możemy po prostu użyć set w następujący sposób:

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

Jeśli nie znamy indeksu, możemy go najpierw wyszukać. Na przykład:

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

Uwagi:

1. set operacja nie spowoduje ConcurrentModificationException .
2. Operacja set jest szybka ( O(1) ) dla ArrayList ale powolna ( O(N) ) dla LinkedList .
3. Wyszukiwanie indexOf na ArrayList lub LinkedList jest powolne ( O(N) ).

Uczynić listę niemodyfikowalną

Klasa Kolekcje zapewnia sposób, aby lista była niemodyfikowalna:

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

Jeśli chcesz mieć niemodyfikowalną listę z jednym przedmiotem, możesz użyć:

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

Przenoszenie obiektów na liście

Klasa Kolekcje pozwala przenosić obiekty na liście przy użyciu różnych metod (ls to Lista):

Odwracanie listy:

Collections.reverse(ls);

Obracanie pozycji elementów na liście

Metoda obracania wymaga argumentu całkowitego. To o ile miejsc należy przesunąć go wzdłuż linii. Przykład tego znajduje się poniżej:

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

Spowoduje to wydrukowanie „cześć, jak się masz?”

Tasowanie elementów na liście

Korzystając z tej samej listy powyżej, możemy tasować elementy na liście:

Collections.shuffle(ls);

Możemy również nadać mu obiekt java.util.Random, którego używa do losowego umieszczania obiektów w miejscach:

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

Klasy wdrażające listę - zalety i wady

Interfejs List jest implementowany przez różne klasy. Każdy z nich ma swój własny sposób na wdrożenie go z różnymi strategiami i zapewnienie różnych zalet i wad.

Klasy wdrażające listę

Są to wszystkie klasy public w Javie SE 8, które implementują interfejs java.util.List :

1. Klasy abstrakcyjne:
   • AbstractList
   • AbstractSequentialList
2. Klasy betonowe:
   • ArrayList
   • AttributeList
   • CopyOnWriteArrayList
   • Połączona lista
   • RoleList
   • RoleUnresolvedList
   • Stos
   • Wektor

Plusy i minusy każdego wdrożenia pod względem złożoności czasowej

ArrayList

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

ArrayList jest implementacją tablicy List o zmiennym rozmiarze. Przechowując listę w tablicy, ArrayList udostępnia metody (oprócz metod implementujących interfejs List ) do manipulowania rozmiarem tablicy.

Zainicjuj ArrayList of Integer o rozmiarze 100

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

- Wady:

Operacje size, isEmpty, get , set , iterator i listIterator działają w stałym czasie. Tak więc uzyskanie i ustawienie każdego elementu listy ma taki sam koszt czasu :

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

- CONS:

Wdrożenie za pomocą tablicy (struktura statyczna) dodawania elementów ponad rozmiar tablicy ma duży koszt ze względu na fakt, że należy dokonać nowej alokacji dla całej tablicy. Jednak z dokumentacji :

Operacja dodawania działa w zamortyzowanym stałym czasie, to znaczy dodanie n elementów wymaga czasu O (n)

Usunięcie elementu wymaga czasu O (n).

AttributeList

Przyjedzie

CopyOnWriteArrayList

Przyjedzie

Połączona lista

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

LinkedList jest implementowany przez podwójnie połączoną listę połączoną strukturę danych, która składa się z zestawu kolejno powiązanych rekordów zwanych węzłami.

Iitialize LinkedList of Integer

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

- Wady:

Dodawanie lub usuwanie elementu na początku listy lub na końcu ma stały czas.

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

- CONS: Z dokumentacji :

Operacje, które indeksują listę, będą przechodzić przez listę od początku lub na końcu, w zależności od tego, który jest bliżej określonego indeksu.

Operacje takie jak:

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

RoleList

Przyjedzie

RoleUnresolvedList

Przyjedzie

Stos

Przyjedzie

Wektor

Przyjedzie