Java Language
Списки

Вступление

Синтаксис

• ls.add (элемент E); // Добавляет элемент
• ls.remove (элемент E); // Удаляет элемент
• for (элемент E: ls) {} // Итерации по каждому элементу
• ls.toArray (новая строка [ls.length]); // Преобразует список строк в массив строк
• ls.get (индекс int); // Возвращает элемент по указанному индексу.
• ls.set (индекс int, элемент E); // Заменяет элемент в указанной позиции.
• ls.isEmpty (); // Возвращает true, если массив не содержит элементов, иначе он возвращает false.
• ls.indexOf (Object o); // Возвращает индекс первого местоположения указанного элемента o или, если его нет, возвращает -1.
• ls.lastIndexOf (Object o); // Возвращает индекс последнего местоположения указанного элемента o или, если его нет, возвращает -1.
• ls.size (); // Возвращает количество элементов в Списке.

замечания

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"

Сортировка общего списка

Класс Collections предлагает два стандартных статических метода для сортировки списка:

• sort(List<T> list) применимый к спискам, где T extends Comparable<? super T> , и
• sort(List<T> list, Comparator<? super T> c) применимый к спискам любого типа.

Применение первого требует внесения изменений в класс сортируемых элементов списка, что не всегда возможно. Это также может быть нежелательным, поскольку, несмотря на то, что он обеспечивает сортировку по умолчанию, другие заказы сортировки могут потребоваться в разных обстоятельствах, или сортировка - это просто одна задача.

У нас есть задача сортировки объектов, которые являются экземплярами следующего класса:

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

Чтобы использовать Collections.sort(List<User> list) нам необходимо изменить класс User для реализации интерфейса Comparable . Например

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

( За исключением: многие стандартные классы Java , такие как String , Long , Integer реализовать Comparable интерфейс Это делает списки тех элементов , отсортированных по умолчанию, и упрощает реализацию. compare или compareTo в других классах.)

В приведенной выше модификации мы можем легко отсортировать список объектов User на основе естественного упорядочения классов. (В этом случае мы определили, что это упорядочение на основе значений id ). Например:

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]

Однако предположим, что мы хотели отсортировать объекты User по name а не по id . В качестве альтернативы предположим, что мы не смогли изменить класс, чтобы он реализовал Comparable .

Здесь метод sort с аргументом 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))

Создание списка

Предоставление вашего списка типа

Для создания списка вам нужен тип (любой класс, например String ). Это тип вашего List . List будет хранить объекты только указанного типа. Например:

List<String> strings;

Может хранить "string1" , "hello world!" , "goodbye" и т. д., но он не может хранить 9.2 , однако:

List<Double> doubles;

Может хранить 9.2 , но не "hello world!" ,

Инициализация вашего списка

Если вы попытаетесь добавить что-то в список выше, вы получите исключение NullPointerException, потому что strings и doubles равные нулю !

Существует два способа инициализации списка:

Вариант 1: используйте класс, который реализует List

List - это интерфейс, который означает, что у него нет конструктора, а скорее методов, которые класс должен переопределить. ArrayList является наиболее часто используемым List , хотя LinkedList также распространен. Итак, мы инициализируем наш список следующим образом:

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

или же

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

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

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

Вариант 2: используйте класс Collections

Класс Collections предоставляет два полезных метода для создания списков без переменной List :

• emptyList() : возвращает пустой список.
• singletonList(T) : создает список типов T и добавляет указанный элемент.

И метод, который использует существующий List для заполнения данных в:

• addAll(L, T...) : добавляет все указанные элементы в список, переданный в качестве первого параметра.

Примеры:

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

Операции с позиционным доступом

API-интерфейс списка содержит восемь методов для операций позиционного доступа:

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

Итак, если у нас есть Список:

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

И мы хотели добавить строки «Привет мир!». и "Прощай мир!" к этому мы будем делать это как таковое:

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

И наш список будет содержать два элемента. Теперь скажем, мы хотели добавить «Program start!». в начале списка. Мы сделали бы это следующим образом:

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

ПРИМЕЧАНИЕ. Первый элемент равен 0.

