Кільцеві пов’язані списки

Останній елемент повязаного списку не має наступного за ним елемента, і значення покажчика nex t останнього елемента зазвичай встановлюється рівним спеціальному значенням, зазвичай NULL, щоб показати, що цей елемент списку є останнім в певних випадках останній елемент списку не вказує на спеціальне значення, а вказує на перший елемент цього ж списку Такий список називаєтьсякільцевим повязаним списком (circular linked list),оскільки звязку утворюють топологію кільця Кільцеві повязані списки можуть бути як однозвязний, так і двохзвязної У двохзвязної кільцевих списках покажчик pre v першого елемента вказує на останній елемент списку На рис АЗ і А4 показані відповідно одинзвязні і двохзвязної кільцеві списки

next                          next                         next

РісA3 Однозвязний кільцевої список

prev                 next      prev                  next      prev                 next

РисА4 Двохзвязної кільцевої список

Стандартної реалізацією повязаних списків в ядрі Linux єдвохзвязної кільцевої список Такі звязані списки забезпечують найбільшу гнучкість роботи

Переміщення по звязаному списку

Переміщення по звязаному списку виконується послідовно (лінійно) Після того як переглянутий поточний елемент, виконаються розіменування його покажчика next, що дозволяє звернутися до наступного за ним елементу і тд Це найпростіший і найбільш підходящий метод переміщення але повязаному списку Якщо важлива можливість довільного доступу до будь-якого елементу контейнера, то повязані списки не використовуються Повязані списки використовуються, коли важлива можливість динамічного додавання і видалення елементів, а також можливість послідовного проходження по всіх елементах списку

Часто перший елемент списку представлений з допомогою спеціального покажчика, який називається головним елементом або головою (head), що дає можливість швидко і легко звертатися до першого елемента У некольцевого повязаному списку останній елемент відрізняється тим, що його покажчик дорівнює значенню NULL У кільцевому повязаному списку останній елемент відрізняється тим, що вказує на головний елемент Таким чином проходження списку можна виконати лінійно, починаючи з першого елемента і закінчуючи останнім У двохзвязної списку проходження можна також виконати і в протилежному напрямку, починаючи з останнього і закінчуючи першим елементом Звичайно, якщо задано певний елемент списку, то можна перейти за списком вперед і тому на задану кількість елементів При цьому немає необхідності проходити весь список

Джерело: Лав, Роберт Розробка ядра 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>

*

*