В попередньому відео ми налаштували дев. середовище та познайомились з першою простою структурою даних List / Список. Сьогодні ми розглянемо наступну реалізацію списку LinkedList. Також порівняємо плюси та мінуси імплементацій цієї структури.
Тож почнемо,
Як ми побачили з попередньої імплементації List - головна проблема це зберігання коректного індексу для значень. Звичайно все залежить від вимог до структури даних та алгоритму реалізації. Але якщо у нас стоїть задача оптимізувати додавання / видалення елементів зі списку, то треба розібратися зі зв'язаним списком LinkedList. На імплементації ми побачимо що за оптимізацію, як то кажуть, треба чимось платити. У випадку алгоритмів — це як правило ресурси пам'яті space complexity.
Що ж таке цей зв'язаний список, пропоную розглянути приклад із реального життя. Наприклад, це може буде потяг:
І для того щоб знайти свій вагон, нам треба пройти з голови до зазначеного індексу / номеру вагона.
Визначимо абстрактну модель для зв'язаного списку LinkedList. Вона буде майже така сама, як і для List:
- Може додавати елемент або вставляти по індексу
- Може змінювати елемент по індексу / номеру
- Можемо зчитувати елемент за індексом
- Може видаляти будь-який елемент зі списку
Визначимо специфікацію абстрактної моделі для структури даних LinkedList / Зв'язаний список:
Імплементація для структури даних LinkedList / Зв'язаний список:
Git репозиторій https://github.com/kostrub-online/Computer-Science
Підсумуємо. Сьогодні ми розглянули та реалізували базову структуру Зв'язаний список LinkeList. Сподіваюсь, ви зрозуміли основний концепт алгоритму та плюси і мінуси.
Але це ні в якому разі не значить, що одна структура гірше за іншу, бо все залежить від конкретних вимог до алгоритмічної структури та ресурсів. Також ми трішки познайомились з рекурсією, яка нам і надалі буде допомагати з імплементацією різної логіки. Задавайте ваші питання та підписуйтесь на канал щоб не пропустити наступний топік - Stack. Далі більше!
0 Коментарі