Різновиди списків
1) Лінійний зв’язний список називається двонаправленим, якщо кожний вузол списку має два поля для збереження вказівників, а саме вказівника на наступний та вказівника на попередній вузли списку.
list
-
NULL
7
9
9
NULL
2) лінійний зв’язний список називається циклічним, якщо його останній елемент замість значення NULL містить вказівник на перший елемент списку.
list
7 |
|
|
2 |
|
|
6 |
|
3) Стисле зберігання списків. Нехай у списку міститься багато елементів з одинаковим значенням (наприклад х). Якщо в цьому списку замінити кожен елемент парою, що складається зі значення елемента та його порядкового номера, і далі вилучити зі списку всі вузли, що мають значення (х), то такий спосіб зберігання називається стислим.
Приклад:
L= <0,3,7,0,0,1,0,0,0,5,0,0,0>
Оскільки останні елементи списку можуть мати значення х і бути вилучені, тобто невідома стане кількість елементів у списку, то доцільно завжди додатково зберігати останній елемент списку.
-
3
2
7
3
1
6
5
10
0
13
NULL
4) Індексне збереження списків: цей спосіб полягає в тому, що список ділиться на декілька підсписків таких, що кожен елемент списку потрапляє тільки в один з підсписків. Додатково використовуємо індексний список, елементи якого вказують на початки підсписків. Поділ початкового списку на підсписки здійснюється за допомогою індексної функції g(x), яка виробляє значення індексу і для елемента х: i=g(x). Цінність індексного зберігання полягає в тому, що для пошуку елемента з певною властивістю треба переглядати не весь список, а тільки елементи певного підсписку.
Приклад:
L = <177, 90, 288, 17, 60, 300>
g(x) = 1+x % 3
L1 = < 177, 90, 288, 60, 300>
L2 = < 250 >
L3 = < 23, 17 >
L
|
|
|
177 |
|
|
90 |
|
|
288 |
|
|
60 |
|
|
300 |
NULL |
|
|
|
250 |
NULL |
NULL |
|
|
23 |
|
|
17 |
NULL |