Реалізація двусвязного списку на си

М и розглянули однозв'язний список і прийшли до невтішних висновків - список розумно використовувати в якості стека, тому що операції вставки в початок списку і видалення з початку списку мають складність порядку 1, з додатковими маневрами можна домогтися складності вставки в кінець порядку 1 і визначення довжини за O (1), але видалення з кінця, вставка і пошук елемента залишаються O (n).

Яким чином можна спростити видалення останнього елемента? Очевидно, що якби ми зберігали покажчик на попередній елемент, то було б можливо видаляти останній.

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

Для реалізації списку нам знадобиться структура вузол

Порожня структура типу DblLinkedList

Структура типу DblLinkedList з одним елементом

Перша функція, як зазвичай, створює екземпляр структури DblLinkedList

У ній немає нічого цікавого. Заодно опишемо функцію, яка видаляє список

Тепер, визначимо набір стандартних функцій - pushFront і popFront для роботи з головою, pushBack І popBack для роботи з останнім елементом, getNth, insert і deleteNth для вставки і видалення в довільне місце.

Вставка нового елемента в початок списку

Вставка спереду дуже схожа на вставку в однозв'язний список. Спочатку створюється новий елемент

Створили новий елемент і задали йому значення

Так як він став першим, то покажчик next посилається на стару голову списку, а попереднього елемента немає. Тепер, якщо в списку вже був головний елемент, то його покажчик prev повинен посилатися на новостворений елемент

Тепер перевіримо покажчик tail. Якщо він порожній, то після додавання нового елемента він повинен посилатися на нього

Тепер перекинемо покажчик head на новостворений елемент і збільшимо значення лічильника size

Перекинули указазатель head списку на новостворений елемент

Видалення з початку списку також схоже на оне для однозв'язного списку. Додаються тільки перекидання додаткових вказівників та перевірка, щоб покажчик на останній елемент, в разі, якщо елементів більше не залишилося, став рівним нулю.

Спочатку створимо покажчик на перший елемент списку. Він знадобиться, щоб після зміни всіх покажчиків prev і next ми змогли видалити вузол.

Створили покажчик на перший елемент

Після цього перекинемо покажчик head на наступний за ним елемент

Перекидаємо покажчик head на наступний елемент

Далі перевіряємо, що удаляеми елемент не є одночасно останнім (коли в списку всього один елемент), після чого звільняємо пам'ять.

Створили покажчик на перший елемент

Вставка в кінець і видалення з кінця дуже схожі - просто ми перегортаємо список. Відповідне, все prev змінюються на next, а head на tail

Отримання n-го елемента дуже просте і не відрізняється від оного для однозв'язного списку.

Можна поліпшити цю функцію: якщо список довгий, то в залежності від індексу можна проходити або з початку в кінець, або з кінця в початок. Це дозволяє завжди використовувати не більше N / 2 кроків.

Тепер можна написати функцію видалення і вставки вузла. Спочатку знаходимо потрібний елемент, потім створюємо або новий вузол (якщо вставка), або покажчик на видаляється елемент. Потім змінюємо все покажчики.

Не забуваємо, звичайно, дивитися за значеннями head І tail, щоб вони вказували на існуючі в даний момент елементи.

Додамо пару допоміжних функцій, які допоможуть в роботі. Перша - це друк списку. Так як тип значення - void *, то необхідно передавати функцію друку одного елемента.

У прикладах будемо використовувати змінні типу int

Друга функція - створення списку з масиву

Тепер можна користуватися двусвязного списком

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

Для реалізації нам знадобиться ще одна функція - вставка до зазначеного елемента. Ця функція буде отримувати покажчик на список, покажчик на вузол, перед яким потрібно вставити елемент і нові дані.

Тепер безпосередньо сортування

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

Складність алгоритму - O (n 2), ми маємо одні прохід по несортованими списку складністю порядку n, для кожного елемента проходимо по відсортовані.

Так як при кожному створенні нового вузла ми видаляємо вузол з першого списку, то додаткової пам'яті не потрібно.

Тепер порівняємо складності різних операцій для однозв'язного і двусвязного списку. Односпрямований зв'язний список

Складність операцій для однозв'язного списку.