Абстрактный тип: структура как набор операций

Коротко

Абстрактный тип данных (АТД) описывает структуру тем, ЧТО с ней можно делать, - набором операций и их контрактом, - а не тем, как она хранится в памяти. «Список» как АТД - это операции «взять i-й», «добавить», «вставить», «удалить», «длина» и обещание, что они делают. Реализация - это уже конкретное представление в памяти и код операций. Одна абстракция допускает много реализаций. Разделять их полезно: код, который ПОЛЬЗУЕТСЯ списком, не должен знать, массив внутри или цепочка узлов.

Если ты уже отличаешь абстрактный тип (набор операций и контракт) от его реализации (представление в памяти) и понимаешь, зачем их разделяют, листай до «Теперь сам».

Как думаешь, что нужно знать про структуру, чтобы ей пользоваться

Чтобы ездить на машине, не обязательно знать устройство двигателя: хватает руля, педалей и коробки - того, ЧТО машина умеет и как её об этом просить. Со структурой данных так же. Чтобы пользоваться списком, тебе нужен набор операций («добавь в конец», «дай пятый элемент», «сколько всего») и обещание, что каждая делает. А вот КАК список хранит элементы внутри - подряд в памяти или цепочкой ссылок - тебя, пока ты им пользуешься, не касается. Это разделение и есть главная идея раздела.

На что это похоже

Розетка в стене - это контракт: форма отверстий и 220 вольт. Ты втыкаешь любой прибор, не зная и не спрашивая, откуда ток - с гидростанции, с атомной или с солнечной панели на крыше. Контракт один, источников много. Поменяли электростанцию - твой чайник этого не заметил, потому что он полагался на контракт розетки, а не на устройство станции. Абстрактный тип - это розетка для данных: фиксированный набор «разъёмов»-операций, за которым может стоять любая начинка.

Механизм: интерфейс сверху, представление снизу

Абстрактный тип - это пара «набор операций + их семантика». Семантика (контракт) говорит, что операция ДЕЛАЕТ, а не как: «взять(i) возвращает элемент, добавленный i-м по счёту»; «добавить(x) увеличивает длину на один и кладёт x в конец». Ни слова о памяти. Реализация выбирает представление (например, непрерывный кусок памяти или цепочку узлов со ссылками) и пишет код каждой операции ПОД это представление. Одному интерфейсу отвечают разные реализации.

Абстрактный тип - это рамка операций сверху. Что под ней, пользователь не видит и не должен видеть.

Правило

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

Разбор: «список» как абстрактный тип

Опишем список, не заглядывая внутрь. Операции: длина() - сколько элементов; взять(i) - элемент под номером i; добавить(x) - дописать в конец; вставить(i, x) - поставить x на место i, сдвинув остальные; удалить(i) - убрать i-й. Контракт каждой - про наблюдаемое поведение: после добавить(x) длина на один больше, а взять(длина−1) возвращает x. Заметь: в этом описании нет слов «память», «ссылка», «ячейка». Это и делает его АБСТРАКТНЫМ - оно про то, что список для тебя ДЕЛАЕТ, а не из чего собран. Ровно по такому описанию потом можно строить реализацию и проверять, держит ли она контракт.

Разбор: зачем вообще это разделять

Представь, что твой код перебирает список и складывает числа. Он вызывает взять(i) и длина() - и всё. Теперь автор структуры поменял начинку: был непрерывный массив, стала цепочка узлов. Если твой код полагался только на ОПЕРАЦИИ, он не сломается - контракт тот же, ответы те же. А если бы ты полез внутрь («я знаю, что элементы лежат подряд, прочитаю память сам») - твой код развалился бы от чужой правки. Разделение интерфейса и реализации - это граница, за которой каждый может меняться, не ломая другого: автор структуры волен переписать начинку, пользователь волен не вникать в неё. Без границы любое изменение внутри тянет за собой правки во всём, что структурой пользуется.

Что ломается без этого

Главная ошибка - спутать интерфейс с реализацией и закладываться на устройство. «Возьму список и буду обращаться к нему как к куску памяти напрямую» - и код намертво привязан к одной реализации: сменят её, и всё посыпется. Вторая ошибка - считать, что раз две структуры дают одинаковые ответы, то они взаимозаменяемы во всём. Ответы-то одинаковые, а вот ЦЕНА операций - нет, и об этом вся следующая глава. Абстракция скрывает устройство, но не отменяет стоимость: её надо знать отдельно.

Зачем это в работе

На разделении интерфейса и реализации стоит вся стандартная библиотека любого языка. В Python list, dict, set - это интерфейсы (наборы операций с обещанным поведением), а их начинка (динамический массив, хеш-таблица) спрятана и может меняться от версии к версии, не ломая твой код. Когда в вакансии пишут «знать структуры данных», имеют в виду именно это: какие операции есть у каждого типа, что они обещают и - в следующей главе - чего стоят. Умение описать задачу через нужные операции, а потом подобрать реализацию под них, - это и есть инженерный выбор структуры данных.

Теперь сам

Опиши как абстрактный тип «мешок непрочитанных писем»: какие операции ему нужны и что каждая обещает - не говоря ни слова о том, как письма хранятся. Почему такое описание полезнее, чем «список в памяти»?

Ответ. Операции примерно такие: добавить(письмо) - положить новое письмо; сколько() - число непрочитанных; есть?(письмо) - лежит ли конкретное; убрать(письмо) - вынуть прочитанное; перебрать() - пройти по всем. Контракт - про поведение: после добавить(p) число выросло на один и есть?(p) истинно; после убрать(p) - есть?(p) ложно. Ни слова о памяти. Полезнее это тем, что описание не привязано к реализации: пока операции и их обещания те же, начинку («список», «множество», «хеш-таблица») можно выбрать позже - под то, какие операции нужны чаще, - и поменять потом, не трогая код, который мешком пользуется. А вот какая начинка даст дешёвый «есть?» - разговор следующей главы.

Главное

Абстрактный тип данных описывает структуру набором операций и их контрактом (что каждая делает), без единого слова о хранении в памяти. Реализация - это представление плюс код операций под него; одной абстракции отвечает много реализаций. Разделять их нужно, чтобы код-пользователь опирался на операции, а не на устройство: тогда начинку можно поменять, ничего не сломав. На этом стоит вся стандартная библиотека - list, dict, set - это интерфейсы, а их начинка спрятана.