Теперь, если мы хотим удалить «До свидания мир!» мы можем сделать это следующим образом:

strings.remove("Goodbye world!");

И если бы мы хотели удалить первую строку (которая в этом случае была бы «Program start!», Мы могли бы сделать это следующим образом:

strings.remove(0);

Замечания:

1. Добавление и удаление элементов списка изменяет список, и это может привести к исключению ConcurrentModificationException если список повторяется одновременно.

2. Добавление и удаление элементов может быть O(1) или O(N) зависимости от класса списка, используемого метода и того, добавляете / удаляете элемент в начале, в конце или в середине списка.

Чтобы получить элемент списка в указанной позиции, вы можете использовать E get(int index); метод API-интерфейса списка. Например:

strings.get(0);

вернет первый элемент списка.

Вы можете заменить любой элемент в указанной позиции, используя set(int index, E element); , Например:

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

Это установит строку «Это замена» в качестве первого элемента списка.

Примечание. Метод установки перезапишет элемент в позиции 0. Он не добавит новую строку в позицию 0 и перетащит старую в позицию 1.

int indexOf(Object o); возвращает позицию первого вхождения объекта, переданного в качестве аргумента. Если в списке нет вхождений объекта, тогда возвращается значение -1. В продолжение предыдущего примера, если вы вызываете:

strings.indexOf("This is a replacement")

ожидается, что 0 будет возвращено, поскольку мы устанавливаем строку «Это замена» в позиции 0 нашего списка. В случае, если в списке имеется более одного вхождения, когда int indexOf(Object o); называется, то, как упоминалось, будет возвращен индекс первого вхождения. int lastIndexOf(Object o) вы можете получить индекс последнего вхождения в списке. Поэтому, если добавить еще одну «Это замена»:

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

На этот раз 1 будет возвращен, а не 0;

Итерирование элементов в списке

Например, скажем, что у нас есть List of type String, который содержит четыре элемента: «hello», «how», «are», «you?»?

Лучший способ перебора каждого элемента - использовать для каждого цикла:

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

Что бы напечатать:

hello,
how
are
you?

Чтобы распечатать их все в одной строке, вы можете использовать StringBuilder:

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

Будет печать:

hello, how are you?

Кроме того, вы можете использовать индексацию элементов (как описано в разделе «Доступ к элементу в i-м индексе от ArrayList» ), чтобы перебрать список. Предупреждение: этот подход неэффективен для связанных списков.

Удаление элементов из списка B, которые присутствуют в списке A

Давайте предположим , что у вас есть 2 Списки А и В, и вы хотите , чтобы удалить из B все элементы , которые вы имеете в А метод в данном случае является

 List.removeAll(Collection c);

#Пример:

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

это напечатает

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

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

B: [13, 32, 533]

Поиск общих элементов между двумя списками

Предположим, у вас есть два списка: A и B, и вам нужно найти элементы, которые существуют в обоих списках.

Вы можете сделать это, просто вызвав метод List.retainAll() .

Пример:

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

}

Преобразование списка целых чисел в список строк

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

То есть:

1. Создайте поток из списка
2. Сопоставьте каждый элемент с помощью Object::toString
3. Соберите значения String в List с помощью Collectors.toList()

Создание, добавление и удаление элемента из массива ArrayList

ArrayList является одной из встроенных структур данных в Java. Это динамический массив (где размер структуры данных, который не требуется сначала объявлять) для хранения элементов (объектов).

Он расширяет класс AbstractList и реализует интерфейс List . ArrayList может содержать повторяющиеся элементы, где он поддерживает порядок вставки. Следует отметить, что класс ArrayList не синхронизирован, поэтому следует проявлять осторожность при работе с параллелизмом с ArrayList . ArrayList допускает произвольный доступ, потому что массив работает на основе индекса. Манипуляция медленнее в ArrayList из-за изменения, которое часто возникает, когда элемент удаляется из списка массивов.

ArrayList может быть создан следующим образом:

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

Где T ( Generics ) - это тип, который будет храниться внутри ArrayList .

Тип ArrayList может быть любым объектом. Тип не может быть примитивным типом (вместо этого используйте их классы-оболочки ).

