Лекция 6.

4. Линейный список –совокупность однотипных элементов, расположенных последовательно друг за другом, количество элементов в списке не фиксируется.

В списке присутствует указатель, он может перемещаться по списку, отмечает текущий элемент при просмотре списка.

в начале текущий в конце

списка элемент списка

 

Указатель может перемещаться по списку от начала к концу, в этом случае список называется однонаправленный.Еслиуказателю разрешено перемещаться от начала к концу и от конца к началу списка, список называется двунаправленный.

Операции для однонаправленного списка:

1. Сделать список пустым.

2. Установить указатель в начало списка.

3. Передвинуть указатель на одну позицию к концу.

4. Добавить элемент за указателем.

5. Удалить элемент за указателем, если такой есть.

6. Проверить, стоит ли указатель в конце списка.

7. Проверить список на пустоту.

8. Выбрать элемент за указателем без удаления.

 

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

Самим придумать операции для двунаправленного списка.