Реализуйте различные структуры данных с помощью Java

Коллекции используются на всех языках программирования. Это объекты, которые объединяют несколько элементов в единое целое. До использования фреймворка Коллекции программистам было сложно писать алгоритмы, которые работали бы для разных типов коллекций. В Java были некоторые классы Collection, такие как Vector, Stack, Hashtable и Array, но у них были свои недостатки.

В JDK 1.2 разработчики Java представили платформу Collections, которая является важной средой, помогающей выполнять все операции с данными. Сегодня мы более подробно рассмотрим этот фреймворк и некоторые его компоненты.

Вот что мы рассмотрим сегодня:

  • Что такое коллекции Java?
  • ArrayList в Java
  • LinkedList в Java
  • HashSet в Java
  • TreeSet в Java
  • Другие коллекции для изучения

Что такое коллекции Java?

Согласно документации, среда Java Collections - это унифицированная архитектура для представления коллекций и управления ими. Он содержит интерфейсы, классы их реализации и алгоритмы для обработки данных, хранящихся в коллекции. Интерфейс Collection расширен другими интерфейсами, такими как List, Set и Queue.

Примечание. Существует также Map интерфейс, но он не реализует Collection интерфейс, поскольку хранит пары ключ-значение, а классы, входящие в интерфейс Collection, хранят только значения.

Различия между платформой коллекций и коллекциями

  • Фреймворк коллекций - это интерфейс, а Collections - это класс.
  • Интерфейс Collection предоставляет стандартные функции структур данных для List, Set и Queue. Класс Collections предоставляет стандартные методы, которые можно использовать для поиска, сортировки и координации элементов коллекции.
  • Collections - это объекты, которые представляют группу объектов (например, Vector), а структура коллекций может представлять коллекции и управлять ими.

Компоненты Java Collections Framework

Интерфейсы

Эти интерфейсы предоставляют абстрактный тип данных для представления коллекции. java.util.Collection - это корневой интерфейс фреймворка. Он находится на вершине иерархии фреймворка и содержит важные методы, такие как size(), iterator(), add(), remove() и clear().

Интерфейс Iterable - это корень всей структуры коллекции. Это позволяет итератору перебирать все коллекции. Все классы и интерфейсы используют этот интерфейс. Интерфейс Collection расширяет итеративный интерфейс и выполняется классами в структуре коллекции. Интерфейс List запрещает структуру данных типа списка, в которой мы можем хранить упорядоченные коллекции объектов.

Некоторые более важные интерфейсы включают в себя:

  • Map интерфейс: java.util.Map
  • Set интерфейс: java.util.Set
  • Deque интерфейс: java.util.Deque

Примечание. Map - единственный интерфейс, который не наследуется от интерфейса Collection, но включен в структуру коллекций. Все интерфейсы фреймворка находятся в пакете java.util.

Классы реализации

Фреймворк предоставляет классы реализации для коллекций. Вы можете использовать их для создания различных типов коллекций в ваших программах Java. Некоторые из основных классов коллекций включают:

  • ArrayList
  • LinkedList
  • PriorityQueue
  • HashMap и HashSet
  • TreeMap и TreeSet

Алгоритмы

Эти алгоритмы выполняют важные функции с коллекциями, например списки сортировки.

Иерархия фреймворка Collections выглядит следующим образом:

ArrayList в Java

ArrayList - наиболее часто используемая реализация интерфейса List. Некоторые из его функций включают:

  • Сохраняет элементы в порядке вставки.
  • Позволяет хранить повторяющиеся элементы.
  • Поддерживает null элементов.

ArrayList хранит данные в массиве с изменяемым размером. Когда вы создаете ArrayList, вы создаете массив нулевого размера. Когда вставляется первый элемент, размер массива изменяется до десяти. Это известно как отложенная инициализация, и при этом сохраняется много памяти. Перед добавлением элемента в ArrayList проверяется емкость. Если массив заполнен, создается новый массив размером (n + n / 2 + 1). Затем элементы из старого массива копируются в новый.

Создать ArrayList в Java можно тремя способами:

  1. Конструктор no-arg - этот конструктор не принимает никаких аргументов и создает нулевой размер списка.
List list = newArrayList();

2. Конструктор, который принимает начальную емкость - вы можете указать начальную емкость при создании ArrayList. Допустим, вы знаете, что ваш ArrayList будет содержать не менее 50 элементов. Вы можете создать свой ArrayList размером 50, уменьшив необходимость постоянного изменения размера.

List list = newArrayList(50);

3. Существующий Collection - вы можете создать ArrayList, используя существующий Collection, и список будет содержать все элементы исходного Collection в том же порядке.

List list = newArrayList(oldList);

Вот пример ArrayList, который можно выполнить на Java:

Выход:

[1, 2, 3]
The element at index two is 2
The size of the List is 3

С ArrayList можно делать много вещей, в том числе:

  • Обновите элемент, используя метод set(int index, E e).
  • Проверьте, присутствует ли элемент, используя метод contains(Object o).
  • Удалите все элементы в пределах заданного Collection, используя метод removeAll(Collection<?> c).
  • Замените все элементы, используя replaceAll(UnaryOperator<E> operator).
  • И т.п.

LinkedList в Java

Класс LinkedList реализует интерфейсы List и Deque. Некоторые из его функций включают:

  • Сохраняет элементы в порядке вставки.
  • Поддерживает повторяющиеся элементы.
  • Допускает любое количество null элементов.

