Двонаправлені списки

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

На рис.8.5 зображено структуру заголовної (рис.8.5,а) і внутрішньої (рис.8.5,б) ділянок, а також самого двонаправленого списку (рис.8.5,в). Кожна ділянка такого списку складається з чотирьох значень (рис.8.5,б), а саме: значення самого елемента даних і довідки стандартного вигляду з трьох значень - довжини ділянки, вказівників на наступну і попередню ділянки. В загальному випадку довжина кожної ділянки може бути різною. Заголовна ділянка також складається з чотирьох значень, але її довжина відома і рівна чотирьом, оскільки записом її елемента є вказівник, а всі вказівники мають однакову довжину (рис.8.5,а).

Рис. 8.5. Зображення двонаправленого списку і його ділянок

Очевидно, що операції включення-виключення запису в даному випадку аналогічні до попередніх і також зводяться до коректування зв‘язків між ділянками. Однак операція включення запису в двонаправлений список буде значно складнішою від операції виключення запису з нього, оскільки в першій операції необхідно прочитувати дві ділянки, а в другій - тільки ту, яка виключається. Попередній запис потрібний для коректування зв‘язку на наступний елемент, але цей запис не треба читати, знайдемо його у ділянці, яка виключається. Тому можна записати туди нову адресу без читання самої ділянки.

Двонаправлений список також відображується в одномірний масив, починаючи зі стандартної заголовної ділянки, яка має в масиві індекси 0, 1, 2, 3.