Древовидная организация данных. Списки. Сравнение методов организации данных в памяти ЭВМ.

Список – множество элементов, каждый из которых может быть либо записью, либо списком.
Структуру списка выражают формулой, в которой записи помечаются буквами, а списки заключаются в круглые скобки. Список, включённый в другой список – подсписок.
Перечисление всех списков из записей а1, а2,…,аn, образующих множество L0, осуществляющихся следующим образом. Обозначим через Li множество всех кортежей с элементами из Li. Введем последовательность множеств:
L1=L0’+ L0
L2= L1’+ L1
L3=L2’+ L2
………
Все списки содержатся в множестве L=L0+L1+… Li+…
Адреса связи, принадлежащие каждой записи, образуют звено связи. В звене связи однонаправленного списка 2 адреса, первый указывает на следующий элемент списка, второй – на подсписок или запись. В звене связи двунаправленного списка 4 адреса связи: 2 из них обеспечивают прямое и обратное направление в списке, 3-й и 4-й начало и конец подсписка