LinkedList также имеет статический внутренний класс Node, который содержит три поля:

  1. item - содержит значение текущего элемента
  2. next - содержит указатель на следующий элемент
  3. prev - содержит указатель на предыдущий элемент

Когда элемент добавляется в LinkedList, он создает новый экземпляр Node. Поля prev и next устанавливаются в зависимости от того, где добавлен новый узел.

Есть два способа создать LinkedList на Java:

  1. Конструктор no-arg - этот конструктор не принимает никаких аргументов и создает список с нулевым размером.
List<Integer> list = new LinkedList<Integer>();

2. Существующий Collection - вы можете создать LinkedList, используя существующий Collection, и список будет содержать все элементы исходного Collection в том же порядке.

List<Integer> list = new LinkedList<Integer>(oldList);

Вот пример LinkedList, который можно выполнить на Java:

Выход:

[1, 2, 3]
[10, 1, 2, 3]
[10, 1, 20, 2, 3]
[10, 1, 20, 101, 102, 103, 2, 3]

Еще несколько вещей, которые вы можете сделать с LinkedList:

  • Получить элемент по определенному индексу с помощью метода get(int index).
  • Удалите последний элемент, используя метод removeLast().
  • Отсортируйте LinkedList, используя метод sort().
  • И т.п.

HashSet в Java

HashSet - это класс в java.util пакете, реализующий интерфейс Set. Некоторые особенности HashSet включают:

  • Не допускает дублирования элементов.
  • Допускается только один null элемент.
  • Элементы вставляются в случайном порядке.
  • Внутренняя поддержка HashMap.

Есть четыре способа создать HashSet в Java:

  1. Конструктор no-arg - создаст HashSet с начальной емкостью 16 и коэффициентом загрузки 0,75.
Set<Integer> set = new HashSet<>();

2. Конструктор, который принимает начальную емкость. Если вы знаете, что ваш HashSet будет иметь более 16 элементов, вы можете установить более высокую начальную емкость, чтобы уменьшить необходимость изменения размера. Он будет использовать коэффициент загрузки по умолчанию 0,75.

3. Конструктор, который принимает начальную емкость и коэффициент нагрузки. Вы также можете указать начальный коэффициент нагрузки вместе с начальной емкостью.

4. Конструктор, который принимает другой Set в качестве параметра. Вы можете создать HashSet, используя другой Set, передав его конструктору. Он будет иметь тот же размер, что и переданный набор, и коэффициент загрузки по умолчанию 0,75.

Вот пример HashSet, который можно выполнить на Java:

Выход:

Inserting 17 in the HashSet: true
Inserting 34 in the HashSet: true
Inserting 17 in the HashSet: false
[17, 34]

В приведенном выше коде показана демонстрация метода add(E e), который вставляет элемент в HashSet. Если вставленного элемента еще не было в HashSet, метод вернул true. Если элемент уже был в HashSet, метод вернул false.

С HashSets вы можете делать больше, например:

  • Удалите элементы с помощью метода remove(Object o).
  • Проверьте, пуст ли HashSet, используя метод isEmpty().
  • Получить элемент из HashSet с помощью метода contains().
  • И т.п.

TreeSet в Java

Класс TreeSet реализует интерфейс Set, который использует дерево для хранения. Некоторые из функций включают:

  • Не допускает дублирования элементов.
  • Не допускает null элементов.
  • Быстрый доступ и время поиска.
  • Элементы хранятся в порядке возрастания.

Иерархия TreeSet выглядит следующим образом:

Чем TreeSet отличается от HashSet?

• HashSet допускает один нулевой элемент, а TreeSet не допускает никаких.

• Элементы сортируются случайным образом в HashSet, а в TreeSet они сортируются по порядку.

• HashSet быстрее для таких операций, как add, remove, contains, size и т. Д.

Есть четыре способа создать TreeSet в Java:

  1. Конструктор no-arg.
Set<Integer> set = new TreeSet<>();

2. Конструктор с Comparator в качестве аргумента. Если объекты, которые вы храните в своем TreeSet, не реализуют Comparator интерфейс или если вам нужно хранить элементы в порядке убывания, вы можете указать собственный Comparator при создании TreeSet. Это отсортирует элементы в соответствии с логикой Comparator.

3. Конструктор с аргументом типа Collection - вы можете создать TreeSet из другого Collection. Элементы будут храниться в порядке возрастания.

4. Конструктор с аргументом типа SortedSet - этот конструктор действует как конструктор копирования и создает новый отсортированный набор с теми же элементами и тем же порядком, что и предоставленный отсортированный набор.

Вот пример TreeSet, который можно выполнить на Java:

Выход:

TreeSet elements in ascending order [11, 21, 32, 44, 54]
TreeSet elements in descending order [54, 44, 32, 21, 11]

С TreeSet можно делать и другие вещи, например:

  • Получить элементы, превышающие данный элемент, используя метод tailSet(E fromElement).
  • Получите подмножество элементов с помощью метода subSet(E fromElement, E to Element).
  • И т.п.

Другие коллекции для изучения

Поздравляем с вашими первыми шагами в работе с фреймворком Java Collections! Collection - одна из самых важных тем в программировании на Java, и эта важная структура поможет вам выполнять все ваши операции с данными.

Теперь вы готовы глубже погрузиться в структуру Java Collections и узнать больше о таких темах, как:

  • LinkedHashMap и LinkedHashSet
  • SortedMap и SortedSet
  • toArray()
  • hasNext()
  • И т.п.

Удачного обучения!