Структури даних у програмуванні: що це та які бувають
Виконуючи повсякденні завдання, програмісти працюють із різними структурами даних, кожної програми вона своя. Про найпопулярніші варіанти структури, їх особливості та способи застосування докладно розповімо в цій статті.
Що таке структура даних і для чого вона потрібна
Структура даних - це форма організації та зберігання інформації в комп'ютерній програмі. Вона підвищує ефективність управління за допомогою модифікації та обробки.
Завдяки структурам даних можна:
- Логічно структурувати та групувати інформацію, роблячи код більш зрозумілим та легко підтримуваним.
- Зберігати унікальні елементи, уникаючи дублювання інформації (наприклад, через хеш-таблиці).
- Оптимізувати процес пошуку, додавання, видалення та оновлення даних.
- Економно використовувати пам'ять, наприклад, через бітові та компактні масиви.
- Спростити виявлення та усунення помилок.
Класи структур даних
На практиці виділяються основні структури даних:
- Примітивна. Має фіксовану пам'ять і представляє прості значення: цілі числа, символи та інше.
- Складна. Дозволяє зберігати безліч значень та працює з більш складними операціями: додавання, видалення, пошук, сортування даних тощо. буд. Сюди належать масиви, списки, вектори та інші типи структур.
- Лінійна. Характеризується збереженням елементів, які йдуть один за одним і доступні у певній послідовності. Прикладами лінійних структур даних є масиви, списки, стеки та черги.
- Нелінійна. Елементи можуть мати кілька зв'язків, утворюючи ієрархічні, мережеві чи довільні структури.Прикладами нелінійних структур є дерева та графи.
- Статистична. Має фіксований розмір пам'яті, що прискорює доступ до вибраних елементів.
- Напівстатистична. Комбінація статичних та динамічних елементів, що забезпечує баланс між ефективністю використання пам'яті та гнучкістю роботи з даними.
- Динамічний. Тут розмір та структура можуть змінюватися динамічно. Це робить управління даними гнучкішим і дозволяє проводити операції з конкретними елементами у будь-який момент.
Основні алгоритмічні типи структур даних
Хеш-таблиці
Невпорядкована колекція пар "ключ - значення", де кожен ключ унікальний. Хеш-таблиця використовується реалізації структур даних (map, dict, set тощо. буд.), особливо корисна для зберігання, пошуку та додавання елементів.
Операції з хеш-таблицями:
- Вставлення. Дозволяє додати до хеш-таблиці елемент із певним ключем. Спочатку ключ перетворюється на хеш-значення, потім розміщується у відповідному осередку таблиці.
- Видалення. Видаляє елемент із заданим ключем з хеш-таблиці. Спочатку ключ перетворюється на хеш-значення, після чого проводиться сама операція.
- Пошук. Допомагає знайти елемент у хеш-таблиці через унікальний ключ.
У хеш-таблицях можна проводити такі дії:
- Відновлення. Змінює значення наявного у таблиці елемента без переіндексації його ключа.
- Підрахунок елементів. Показує, скільки елементів знаходиться у хеш-таблиці.
- Дозвіл колізій. Застосовується, коли кілька ключів перетворюються на те саме хеш-значення. Помилки коригуються через операції «Пошук» та «Вставка».
Де застосовуються хеш-таблиці:
- Реалізація словників та асоціативних масивів.
- Кешування даних чи обчислень.
- Маркування відвіданих URL-адрес.
- Швидкий пошук та індексація даних (контакти, номери телефонів тощо) у CPaaS-сервісах на кшталт Exolve.
- Управління кешем об'єктів у додатках та іграх.
- Основа у багатьох базах даних для зберігання більшого обсягу даних.
Масиви
Це структура, яка дозволяє послідовно зберігати кілька елементів одного й того самого типу. Перейти до цих елементів можна через індекс - числове значення певної позиції, яке починається з 0. При цьому масиви бувають одновимірними та двовимірними, ними може бути кожен елемент.
Завдання масиву - організувати зручне сортування даних або пошук відповідного набору значень.
Операції з масивами:
- Додавання. Призначена для вставляння нового елемента в кінець існуючої структури даних.
- Відновлення. Дозволяє змінювати та надавати нові значення елементам.
- Видалення. Можна стискати, видаляючи елементи.
- Сортування порядку зростання або зменшення елементів, наприклад, через алгоритми швидкого або бульбашкового сортування.
- Копіювання елементів.
- Об'єднання. Для створення нових масивів з елементами двох або більше вихідних.
Де застосовуються масиви:
- Розв'язання матричних задач.
- Застосування алгоритму сортування.
- Реалізація стеків, черг, хеш-таблиць.
- Планування роботи процесора.
- Створення довідкової таблиці на комп'ютерах.
- Обробка мови, де кожен мовний сигнал є масивом.
- Робота з системами управління баз даних: облік книг, журналів чи статей, учнів та студентів, голосів та рішень тощо.
- Створення комп'ютерних ігор на зразок онлайн-шахів, зі збереженням минулих та поточних ходів гравця для вказівки позиції фігур.
Зв'язковий перелік
Непримітивна структура, яка створює колекції елементів у послідовному порядку.У цьому форматі вузли зберігаються в несуміжних осередках пам'яті.
Це гнучка структура, де можна взаємодіяти з елементами списку без попереднього виділення фіксованого обсягу пам'яті, як це робиться у тих же масивах.
Операції зі зв'язаними списками:
- Ініціалізація. Ініціювати список можна через створення головного вузла.
- Вставлення Дані можна додавати на початок, кінець або вказану позицію пов'язаного списку.
- Видалення. Робиться через оновлення посилання попереднього вузла, щоб вона вказувала на наступну комірку списку.
- Пошук. Пошук потрібного елемента починається з головного вузла і поширюється на наступні осередки до тих пір, поки відповідний елемент не буде знайдено.
- Оновлення. Проводиться шляхом зміни даних, які знаходяться у вибраному елементі.
- Обхід По вузлах зв'язаного списку можна переміщатися, починаючи з головного вузла і слідуючи посиланням на наступні елементи, аж до кінця списку.
- Звернення списку. Зв'язаний список можна звернути назад, оновивши посилання кожного вузла таким чином, щоб вони вказували на попередній, а не наступний елемент.
Де застосовуються зв'язкові списки:
- Виконує арифметичні операції з довгими цілими числами.
- Подання розріджених матриць.
- Пов'язане розміщення файлів.
- Відображення контейнерів зображень (для перегляду попередніх, поточних та наступних зображень).
- Циклічне планування для відстеження ходів у розрахованих на багато користувачів іграх.
- Упорядкований зв'язок пісень у плейлисті тощо.
Стек
Це лінійна структура, яка функціонує за принципом LIFO, де останній доданий елемент видалятиметься або вилучатиметься першим. Наприклад, при відкритті кількох вікон у Windows активним залишиться саме останнє задіяне вікно.
- Додавання. Елемент додається на вершину та замінює колишнє значення.
- Видалення. Виштовхування всіх елементів зі стека, що призводить до його очищення та відновлення порожнього стану.
- Читання головний елемент. Вилучення значення, яке було додано останнім і знаходиться у верхній частині стека.
Також зі стеком можна проводити такі дії:
- Перегляд. За допомогою цієї операції верхній елемент можна оглянути без видалення його.
- Розмір. Дозволяє переглянути кількість елементів.
- Пошук. Знаходить, повертає на позицію або повідомляє про відсутність конкретного елемента.
- Перевірка на порожнечу чи заповненість. Визначає наявність або відсутність даних у стеку.
Де застосовуються стеки:
- Обчислення та перетворення арифметичних виразів.
- Управління пам'яттю.
- Обробка функцій викликів.
- Перетворення виразів з інфіксних на постфіксні.
- Відтворення наступної чи попередньої пісні.
- Відстеження раніше відвіданих сайтів у браузері.
- Формування журналу дзвінків у мобільному додатку.
Черга
Структура лінійного порядку, на відміну стека, заснована на принципі FIFO, де спочатку обробляється перший збережений елемент даних.
Черга добре справляється з управлінням завдань для ОС, обліком товарів складі, обробкою мережевих пакетів тощо.
- Додавання. Елемент можна додавати до кінця до моменту обробки.
- Видалення. Дозволяє витягти та обробити елемент із початку черги.
- Front.Читання або набуття значення, що знаходиться на початку, без його видалення.
- Rear. Читання або отримання значення елемента, що знаходиться наприкінці черги, без його видалення.
Де застосовується черга:
- Обробка веб-сайту трафіку.
- Планування та облік запитів до загального ресурсу: роздруківка на принтері, планування завдань процесора тощо. буд.
- Обробка переривання, планування завдань, перемикання додатків до ОС.
- Асинхронне передавання даних.
- Завантаження кількох фото чи відео тощо. буд.
Дерево
Ієрархічна структура даних із розгалуженою системою елементів. Найвищий вузол дерева називається "кореневим" - він веде до "батьківських" вузлів, які діляться на "дочірні". Структура завершується "аркушами" - кінцевою точкою без "дочірніх" вузлів. Всі елементи дерева з'єднані ребрами.
Дерева бувають бінарними, червоно-чорними, AVL тощо. буд. Кожен із видів має унікальні властивості та спосіб застосування. У будь-якого дерева:
- Кожен вузол, крім кореневого вузла, входить одна гілка.
- Існує вузол, до якого не входить жодна гілка.
Операції з деревами:
- Вставлення. Дозволяє додати новий вузол відповідно до правил, властивих конкретному типу дерева. У двійковому пошуковому дереві новий вузол вставляється за умови збереження порядку елементів.
- Балансування. У деяких типах дерев (AVL, червоно-чорні) можна перевірити, наскільки збалансовані та рівномірні «ребра».
- Обхід. Допомагає відвідати всі вузли дерева у певному порядку. Для цього можна використовувати прямий, обернений, симетричний метод обходу.
- Пошук. Знаходить вузол за заданим ключем або значенням. Процедура починається з кореня і рекурсивно рухається до отримання результату.
- Видалення.Видалення вузла з дерева та коригування структури для підтримки балансу чи інших властивостей.
Де застосовуються дерева:
- Моделювання та управління поведінкою персонажів у відеоіграх.
- Додавання індексів до баз даних.
- Структурування файлової системи.
- Створення та організація ієрархії завдань та завдань у системах управління проектами.
- Подання синтаксичної структури програмного коду в компіляторах та аналізаторах.
- Створення ієрархічних меню та деревоподібних структур навігації.
Граф
Нелінійна абстрактна структура даних, що складається з фіксованого кінцевого набору вузлів або вершин.
Графи широко застосовуються в алгоритмах і структурах даних, наприклад, у комп'ютерній графіці, маршрутизації в мережах та інших областях програмування.
- Додавання вершини Створює в графі нову вершину.
- Додавання ребра. Зв'язує дві вершини, задає напрямок і за необхідності вага ребра.
- Видалення вершини. Виключає з графа вибрану вершину та пов'язані з нею ребра.
- Видалення ребра. Розриває з'єднання між двома вершинами, скасовуючи вказане ребро.
- Перевірка властивостей графа Включає аналіз різних характеристик графа: спрямованість, ациклічність, зв'язність, наявність циклів та інших властивостей — для забезпечення коректності та відповідності вимогам завдання.
- Обчислення найкоротших шляхів між вершинами. Це робиться за допомогою алгоритмів Дейкстри, Флойда – Уоршелла та інших методів.
Де застосовуються графи:
- Подання потоку обчислень.
- Розподіл ресурсів у операційній системі.
- Моделювання дружніх зв'язків та взаємодій між користувачами соціальних мереж.
- Оптимізація дорожніх мереж, планування маршрутів, керування транспортним рухом та GPS-навігації.
- Подання біохімічних мереж, геномних даних та аналізу взаємодії білків у молекулярній біології.
- Відображення синтаксичних та семантичних відносин між словами у тексті.
- Бронювання номерів у готелях.
Висновок
Існує безліч класів і типів структур даних — кожен зі своїми особливостями, перевагами та недоліками.
10 типів структур даних, які потрібно знати
Катерина Малахова, редактор-фрілансер, спеціально для блогу Нетології адаптувала статтю Beau Carnes про основні типи структур даних.
"Погані програмісти думають про код. Хороші програмісти думають про структури даних та їх взаємозв'язки", - Лінус Торвальдс, творець Linux.
Структури даних відіграють важливу роль у процесі розробки ПЗ, а ще по них часто ставлять питання на співбесідах для розробників.
У цій статті я покажу вам 10 найпоширеніших структур даних.Для кожної з них наведено відео та приклади їх реалізації на JavaScript.
Зверніть увагу, деякі структури даних включають тимчасову складність у нотації «великого О».Це стосується не всіх їх, оскільки іноді тимчасова складність залежить від реалізації. Якщо ви хочете дізнатися більше про нотацію «великого О», перегляньте це відео від Briana Marie.
У статті я наводжу приклади реалізації цих структур даних на JavaScript: вони також стануть у нагоді, якщо ви використовуєте низькорівневу мову на кшталт С. Багато високорівневих мов, включаючи JavaScript, вже вбудовані реалізації більшості структур даних, про які піде мова. Тим не менш, такі знання стануть серйозною перевагою при пошуку роботи та стануть у нагоді при написанні високопродуктивного коду.
Зв'язкові списки
Зв'язковий список – одна з базових структур даних. Її часто порівнюють з масивом, оскільки багато інших структур можна реалізувати за допомогою або масиву, або зв'язкового списку. У цих двох типів є переваги та недоліки.
Так влаштований зв'язковий перелік
Зв'язковий список складається із групи вузлів, які разом утворюють послідовність. Кожен вузол містить дві речі: фактичні дані, які в ньому зберігаються (це можуть бути дані будь-якого типу) та покажчик (або посилання) на наступний вузол у послідовності. Також існують двозв'язкові списки: у них кожен вузл має покажчик і на наступний, і на попередній елемент у списку.
Основні операції у зв'язковому списку включають додавання, видалення та пошук елемента у списку.
Тимчасова складність зв'язкового списку
Вправи від freeCodeCamp
Стеки
Стек — це базова структура даних, яка дозволяє додавати чи видаляти елементи лише на її початку. Вона схожа на стопку книг: якщо ви хочете поглянути на книгу в середині стека, спершу доведеться прибрати лежачі зверху.
Стек організований за принципом LIFO (Last In First Out, "останнім прийшов - першим вийшов"). Це означає, що останній елемент, який ви додали до стек, першим вийде з нього.
У стеках можна виконувати три операції: додавання елемента (push), видалення елемента (pop) та відображення вмісту стека (pip).
Тимчасова складність стеку
Вправи від freeCodeCamp
Черги
Цю структуру можна як черга в продуктовому магазині. Першим обслуговують того, хто прийшов на початку — все як у житті.
Так влаштована черга
Черга влаштована за принципом FIFO (First In First Out, "перший прийшов - перший вийшов"). Це означає, що видалити елемент можна тільки після того, як були прибрані раніше додані елементи.
Черга дозволяє виконувати дві основні операції: додавати елементи до кінця черги (enqueue) і видаляти перший елемент (dequeue).
Тимчасова складність черги
Вправи від freeCodeCamp
Безліч
Так виглядає безліч
Багато зберігає значення даних без певного порядку, не повторюючи їх. Воно дозволяє не тільки додавати та видаляти елементи: є ще кілька важливих функцій, які можна застосовувати до двох множин відразу.
- Об'єднання комбінує всі елементи з двох різних множин, перетворюючи їх на одну (без дублікатів).
- Перетин аналізує дві множини і створює ще один із тих елементів, які присутні в обох початкових множинах.
- Різниця виводить список елементів, які є в одному множині, але відсутні в іншому.
- Підмножина видає булеве значення, яке показує, чи включає одна множина всі елементи іншої множини.
Вправи від freeCodeCamp
- Create a Set Class
- Remove from a Set
- Size of the Set
- Perform a Union on Two Sets
- Perform an Intersection on Two Sets of Data
- Perform a Difference on Two Sets of Data
- Perform a Subset Check on Two Sets of Data
- Create and Add to Sets in ES6
- Remove items from a set in ES6
- Use .has and .size on an ES6 Set
- Use Spread and Notes for ES5 Set() Integration
Map
Map — це структура, яка зберігає дані в парах ключ/значення, де кожен ключ є унікальним. Іноді її також називають асоціативним масивом чи словником. Map часто використовується для швидкого пошуку даних. Вона дозволяє робити такі речі:
- додавати пари до колекції;
- видаляти пари з колекції;
- змінювати існуючу пару;
- шукати значення, пов'язане із певним ключем.
Так влаштовано структуру map
Вправи від freeCodeCamp
Хеш-таблиці
Так працюють хеш-таблиця та хеш-функція
Хеш-таблиця - це схожа на Map структура, яка містить пари ключ/значення. Вона використовує хеш-функцію для обчислення індексу в масиві блоків даних, щоб знайти бажане значення.
Зазвичай хеш-функція приймає рядок символів як вступні дані і виводить числове значення. Для того самого введення хеш-функція повинна повертати однакове число. Якщо два різних введення хешуються з тим самим підсумком, виникає колізія. Мета в тому, щоб таких випадків було якнайменше.
Таким чином, коли ви вводите пару ключ/значення в хеш-таблицю, ключ проходить через хеш-функцію і перетворюється на число. Надалі ця кількість використовується як фактичний ключ, який відповідає певному значенню. Коли ви введете той самий ключ, хеш-функція обробить його і поверне такий же числовий результат. Потім цей результат буде використано для пошуку пов'язаного значення. Такий підхід помітно зменшує середній час пошуку.
Тимчасова складність хеш-таблиці
Вправи від freeCodeCamp
Двійкове дерево пошуку
Двійкове дерево пошуку
Дерево - це структура даних, що складається з вузлів. Їй притаманні такі властивості:
- Кожне дерево має кореневий вузол (нагорі).
- Кореневий вузол має нуль чи більше дочірніх вузлів.
- Кожен дочірній вузол має нуль або більше дочірніх вузлів, і таке інше.
Двійковий дерево пошуку має дві додаткові властивості:
- Кожен вузол має до двох дочірніх вузлів (нащадків).
- Кожен вузол менше своїх нащадків праворуч, яке нащадки ліворуч менше його самого.
Двійкові дерева пошуку дозволяють швидко знаходити, додавати та видаляти елементи. Вони влаштовані так, що час кожної операції пропорційний до логарифму загального числа елементів у дереві.
Тимчасова складність двійкового дерева пошуку
Вправи від freeCodeCamp
- Find the Minimum and Maximum Value in a Binary Search Tree
- Add a New Element to a Binary Search Tree
- Check if an Element is Present in a Binary Search Tree
- Find the Minimum and Maximum Height of a Binary Search Tree
- Use Depth First Search in a Binary Search Tree
- Use Breadth First Search in a Binary Search Tree
- Delete a Leaf Node in a Binary Search Tree
- Delete a Node with One Child in a Binary Search Tree
- Delete a Node with Two Children in a Binary Search Tree
- Invert a Binary Tree
Префіксне дерево
Префіксне (навантажене) дерево – це різновид дерева пошуку. Воно зберігає дані в мітках, кожна з яких є вузол на дереві. Такі структури часто використовують, щоб зберігати слова та виконувати швидкий пошук за ними, наприклад, для функції автозаповнення.
Так влаштовано префіксне дерево
Кожен вузол у префіксному мовному дереві містить одну літеру слова. Щоб скласти слово, потрібно слідувати гілками дерева, проходячи по одній букві за раз.Дерево починає розгалужуватися, коли порядок літер відрізняється від інших слів, що є в ньому, або коли слово закінчується. Кожен вузол містить літеру (дані) та булеве значення, яке вказує, чи є він останнім у слові.
Подивіться на ілюстрацію та спробуйте скласти слова. Завжди починайте з кореневого вузла вгорі та спускайтеся вниз. Це дерево містить такі слова: ball, bat, doll, do, dork, dorm, send, sense.
Вправи від freeCodeCamp
Двійкова купа
Двійкова купа – ще одна деревоподібна структура даних. У ній у кожного вузла трохи більше двох нащадків. Також вона є досконалим деревом: це означає, що в ній повністю зайняті даними всі рівні, а останній заповнений зліва направо.
Так влаштовані мінімальна та максимальна купи
Двійкова купа може бути мінімальною або максимальною. У максимальній купі ключ будь-якого вузла завжди більше ключів його нащадків або дорівнює їм. У мінімальній купі все влаштовано навпаки: ключ будь-якого вузла менший за ключі його нащадків або дорівнює їм.
Порядок рівнів у двійковій купі важливий, на відміну порядку вузлів одному й тому рівні. На ілюстрації видно, що у мінімальній купі третьому рівні значення йдуть за порядку: 10, 6 і 12.
Тимчасова складність двійкової купи
Вправи від freeCodeCamp
Граф
Графи - це сукупності вузлів (вершин) та зв'язків між ними (ребер). Також їх називають мережами.
За таким принципом влаштовані соціальні мережі: вузли – це люди, а ребра – їхні стосунки.
Графи поділяються на два основні типи: орієнтовані та неорієнтовані. У неорієнтованих графів ребра між вузлами немає якогось напрями, тоді як і ребер в орієнтованих графах воно є.
Найчастіше граф зображують у якомусь із двох видів: це може бути список суміжності або матриця суміжності.
Граф у вигляді матриці суміжності
Список суміжності можна представити як перелік елементів, де ліворуч знаходиться один вузол, а праворуч — решта всіх вузлів, з якими він з'єднується.
Матриця суміжності - це сітка з числами, де кожен рядок або колонка відповідають окремому вузлу в графі. На перетині ряду та колонки знаходиться число, яке вказує на наявність зв'язку. Нулі означають, що вона відсутня; одиниці - що зв'язок є. Щоб позначити вагу кожного зв'язку, використовують числа більше одиниці.
Існують спеціальні алгоритми перегляду ребер і вершин у графах — звані алгоритми обходу. До їх основних типів відносять пошук у ширину (breadth-first search) та в глибину (depth-first search). Як варіант, за допомогою їх можна визначити, наскільки близько до кореневого вузла знаходяться ті чи інші вершини графа. У відео нижче показано, як на JavaScript виконати пошук завширшки.
Тимчасова складність списку суміжності (графа)
Вправи від freeCodeCamp
Дізнатись більше
Якщо до цього ви ніколи не стикалися з алгоритмами або структурами даних, і у вас немає будь-якої підготовки в галузі ІТ, найкраще підійде книга Grokking Algorithms. У ній матеріал подано доступно і з кумедними ілюстраціями (їхній автор — провідний розробник в Etsy), у тому числі й за деякими структурами даних, які ми розглянули в цій статті.
Думка автора та редакції може не збігатися. Бажаєте написати колонку для «Нетології»? Читайте наші умови публікації.
Середня оцінка 5 / 5. Всього проголосувало 1
10 типів структур даних, які потрібно знати + відео та вправи
Катерина Малахова, редактор-фрілансер, спеціально для блогу Нетології адаптувала статтю Beau Carnes про основні типи структур даних.
«Погані програмісти думають про код. Хороші програмісти думають про структури даних та їх взаємозв'язки», — Лінус Торвальдс, творець Linux.
