Пов’язані списки

вязаний список – це структура зберігання інформації (контейнер), яка може містити змінну кількість елементів даних, часто називає-

екпортувати

вузлами,

і дозволяє маніпулювати цими даними На відміну від статичної

масиву, елементи повязаного списку можна створювати динамічно Це дає можливість створювати змінну кількість елементів списку, причому вказане кількість може бути невідомо на етапі компіляції Так як елементи повязаних списків створюються в різні моменти часу, вони не обовязково будуть знаходитися в суміжних областях оперативної памяті Тому елементи списку повинні бути повязані один з одним таким чином, щоб кожен елемент містив покажчик на наступний за ним елемент (next) Вставка або видалення елементів списку виконується простим ізмепеніем покажчиків на наступний елемент Структура повязаного списку показана на рис А1

next                         next                          next              NULL

Рис AI Одност & язний список

В деяких повязаних списках міститься покажчик не тільки на наступний, а й напопередній елемент (prev) Ці списки називаються двохзвязної (doubly linked),тому що вони повязані як вперед, так і назад Повязані списки, аналогічні тим, що показані на рісА1, називаютьсяодносвязіимі (singly linked)Двохзвязної список показаний на рис А2

NULL prev                 next      prev                 next      prev                 next    NULL

Рис А2 Двохзвязної список

Джерело: Лав, Роберт Розробка ядра Linux, 2-е видання : Пер з англ – М: ТОВ «ІД Вільямс »2006 – 448 с : Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*