Программирование двусвязных списков

Очень часто для хранения и обработки различных наборов данных удобно использовать 2-связные (двунаправленные) линейные списки, записи которых связаны посредством пары указателей, хранимых в адресных полях записей списка [5-6]. Логическую структуру 2-связного списка иллюстрирует диаграмма, представленная на рисунке 4.

Рисунок 4 – Диаграмма 2-связного списка

В каждой записи поле prev содержит адрес предыдущей записи, поле next – адрес последующей записи, а data обозначает информационные поля. Для доступа к списку могут быть использованы адреса начальной (start), конечной (end) и текущей (this) записей списка. Индикатором начальной и конечной записей являются нулевые (NULL) значения адресных полей Start и end, соответственно. Любая функциональная обработка списка строится на основе процедур модификации и просмотра. Процедуры модификации должны обеспечивать вставки и исключение записей списка. Частным случаем процедур вставки и исключения являются процедуры добавить и удалить начальную или конечную запись списка. На рисунке 5 представлена диаграмма, иллюстрирующая процедуру вставки новой записи Z после записи Y (или перед записью X).

Рисунок 5 – Процедура вставки в 2-связном списке

Следующая диаграмма иллюстрирует процедуру исключения текущей записи this (рисунок 6).

Рисунок 6 – Процедура исключения в 2-связном списке

Процедуры просмотра списка должны обеспечивать смещение указателя текущей записи (this) на требуемое число позиций в направлении начала или конца списка, как показано на следующей диаграмме (рисунок 7).

Рисунок 7 – Процедура просмотра списка

Частным случаем смещения указателя текущей записи является переход к соседней предыдущей или последующей записи (смещение на 1 позицию), а также нефиксированный переход к начальной или конечной записям списка, который позволяет принудительно инициализировать указатели start и end после модификаций в начале и конце списка.

Для организации объектно-ориентированной обработки данных, реализованных на основе списковых структур, целесообразно построить базовый класс записей 2-связного списка (class Dlink).

Базовый класс Dlink должен включать универсальные компоненты. Компоненты-данные класса Dlink должны обеспечивать двунаправленную защищенную (protected) связь записей списка посредством 2-х адресных полей, которые содержат адреса предыдущей и последующей записей списка, соответственно. Универсальную обработку записей списка должны обеспечивать общедоступные (public) компонентные методы. Компоненты базового класса Dlink могут наследоваться в различных производных классах с информационными полями данных и методами их обработки с обращением к базовым методам обработки списка.