Чтобы добавить элемент в ArrayList , используйте метод add() :

myArrayList.add(element);

Или добавить элемент к определенному индексу:

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

Чтобы удалить элемент из ArrayList , используйте метод remove() :

myArrayList.remove(element);

Или удалить элемент из определенного индекса:

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

Замена на месте элемента списка

Этот пример касается замены элемента List , гарантируя, что элемент замены находится в том же положении, что и заменяемый элемент.

Это можно сделать, используя следующие методы:

• set (индекс int, тип T)
• int indexOf (тип T)

Рассмотрим ArrayList содержащий элементы «Начало программы!», «Привет, мир!». и "Прощай мир!"

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

Если нам известен индекс элемента, который мы хотим заменить, мы можем просто использовать set следующим образом:

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

Если мы не знаем индекс, мы можем сначала его найти. Например:

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

Заметки:

1. Операция set не вызовет ConcurrentModificationException .
2. Операция set выполняется быстро ( O(1) ) для ArrayList но медленная ( O(N) ) для LinkedList .
3. Поиск indexOf в ArrayList или LinkedList медленный ( O(N) ).

Создание списка не подлежащих регистрации

Класс Collections позволяет сделать список немодифицируемым:

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

Если вам нужен немодифицируемый список с одним элементом, который вы можете использовать:

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

Перемещение объектов в списке

Класс Collections позволяет перемещать объекты в списке с помощью различных методов (ls - это List):

Перемещение списка:

Collections.reverse(ls);

Поворот позиций элементов в списке

Для метода rotate требуется целочисленный аргумент. Это то, сколько мест перемещать по линии. Ниже приведен пример:

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

Это будет печатать «привет, как дела?»

Перемешивание элементов в списке

Используя тот же список выше, мы можем перетасовать элементы в списке:

Collections.shuffle(ls);

Мы также можем дать ему объект java.util.Random, который он использует для случайного размещения объектов в точках:

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

Классы, реализующие список - за и против

Интерфейс List реализуется различными классами. Каждый из них имеет свой собственный путь для реализации этого с различными стратегиями и предоставления различных плюсов и минусов.

Классы, реализующие List

Это все public классы в Java SE 8, которые реализуют интерфейс java.util.List :

1. Абстрактные классы:
   • AbstractList
   • AbstractSequentialList
2. Бетонные классы:
   • ArrayList
   • AttributeList
   • CopyOnWriteArrayList
   • LinkedList
   • RoleList
   • RoleUnresolvedList
   • стек
   • Вектор

Плюсы и минусы каждой реализации с точки зрения временной сложности

ArrayList

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

ArrayList - это реализация интерфейса списка с изменяемым размером. Сохраняя список в массив, ArrayList предоставляет методы (в дополнение к методам, реализующим интерфейс List ) для управления размером массива.

Инициализировать ArrayList из Integer с размером 100

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

- PROS:

Операции size, isEmpty, get , set , iterator и listIterator выполняются в постоянное время. Таким образом, получение и установка каждого элемента списка имеют одинаковую стоимость :

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

- CONS:

При реализации с массивом (статическая структура) добавление элементов по размеру массива имеет большую стоимость из-за того, что для всего массива необходимо выполнить новое распределение. Однако из документации :

Операция add выполняется в режиме амортизированного постоянного времени, то есть добавление n элементов требует O (n) времени

Для удаления элемента требуется время O (n).

AttributeList

Прибытие

CopyOnWriteArrayList

Прибытие

LinkedList

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

LinkedList реализуется двусвязным списком связанной структуры данных, которая состоит из набора последовательно связанных записей, называемых узлами.

Iitialize LinkedList из Integer

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

- PROS:

Добавление или удаление элемента в начале списка или до конца имеет постоянное время.

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

- CONS: Из документации :

Операции, которые индексируются в список, будут перемещаться по списку от начала или до конца, в зависимости от того, что ближе к указанному индексу.

Операции, такие как:

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

RoleList

Прибытие

RoleUnresolvedList

Прибытие

стек

Прибытие

Вектор

Прибытие