---
title: Структуры данных
seo:
title: Структуры данных — Kotlin Developer
description: "Тема «Структуры данных» для собеседования Kotlin Developer. В чём различия между стеком и кучей? Какие структуры данных вы знаете, для чего они используются и в каких случаях их следует применять?"
---
[Все темы Kotlin Developer](/kotlin-developer)
## В чём различия между стеком и кучей? [#q-14bee738d69b8196bc61da2357a18a4e]
Стек и куча - это два основных механизма управления памятью:
{/* prettier-ignore */}
1. Стек (Stack):
- Хранит локальные переменные и вызовы функций.
- Организуется по принципу LIFO (Last-In, First-Out).
- Размер стека фиксирован и обычно небольшой.
- Управление стеком автоматическое и эффективное.
1. Куча (Heap):
- Используется для динамического выделения памяти.
- Объекты хранятся в куче, когда их размер неизвестен на этапе компиляции или когда они должны быть доступны в течение продолжительного времени.
- Управление памятью в куче более сложное, и она может подвергаться фрагментации.
- В Kotlin/JVM память объектов в куче освобождает GC. Разработчик управляет достижимостью объектов и отдельно закрывает внешние ресурсы, например файлы.
:::note[Ссылки для изучения]
1. [Типы данных в Kotlin](https://metanit.com/kotlin/tutorial/2.2.php)
:::
---
## Какие структуры данных вы знаете, для чего они используются и в каких случаях их следует применять? [#q-14bee738d69b81f99d32f0d3de8146f5]
Вот несколько основных структур данных и их области применения:
{/* prettier-ignore */}
1. Список (List):
- Позволяет хранить упорядоченную коллекцию элементов.
- Используется для хранения данных, которые должны быть упорядочены и доступны для изменения.
1. Массив (Array):
- Представляет собой последовательный блок памяти, содержащий элементы одного типа данных.
- Эффективен для доступа к элементам по индексу.
- Часто используется в алгоритмах и задачах, где требуется быстрый доступ к элементам.
1. Стек (Stack):
- Реализует принцип Last-In, First-Out (LIFO).
- Используется для управления вызовами функций, обратного отслеживания, обхода деревьев и т. д.
1. Очередь (Queue):
- Реализует принцип First-In, First-Out (FIFO).
- Используется в задачах, где необходимо обрабатывать элементы в том порядке, в котором они были добавлены.
1. Словарь (Dictionary или Map):
- Предоставляет связь между ключами и значениями.
- Используется для быстрого доступа к данным по ключу и поиска элементов по ключу.
1. Множество (Set):
- Содержит уникальные элементы без учета порядка.
- Используется для удаления дубликатов и проверки на принадлежность элемента к набору.
1. Связанный список (Linked List):
- Элементы связаны ссылками. Доступ по индексу требует обхода списка и занимает O(n).
- Вставка и удаление рядом с уже найденным узлом эффективны; поиск позиции в середине списка сам по себе занимает O(n).
:::note[Ссылки для изучения]
1. [Типы данных в Kotlin](https://metanit.com/kotlin/tutorial/2.2.php)
:::
---
## Какие структуры данных наиболее часто используются в Kotlin и как они реализованы? [#q-14bee738d69b8164bbb8d4e1228a4226]
Наиболее часто используемые структуры данных в Kotlin:
- List: Интерфейс списка только для чтения, например List<Int>. Сам объект может изменяться через другую ссылку.
- MutableList: Реализован как изменяемый список. Например,
MutableList<Int>.
- Set: Интерфейс множества только для чтения, например Set<Int>. Сам объект может изменяться через другую ссылку.
- MutableSet: Реализован как изменяемое множество. Например,
MutableSet<Int>.
- Map: Интерфейс словаря только для чтения, например Map<String, Int>. Сам объект может изменяться через другую ссылку.
- MutableMap: Реализован как изменяемый словарь. Например,
MutableMap<String, Int>.
Все эти интерфейсы позволяют читать и искать элементы. Операции добавления, удаления и замены предоставляют изменяемые интерфейсы MutableList, MutableSet и MutableMap.
:::note[Ссылки для изучения]
1. [Типы данных в Kotlin](https://metanit.com/kotlin/tutorial/2.2.php)
:::
---
## Объясните разницу между MutableList и List в Kotlin. [#q-14bee738d69b812f99c5debf4545897c]
Разница между MutableList и List:
- List предоставляет доступ только для чтения. Через эту ссылку нельзя добавлять, удалять или заменять элементы, но другой владелец MutableList может изменить тот же объект. Пример: val numbers: List<Int> = listOf(1, 2, 3).
- MutableList: Изменяемый список. Позволяет добавлять,
удалять и изменять элементы после создания. Пример:
val mutableNumbers: MutableList<Int> =
mutableListOf(1, 2, 3)
.
:::note[Ссылки для изучения]
1. [Типы данных в Kotlin](https://metanit.com/kotlin/tutorial/2.2.php)
:::
---
## Как реализовать собственную структуру данных в Kotlin? [#q-14bee738d69b81d78e23c600f5d83b21]
Чтобы реализовать собственную структуру данных, необходимо создать класс и определить нужные методы.
Пример — реализация простого стека:
```kotlin
class Stack {
private val elements = mutableListOf()
fun push(item: T) {
elements.add(item)
}
fun pop(): T? {
if (elements.isEmpty()) {
return null
}
return elements.removeAt(elements.size - 1)
}
fun isEmpty() = elements.isEmpty()
fun size() = elements.size
}
```
:::note[Ссылки для изучения]
1. [Типы данных в Kotlin](https://metanit.com/kotlin/tutorial/2.2.php)
:::
---
## В каких случаях стоит использовать HashMap вместо TreeMap? [#q-14bee738d69b81a191a0d2b93ddeba0e]
Разница между HashMap и TreeMap:
- HashMap подходит для доступа по ключу без сортировки. При хорошем распределении хешей get и remove имеют ожидаемую сложность O(1), а put также требует учитывать амортизированную стоимость расширения. Это не безусловная гарантия для худшего случая. Порядок обхода не гарантируется.
- TreeMap: Используется, когда требуется хранить элементы в
отсортированном порядке. TreeMap реализует красно-черное дерево и обеспечивает
логарифмическую сложность для операций вставки, удаления и поиска.
Поддерживает упорядоченные итерации.
В общем, используйте HashMap для быстрых операций с элементами без необходимости в сортировке, и TreeMap — когда необходима сортировка и упорядоченный доступ.
:::note[Ссылки для изучения]
1. [Типы данных в Kotlin](https://metanit.com/kotlin/tutorial/2.2.php)
:::