Функциональная спецификация двоичного дерева:

Пусть Т – базовый тип элементов. Обозначим ЛС_т – линейный список из элементов типа Т.

Операции:

• Создание_списка:  ЛС_т

• Список_пуст: ЛС_т  ЛОГ

• Следующий: Т*ЛС_т  Т

• Добавление: Т*Т*ЛС_т  ЛС_т

• Удаление: Т*ЛС_т  ЛС_т

• Первый: ЛС_т  Т

Логическое описание:

тип ЛС_т = (ПУСТО/Непустой_ ЛС_т)

тип Непустой_ЛС_т = (начало: Т; продолжение_ЛС_т)

Логическое описание должно содержать описание декомпозиции операции функциональной спецификации.

1) прогр. добавление: ЛС_т (арг. t, t^’: T, ll: ЛС_Т )

|добавление  если ll есть ПУСТО то непустой_ЛС_Т (t, ll)

иначе непустой_ЛС_Т (начало (ll), добавление (t, t^’, продолжение (ll))

2) прогр. удаление: ЛС_Т (арг. t: T; ll: ЛС_Т)

|удаление  если ll есть ПУСТО то ОШИБКА

иначе

если t=начало (ll) то продолжение (ll)

иначе непустой_ЛС_Т (начало (ll), удаление (t, продолжение (ll))

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

Узел и ссылку можно описать так:

Type     Link = ^Node;     Node = record         Data: integer;         Next: Link;     End;

Для описания списка мы будем использовать дополнительно два вспомогательных узла head и z. Узел head будет указывать на первый элемент списка, а z - последний элемент списка. Head иногда называют "голова" списка, а z - "хвост".

Тогда список можно будет представить в следующем виде.

Такое представление данных позволяет производить некоторые операции гораздо более эффективными методами, чем над массивами. Например, если мы хотим передвинуть элемент 1 из конца в начало, то для произведения такой операции в массиве нам потребовалось бы передвинуть все его элементы чтобы освободить место. В связанном же списке мы только меняем ссылки. Оба варианта рисунка эквивалентны; они только по разному нарисованы. Мы просто переустанавливаем ссылку узла, содержащего 1, на узел содержащий 2, а ссылку пустого узла head на узел содержащий 1. Даже если бы список был очень большой, то нам все равно потребовалось бы только три перестановки ссылок для подобного обмена.

Что более важно, теперь мы можем говорить о "вставке" элемента в связанный список (что увеличивает его длину на один элемент) - операции которая столь неестественна и неудобна на массивах. На рисунке показано как вставить в список новый узел. Нужно вначале добавить этот узел, затем создать ссылку на узел q, а затем изменить ссылку узла p на новый узел. Для этого требуется изменить лишь две ссылки в независимости от длины списка.

Аналогично, мы можем вести речь об "удалении" элемента из списка (что уменьшает его размер на один элемент). Нужно просто переставить ссылку на узел, который следует за узлом q и после этого узел содержащий q должен быть уничтожен.

С другой стороны, есть и операции для которых связанный список не очень хорошо подходит. Наиболее очевидная из них - это "найти k-й элемент" (найти элемент по его индексу): в массиве это делалось простым обращением типа a[k], но в связанном списке мы должны пройти по k ссылкам.

Другой неестественной операцией над связанными списками является операция "найти элемент перед заданным". Если все, что у на есть - это ссылка на элемент q в нашем примере, то единственный способ найти элемент p, который указывает на q - это пройти по всем ссылкам начиная с узла head. На самом деле - эта операция необходима для удаления заданного элемента из списка: как же иначе мы можем переустановить ссылку предыдущего узла ? Во многих задачах, мы можем обойти эту проблему посредством изменения формулировки этой фундаментальной операции на "удалить узел следующий после данного". Аналогичная проблема может быть обойдена и для вставки посредством изменения определения операции на "вставить элемент после заданного узла".