Структура списка

Динамические структуры

NIL

Это константа-указатель, которая ссылается в никуда.

(Иногда – списковые структуры)

Динамические структуры делятся на 2 типа:

· Очереди (queue) FIFO

· Стеки (stack) LIFO

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

HEAD (указатель)

Данные

Указатель

Данные

Указатель

Данные (последний элемент)

Указатель – NIL

(опционально)
TAIL (указатель)

Это однонаправленный (односвязный) список.

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

HEAD (указатель)

Данные

Указатель вверх – NIL

Указатель вниз

Данные

Указатель вверх

Указатель вних

Данные (последний элемент)

Указатель – NIL

(опционально)
TAIL (указатель)

Достоинства и недостатки динамических структур
Достоинства

· Лёгкость их расширения (в них удобно добавлять элементы в любое место)

Недостатки

Невозможна произвольная адресация

· Накладные расходы на хранение каждого элемента списка