Лекція №3

Зв’язний список

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

Структура даних, яка надає можливість доступу до елементів, що розміщені не на її межах, називається зв’язним списком.

Розглянемо принцип виконання основних операцій над її елементами.

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

Насправді у зв’язному списку відбуватиметься вилучення цих елементів зі списку, але за традицією надалі продовжуватимемо називати цю операцію читанням.

Читання елемента списку можна організувати шляхом зсуву вліво решти елементів, що розташовані за тим, що читається. Однак, ці дії характеризуються певним часом виконання. Ефективнішим буде шлях «не бачення» цього елемента у списку. Тобто, якщо після (k-1)-го елемента у списку йшов k-ий, а після нього ― (k+1)-ий, то після вилучення k-ого елемента за (k-1)-им буде слідувати (k+1)-ий. Схематично це можна зобразити таким чином:

(k-1) елемент

k елемент

(k+1) елемент

Запис нового елемента списку у вказане місце, наприклад після k-ого елемента, буде викликати зсув всіх елементів, що знаходяться після k-ого, на одну позицію вправо. Зрозуміло, що і такий підхід не є оптимальним. Простіше було б записати його в кінець списку, але змінити для цього послідовність перегляду елементів списку: після k-ого елемента переходити до нового елемента, записаного в кінець, а потім до (k+1)-ого:

k елемент

(k+1) елемент

...

n елемент

new елемент

Структуру «список» можна реалізувати на одновимірному масиві. Кожний елемент списку буде займати два сусідніх елементи масиву, тобто таку ланку: перший ― сам елемент списку, другий ― індекс масиву, що вказує на місце знаходження наступного елемента списку:

k-ий елемент списку	індекс елемента масиву, який містить наступний елемент списку
а_і	а_і₊₁

Однак, ефективнішим для реалізації списку є використання покажчиків, тобто розміщення списку в динамічній пам’яті, а не на статичному масиві, оскільки при вставленні усередину масиву або ж вилученні з нього елементів необхідно переміщати на сусідні місця ті елементи,що залишилися. Схематично структуру списку можна представити так:

Елемент 1

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Відповідальність газопостачального та газорозподільного підприємства	\|	Зв’язним списком називається структура даних, кожний елемент якої зв’язаний з наступним (або попереднім, або з обома сусідніми) елементом за допомогою покажчиків.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.01 сек.