Модуль 0. Урок 1. List/Set/Array. — Java: Структуры данных

В первом модуле будем говорить об абстрактных структурах данных (СД).

Что же такое структура данных (СД)?

СД - способ организации информации в компьютере таким образом, чтобы потом ее эффективно использовать.

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

Каждая СД работает с записями. Один объект внутри структуры данных - одна запись. Одна запись может быть n-размерной.

По мерности записей на один объект, СД делят на:

• 0 - юнит/unit (но таких СД нет);
• 1 - синглтон/singleton - хранит только объект. Это может быть число, строка, да вообще любой объект;
• 2 - пара/couple, pair, dual, twin, product - хранит не только сам объект, но и дополнительную, связанную с ним, информацию, которая не является частью этого объекта. Это может быть ключ к объекту или некий другой объект;
• 3 - трипл/triple...
• n - ...

Рассмотрим пример:

Какую СД выбрать?

• Задача 1. Составить список всех студентов в группе.
• Задача 2. Список всех аудиторий в корпусе университета.

1. Какого размера будет запись в СД?

   Один студент - одна запись в СД, но форма записи может быть многомерной. Для списка аудиторий нам точно triplet не пригодится. Поэтому размер записи для студентов / аудиторий - 1 / 1

2. СД для хранения или для обработки?

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

   Список студентов нужно как-то обрабатывать, а список аудиторий просто для учета, поэтому: обрабатывать / хранить.

3. Разрешаем ли мы хранить дубликаты?

   Фамилии, имена могут совпадать, в отличие от номеров аудиторий в одном корпусе, поэтому: да / нет

4. СД будет фиксированного или изменяемого размера? Для обоих задач — изменяемого.

Выбираем СД:

• для учета студентов — list (например, его имплементация ArrayList);
• для учета аудиторий — set (например, его имплементация TreeSet)

Почитайте про каждую из этих структур данных из примера. Возможно у вас будут иные обоснованные предложения той или иной СД для этого примера? Обсуждение приветствуется :)

Классификация структур данных

• Collections.pdf

Полезные ссылки:

• Структура данных
• Абстрактный тип данных
• List
• Array
• Set

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.