1.1  Види динамічних структур даних

А) Лінійні списки

В лінійному списку кожний елемент пов’язаний з наступним і, можливо, з попереднім. У першому випадку список називається «однозв’язним» ( рис.1.2 ) , в другому – «двозв’язним» ( рис.1.3 ) . Якщо останній елемент пов’язати вказівником з першим, отримаємо «кільцевий список» ( рис.1.4 ), ( рис.1.5).

Кожний елемент списку містить  ключ, що ідентифікує цей елемент. Ключ зазвичай буває або цілим числом, або рядком та є частиною інформаційного поля. В якості ключа в процесі роботи зі списком можуть виступати різні частини інформаційного поля. Ключі різних елементів списку можуть співпадати. Над списками можна виконувати наступні операції :

       початкове формування списку ( створення першого елементу );

       додання елементу в кінець списку ;

       читання елементу із заданим ключем ;

       видалення елементу із заданим ключем ;

       упорядкування списку за ключем.

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

Малюнок 1.2 – Однозв’язний список