Лінійний список

Рис. Складові вузла списку

Рис. Лінійний список

Лінійний список

Список може бути односпрямованим, якщо його вузли мають зв'язки, які спрямовані тільки від голови до останнього вузла хвоста, і двоспрямованим, якщо його вузли мають що зв'язки додатково спрямовані від останнього вузла хвоста до голови.

Оскільки можна вказати лексикографічний порядок вузлів, то список ще називається зв'язаним. При цьому односпрямований список називається однозв’язанным, а двоспрямований – двозв’язаний.

До списку можна застосовувати, наприклад, такі операції: розбити список на два списку, об'єднати два списки, додати вузли до списку.

Підходи до реалізації списку

З погляду реалізації списку в пам'яті даних можна розглядати два такі підходи:

Ø вузли списку розміщуються в суміжних ділянках пам'яті, утворюючи масив (вектор);

Ø вузли списку розміщуються в довільних ділянках пам'яті, зв'язуючись спеціальним чином і утворюючи шляхом зчеплення вузлів, або зв'язаний список.

Другий підхід зазвичай реалізується за допомогою механізму динамічного розподілу пам'яті в купі.

На основі лінійного списку будуються лінійні структури даних, наприклад, стек, черга і дек.

Стек

Стек - це лінійний список, в якому всі включення і виключення вузлів здійснюється в одному кінці списку, який називається вершиною.

а) векторне представлення;

б) зв’язане представлення.

Рис. Представлення стеку

Черга

Черга – це лінійний список, в якому всі включення проводяться в одному кінці, а всі виключення – в іншому.

а) векторне представлення;

б) зв’язане представлення.

Рис. Представлення черги

Дек

Дек (deque-dounle-ended queue) (черга з двома кінцями) – це лінійний список, в якому всі включення та виключення виконуються на обох кінцях списку.

а) векторне представлення;

б) зв’язане представлення.

Рис. Представлення деку

Дата добавления: 2015-10-29