Способы организации записей в списки. Проблемы, возникающие при работе со списками. Способы их преодоления.

 Линейные структуры (списки, вектора). Обычные списки. Адрес каждого элемента однозначно определяется его номером. Спи́сок — конечное, возможно пустое множество данных (элементов) различной природы, имеющее определённый смысл для решаемой задачи. В качестве элементов множества (списка) могут выступать любые другие элементы данных, в том числе и сами списки. Размер списка — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком.Очередь – линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом конце списка. Стек – линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка. Уязвимость – переполнение стека, ограниченный объем данных. Дек – линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах списка. Кольцо – включение идет по одному, а выключение по-другому. Может быть потеря данных. Кольцо с указателями на заголовок. При входе в кольцо не через его начало можно быстро получить информацию из заголовка. Кольцо с двунаправленными указателями. Если какая-нибудь запись цепи будет разрушена, все остальные записи останутся доступными. Если будет испорчен один указатель – его можно восстановить. «Коралловое» кольцо для повышения устойчивости. Если разрушена запись с четным номером, любая другая запись может быть найдена. Если потеряна запись с нечетным номером, то некоторые записи могут стать недоступными.

 

 

 

 

Серия сообщений "Базы данных":
Часть 1 - Файловые системы. Назначение файловых систем.
Часть 2 - Особенности орган хранения данных
...
Часть 5 - Журнализация изменений БД. Индивидуальные откаты транзакций.
Часть 6 - Коллективный доступ к данным. Проблемы коллективного доступа.
Часть 7 - Линейные структуры. Понятие списка. Типы списков («шина», «кольцо»).
Часть 8 - Иерархии или деревья. Основные понятия и определения. Бинарные и n-арные деревья,
Часть 9 - 6 Понятие сетевой организации данных. Структуры типа «звезда», объединение звёзд, полносвязная сеть, произвольный граф.
...
Часть 43 - Метод вспомогательной таблицы для случая произвольного графа. Отличия от случая моделирования иерархий
Часть 44 - Объектно-ориентированная модель и реляционная модель. Сходство и отличия.
Часть 45 - Использование «координатного» метода для моделирования иерархий и произвольных графов. Его достоинства и