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

Date: 2015-10-07; view: 462.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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