Структура даних Зв'язаний список / LinkedList

Привіт всім! Вітаю на каналі kostrub.online

В попередньому відео ми налаштували дев. середовище та познайомились з першою простою структурою даних List / Список. Сьогодні ми розглянемо наступну реалізацію списку LinkedList. Також порівняємо плюси та мінуси імплементацій цієї структури.



Тож почнемо,

Як ми побачили з попередньої імплементації List - головна проблема це зберігання коректного індексу для значень. Звичайно все залежить від вимог до структури даних та алгоритму реалізації. Але якщо у нас стоїть задача оптимізувати додавання / видалення елементів зі списку, то треба розібратися зі зв'язаним списком LinkedList. На імплементації ми побачимо що за оптимізацію, як то кажуть, треба чимось платити. У випадку алгоритмів — це як правило ресурси пам'яті space complexity.

Що ж таке цей зв'язаний список, пропоную розглянути приклад із реального життя. Наприклад, це може буде потяг:



І для того щоб знайти свій вагон, нам треба пройти з голови до зазначеного індексу / номеру вагона.



Визначимо абстрактну модель для зв'язаного списку LinkedList. Вона буде майже така сама, як і для List:
  • Може додавати елемент або вставляти по індексу
  • Може змінювати елемент по індексу / номеру
  • Можемо зчитувати елемент за індексом
  • Може видаляти будь-який елемент зі списку
Перейдемо до реалізації.

Визначимо специфікацію абстрактної моделі для структури даних LinkedList / Зв'язаний список:

 
Імплементація для структури даних LinkedList / Зв'язаний список:
 

Git репозиторій https://github.com/kostrub-online/Computer-Science

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


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


Опублікувати коментар

0 Коментарі