Лінійні однорангові списки

Довжина списку. Кількість елементів у списку.

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

Список може бути сортовані або несортовані

Залежно від реалізації може бути можливий довільний доступ до елементів списку.

 елемент списку доступний в програмі через покажчик. «Сенс» цього покажчика відображає функціональне призначення елемента списку в програмі: перший, останній, поточний, попередній, новий і т.п. Між покажчиком і елементом списку є така ж взаємозв'язок, як між індексом в масиві і елементом масиву;

 в програмі список задається за допомогою заголовка - покажчика на перший елемент списку;

 порядок проходження елементів визначається послідовністю зв'язків між елементами. Зміна порядку елементів (вставка, видалення) здійснюються зміною перевстановлення покажчиків на сусідні елементи.

логіческій (порядковий) номер елемента списку також задається його природною нумерацією в ланцюжку елементів;

спісок є структурою даних з послідовним доступом. Для полученіяn-го за рахунком елемента необхідно послідовно пройти по ланцюжку від елемента, на який є покажчик (наприклад, від заголовка);

спісок зручний для використання саме як динамічна структура даних. елементи списку зазвичай створюються як динамічні змінні, а зв'язки між ними встановлюються програмно (динамічно);

спісок має властивість локальності змін: при вставці / видаленні елемента зміни стосуються тільки поточного та його сусідів. Згадаймо масив: при вставці / видаленні його елементів відбувається фізичне переміщення (зрушення) всіх елементів від поточного до кінця.

Звідси випливає, що переваги списків проявляються в таких структурах даних, де операції зміни порядку превалюють над операціями доступу і пошуку.

Операції, які ми маємо право виконувати з лінійними списками:

1. Отримати доступ до k-му вузлу списку, щоб проаналізувати і / або

змінити вміст його полів.

2. Включити новий вузол безпосередньо перед k-им вузлом.

3. Виключити k-й вузол.

4. Об'єднати два (або більше) лінійних списки в один список.

5. Розбити лінійний список на два (або більше) списку.

6. Зробити копію лінійного списку.

7. Визначити кількість вузлів в списку.

8. Виконати сортування вузлів списку в порядку зростання за деякими

9. Знайти в списку вузол з заданим значенням в деякому полі.

Односпрямований і двонаправлений список

Односпрямований і двонаправлений список - це лінійний список, в якому все виключення і додавання відбуваються в будь-якому місці списку.

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

Приклад 2. Видалення з односпрямованого списку елемента з номером k

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

Більш докладно розглянемо роботу зі зв'язаними списками на прикладі однонаправленої некольцевого списку.

#include

typedef long BT;