Структуры данных Java

Java предоставляет богатый набор структур данных для обработки и организации данных.

Пакет java.util в Java предоставляет реализации многих из этих структур данных, и вы можете выбрать подходящий класс по мере необходимости.

Ниже приведены некоторые распространённые структуры данных Java:

Массивы

Массивы — это базовая структура данных, которая может хранить коллекцию элементов одного типа фиксированного размера.

int[] array = new int[5];
  • Характеристики:Фиксированный размер, хранит элементы одного типа.
  • Преимущества:Эффективный произвольный доступ к элементам.
  • Недостатки:Фиксированный размер, вставка и удаление элементов сравнительно медленны.

Списки

Java предоставляет несколько реализаций списков, таких как ArrayList и LinkedList.

List<String> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

ArrayList:

  • Характеристики:Динамический массив, изменяемый размер.
  • Преимущества:Эффективный произвольный доступ и быстрая вставка в конец.
  • Недостатки:Вставка и удаление в середине сравнительно медленны.

LinkedList:

  • Характеристики:Двусвязный список, элементы соединены указателями.
  • Преимущества:Эффективная вставка и удаление элементов, хорошая производительность итератора.
  • Недостатки:Произвольный доступ сравнительно медленный.

Множества

Множества используются для хранения неповторяющихся элементов, а распространённые реализации включают HashSet и TreeSet.

Set<String> hashSet = new HashSet<>();
Set<Integer> treeSet = new TreeSet<>();

HashSet:

  • Характеристики:Неупорядоченная коллекция, реализованная на основе HashMap.
  • Преимущества:Эффективные операции поиска и вставки.
  • Недостатки:Не гарантирует порядок.

TreeSet:

  • Характеристики:TreeSet — упорядоченная коллекция, реализованная на основе красно-чёрного дерева на нижнем уровне, и не допускает дублирующихся элементов.
  • Преимущества:Обеспечивает автоматическую сортировку, подходит для сценариев, где элементы должны храниться в порядке.
  • Недостатки:Производительность относительно низкая, и вставка null-элементов не допускается.

Карты

Структуры Map используются для хранения пар «ключ-значение», а распространённые реализации включают HashMap и TreeMap.

Map<String, Integer> hashMap = new HashMap<>();
Map<String, Integer> treeMap = new TreeMap<>();

HashMap:

  • Характеристики:Структура хранения пар «ключ-значение», реализованная на основе хеш-таблицы.
  • Преимущества:Эффективные операции поиска, вставки и удаления.
  • Недостатки:Неупорядочен, порядок не гарантируется.

TreeMap:

  • Характеристики:Упорядоченная структура хранения пар «ключ-значение», реализованная на основе красно-чёрного дерева.
  • Преимущества:Упорядочен, поддерживает обход в порядке ключей.
  • Недостатки:Вставка и удаление выполняются относительно медленно.

Стек

Стек — это линейная структура данных, которая управляет элементами по принципу Last In, First Out (LIFO). В стеке новые элементы добавляются на вершину стека, и элементы можно удалять только с вершины стека. Это означает, что последний добавленный элемент удаляется первым.

Stack<Integer> stack = new Stack<>();

Класс Stack:

  • Характеристики:Представляет собой стек, обычно работающий с элементами по принципу «последним пришёл — первым вышел» (LIFO).

Очередь

Очереди следуют принципу «первым пришёл — первым вышел» (FIFO), а распространённые реализации включают LinkedList и PriorityQueue.

Queue<String> queue = new LinkedList<>();

Интерфейс Queue:

  • Характеристики:Представляет собой очередь, обычно работающую с элементами по принципу «первым пришёл — первым вышел» (FIFO).
  • Классы реализации: LinkedList, PriorityQueue, ArrayDeque.

Куча

Куча лежит в основе очереди с приоритетом и может реализовывать максимальную и минимальную кучу.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

Деревья

Java предоставляет тип TreeNode, который можно использовать для построения таких структур данных, как двоичные деревья.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Графы

Для представления графов обычно требуются собственные структуры данных или использование библиотек для работы с графами; в Java нет встроенного класса графа.

Выше перечислены лишь некоторые распространённые структуры данных в Java. Фактически существует множество других структур данных и алгоритмов, которые можно выбирать и использовать в зависимости от конкретных задач.

Прочие примечания

Следующие классы традиционно считаются устаревшими. В Java 2 был представлен новый фреймворк — Collection Framework, который мы обсудим позже.

Enumeration

Интерфейс Enumeration, хотя сам по себе не является структурой данных, широко используется в контексте других структур данных. Интерфейс Enumeration определяет способ извлечения последовательных элементов из структуры данных.

Например, Enumeration определяет метод nextElement, который используется для получения следующего элемента структуры данных, содержащей несколько элементов.

Для получения дополнительной информации об интерфейсе Enumeration,см. Enumeration。

BitSet

Класс BitSet реализует группу битов или флагов, которые можно устанавливать и сбрасывать по отдельности.

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

Для получения дополнительной информации об этом классе,см. BitSet。

Вектор

Класс Vector очень похож на традиционный массив, но размер Vector может динамически изменяться по мере необходимости.

Как и в массивах, к элементам объектов Vector также можно обращаться по индексу.

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

Для получения дополнительной информации об этом классе,см. Vector

Стек

Класс Stack реализует структуру данных «последним пришёл — первым вышел» (LIFO).

Стек можно представить как вертикально распределённый стек объектов. Когда вы добавляете новый элемент, вы помещаете его поверх других элементов.

Когда вы берёте элемент из стека, вы берёте его с вершины стека. Иными словами, элемент, который вошёл в стек последним, удаляется первым.

Для получения дополнительной информации об этом классе,см. Stack。

Словарь

Класс Dictionary — это абстрактный класс, который определяет структуру данных, сопоставляющую ключи значениям.

Когда вы хотите получить доступ к данным по определённому ключу, а не по целочисленному индексу, следует использовать Dictionary.

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

Для получения дополнительной информации об этом классе,см. Dictionary。

Класс Dictionary объявлен устаревшим в новых версиях Java. Рекомендуется использовать интерфейс Map и его классы реализации, такие как HashMap, TreeMap и т. д., вместо Dictionary.

Об интерфейсе Map и его классах реализации см.:Java Collections Framework。

Hashtable

Класс Hashtable предоставляет средство организации данных на основе определяемой пользователем структуры ключей.

Например, в хеш-таблице списка адресов можно хранить и сортировать данные по почтовому индексу в качестве ключа, а не по имени человека.

Конкретное значение ключа хеш-таблицы полностью зависит от сценария использования хеш-таблицы и содержащихся в ней данных.

Для получения дополнительной информации об этом классе,см. Hashtable。

Свойства

Properties наследуется от Hashtable. Класс Properties представляет постоянный набор свойств. Каждый ключ и соответствующее ему значение в списке свойств являются строками.

Класс Properties используется многими классами Java. Например, он служит возвращаемым значением метода System.getProperties() при получении переменных окружения.

Для получения дополнительной информации об этом классе,см. Properties。

Другие расширения