СД типа двусвязный линейный список

СД типа циклический линейный список.

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

Операции для работы с циклическим линейным списком те же, что и для односвязного линейного списка.

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

Дескриптор данной структуры состоит из трех полей указательного типа:

Допустимые операции:

1. инициализация;

2. сделать список пустым:

3. проверка: список пуст / список не пуст;

4. установить указатель в конец списка / начало списка (две отдельные процедуры);

5. передвинуть указатель вперед / назад на один шаг;

6. включить элемент в список до указателя / после указателя;

7. исключить элемент из списка до указателя / после указателя.

При этом для включения элемента в список необходимо распознать следующие три ситуации:

1. список пуст;

2. включение элемента в середину списка;

3. включение элемента в список в качестве первого.

Для упрощения операции включения / исключения реализуют циклические двусвязные списки. При реализации такого списка формируют указатели (вместо маркеров конца и начала списка), указывающие на первый и последний элементы списка. Допустимые операции для СД типа циклический двусвязный список аналогичны операциям для линейного двусвязного списка.

Дата добавления: 2014-01-07