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

Структура вузла: Вузол у зв’язаному списку зазвичай складається з двох компонентів:
дані: Він містить фактичне значення або дані, пов’язані з вузлом.
Наступний покажчик: Він зберігає адресу пам'яті (посилання) наступного вузла в послідовності.
Голова і хвіст: Доступ до пов’язаного списку здійснюється через головний вузол, який вказує на перший вузол у списку. Останній вузол у списку вказує на NULL або nullptr, що вказує на кінець списку. Цей вузол відомий як хвостовий вузол.

Навіщо потрібна структура даних зв’язаного списку?

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

• Динамічна структура даних: Розмір пам'яті можна виділяти або звільняти під час виконання на основі операції вставки або видалення.
• Простота вставки/видалення: Вставляти та видаляти елементи простіше, ніж масиви, оскільки жодні елементи не потрібно зміщувати після вставки та видалення, потрібно лише оновити адресу.
• Ефективне використання пам'яті: Як ми знаємо, зв’язаний список — це динамічна структура даних, розмір якої збільшується або зменшується відповідно до вимог, тому це дозволяє уникнути невикористання пам’яті.
• Реалізація: Різноманітні розширені структури даних можна реалізувати за допомогою пов’язаного списку, як-от стек, черга, графік, хеш-карти тощо.

приклад:

У системі, якщо ми підтримуємо відсортований список ідентифікаторів у масиві id[] = [1000, 1010, 1050, 2000, 2040].

Якщо ми хочемо вставити новий ID 1005, тоді, щоб зберегти відсортований порядок, ми повинні перемістити всі елементи після 1000 (за винятком 1000).

Видалення масивів також обходиться дорого, доки не використовуються спеціальні методи. Наприклад, щоб видалити 1010 в id[], потрібно перемістити все після 1010, оскільки виконується так багато роботи, що впливає на ефективність коду.

Типи зв'язних списків :

В основному існує три типи пов’язаних списків:

1. Однозв'язковий список
2. Подвійний зв'язаний список
3. Круговий пов'язаний список

1. Однозв'язковий список :

У однозв’язаному списку кожен вузол містить посилання на наступний вузол у послідовності. Обхід однозв’язаного списку виконується в прямому напрямку.

Однозв'язковий список

2. Двозв'язний список :

У подвійно зв'язаному списку кожен вузол містить посилання як на наступний, так і на попередній вузли. Це дозволяє здійснювати обхід як у прямому, так і у зворотному напрямках, але вимагає додаткової пам’яті для зворотного посилання.

Двозв'язний список

3. Круговий пов'язаний список :

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

повна схема суматора

Круговий пов'язаний список

Операції над пов’язаними списками

1. Вставка : Додавання нового вузла до пов’язаного списку передбачає коригування покажчиків існуючих вузлів для підтримки належної послідовності. Вставлення можна виконати на початку, у кінці або в будь-якій позиції в списку
2. Видалення : Видалення вузла зі зв’язаного списку вимагає налаштування покажчиків сусідніх вузлів, щоб подолати розрив, залишений видаленим вузлом. Видалення можна виконати на початку, у кінці чи будь-якій позиції в списку.
3. Пошук : Пошук конкретного значення у зв’язаному списку передбачає обхід списку від головного вузла, поки значення не буде знайдено або досягнуто кінця списку.

Аналіз складності зв'язаного списку :

• Часова складність: O(n)
• Допоміжний простір: O(n)

Переваги пов’язаних списків

• Динамічний розмір: Зв’язані списки можуть динамічно збільшуватися або звужуватися, оскільки розподіл пам’яті здійснюється під час виконання.
• Вставка та видалення: Додавання або видалення елементів зі зв’язаного списку є ефективним, особливо для великих списків.
• Гнучкість: Зв’язані списки можна легко реорганізовувати та змінювати, не вимагаючи безперервного блоку пам’яті.

Недоліки пов’язаних списків

• Довільний доступ: На відміну від масивів, пов’язані списки не дозволяють прямого доступу до елементів за індексом. Обхід необхідний для досягнення певного вузла.
• Додаткова пам'ять: Зв’язані списки вимагають додаткової пам’яті для зберігання покажчиків порівняно з масивами.

Висновок:

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