10 загальних структур даних, пояснених у відео та вправах

“Погані програмісти турбуються про код. Хороших програмістів турбує структура даних та їх взаємозв'язок ". - Лінус Торвальдс, творець Linux ** Оновлення ** Мій відео-курс про алгоритми вже працює! Ознайомтесь з алгоритмами в русі з публікацій Manning. Знизьте 39% на мій курс, використовуючи код ' 39carnes '! Або ви можете отримати знижку 50% на мій курс глибокого навчання в русі з кодом ' vlcarnes2 '.

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

Хороша новина полягає в тому, що вони в основному є лише спеціалізованими форматами для організації та зберігання даних.

Я навчу вас 10 найпоширеніших структур даних - прямо тут, у цій короткій статті.

Я вбудував відео, які створив для кожної з цих структур даних. Я також посилався на приклади коду для кожного з них, які показують, як їх реалізувати в JavaScript.

І щоб дати вам трохи практики, я зв’язав виклики з навчальної програми freeCodeCamp.

Зверніть увагу, що деякі з цих структур даних включають часову складність у позначеннях Big O. Це включено не для всіх, оскільки складність часу інколи залежить від того, як це реалізовано. Якщо ви хочете дізнатись більше про Big O Notation, перегляньте мою статтю про це або це відео Бріани Марі.

Також зауважте, що, хоча я показую, як реалізувати ці структури даних у JavaScript, для більшості з них вам ніколи не потрібно буде їх реалізовувати самостійно, якщо ви не використовували мову низького рівня, як C.

JavaScript (як і більшість мов високого рівня) має вбудовані реалізації багатьох із цих структур даних.

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

Зв’язані списки

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

Зв’язаний список складається з групи вузлів, які разом представляють послідовність. Кожен вузол містить дві речі: фактичні дані, що зберігаються (це можуть бути в основному дані будь-якого типу), і покажчик (або посилання) на наступний вузол у послідовності. Існують також подвійно зв’язані списки, де кожен вузол має вказівник як на наступний елемент, так і на попередній елемент у списку.

Найбільш основні операції у зв’язаному списку - це додавання елемента до списку, видалення елемента зі списку та пошук елемента у списку.

Код пов'язаного списку в JavaScript дивіться тут.

Складність часового списку

АлгоритмСереднійНайгірший випадок
Космос0 (n)0 (n)
Пошук0 (n)0 (n)
Вставити0 (1)0 (1)
Видалити0 (1)0 (1)

виклики freeCodeCamp

  • Робота з вузлами у зв’язаному списку
  • Створіть клас зв’язаного списку
  • Видалення елементів зі зв’язаного списку
  • Шукати у зв’язаному списку
  • Видалення елементів зі зв’язаного списку за покажчиком
  • Додавання елементів за певним індексом у зв’язаний список
  • Створіть подвійно пов’язаний список
  • Змінити подвійно пов’язаний список

Стеки

Стек - це основна структура даних, де ви можете вставляти або видаляти елементи лише у верхній частині стека. Це якось схоже на стос книг. Якщо ви хочете поглянути на книгу посередині стопки, ви повинні спочатку зняти всі книги над нею.

Стек вважається LIFO (Last In First Out) - це означає, що останній предмет, який ви помістили в стек, є першим елементом, який виходить із стека

Існує три основні операції, які можна виконувати над стеками: вставлення елемента в стек (так званий «push»), видалення елемента зі стека (так званий «поп») та відображення вмісту стека (іноді його називають «pip» ').

Код стека в JavaScript дивіться тут.

Складність часу стеку

АлгоритмСереднійНайгірший випадок
Космос0 (n)0 (n)
Пошук0 (n)0 (n)
Вставити0 (1)0 (1)
Видалити0 (1)0 (1)

виклики freeCodeCamp

  • Дізнайтеся, як працює стек
  • Створіть клас стека

Черги

Ви можете уявити чергу як групу людей у ​​продуктовому магазині. Перший у черзі - це перший, який подають. Так само, як черга.

Чергою вважається FIFO (First In First Out), щоб продемонструвати спосіб доступу до даних. Це означає, що після додавання нового елемента всі елементи, які були додані раніше, повинні бути видалені, перш ніж новий елемент можна буде видалити.

Черга має лише дві основні операції: чергування та вилучення. Enqueue означає вставлення елемента в задню частину черги, а dequeue - видалення переднього елемента.

Код черги в JavaScript дивіться тут.

Складність часу черги

АлгоритмСереднійНайгірший випадок
Космос0 (n)0 (n)
Пошук0 (n)0 (n)
Вставити0 (1)0 (1)
Видалити0 (1)0 (1)

виклики freeCodeCamp

  • Створіть клас черги
  • Створіть клас пріоритетних черг
  • Створіть кругову чергу

Набори

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

  • Union - поєднує всі елементи з двох різних наборів і повертає як новий набір (без дублікатів).
  • Перетин - Дано два набори, ця функція повертає інший набір, який містить усі елементи, що входять до обох наборів.
  • Різниця - повертає список елементів, які є в одному наборі, але НЕ в іншому наборі.
  • Підмножина - повертає логічне значення, яке показує, чи всі елементи одного набору включені в інший набір.

Тут перегляньте код для реалізації набору в JavaScript.

виклики freeCodeCamp

  • Створіть клас набору
  • Видалити з набору
  • Розмір набору
  • Виконайте об’єднання на двох наборах
  • Виконайте перетин двох наборів даних
  • Виконайте різницю у двох наборах даних
  • Виконайте перевірку підмножини двох наборів даних
  • Створення та додавання до наборів у ES6
  • Видаліть елементи з набору в ES6
  • Використовуйте .has та .size на наборі ES6
  • Використовуйте Spread та примітки для інтеграції ES5 Set ()

Карти

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

  • додавання пари до колекції
  • вилучення пари з колекції
  • модифікація існуючої пари
  • пошук значення, пов'язаного з певним ключем

Перегляньте код для реалізації карти в JavaScript тут.

виклики freeCodeCamp

  • Створіть структуру даних карти
  • Створіть ES6-карту JavaScript

Хеш-таблиці

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

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

Отже, коли ви вводите пару ключ / значення в хеш-таблицю, ключ пропускається через хеш-функцію і перетворюється на число. Потім це числове значення використовується як фактичний ключ, яким зберігається значення. При повторній спробі отримати доступ до тієї ж клавіші, функція хешування обробить ключ і поверне той самий числовий результат. Потім число буде використано для пошуку відповідного значення. Це забезпечує в середньому дуже ефективний час пошуку O (1).

Перегляньте код хеш-таблиці тут.

Складність часу хеш-таблиці

АлгоритмСереднійНайгірший випадок
Космос0 (n)0 (n)
Пошук0 (1)0 (n)
Вставити0 (1)0 (n)
Видалити0 (1)0 (n)

виклики freeCodeCamp

  • Створіть хеш-таблицю

Бінарне дерево пошуку

Дерево - це структура даних, що складається з вузлів. Вона має такі характеристики:

  1. Кожне дерево має кореневий вузол (вгорі).
  2. Кореневий вузол має нуль або більше дочірніх вузлів.
  3. Кожен дочірній вузол має нуль або більше дочірніх вузлів тощо.

Двійковий пошук дерево додає ці дві характеристики:

  1. Кожен вузол має до двох дітей.
  2. Для кожного вузла його ліві нащадки менше, ніж поточний вузол, що менше, ніж праві нащадки.

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

Перегляньте код двійкового дерева пошуку в JavaScript тут.

Складність часу двійкового пошуку

АлгоритмСереднійНайгірший випадок
Космос0 (n)0 (n)
Пошук0 (журнал n)0 (n)
Вставити0 (журнал n)0 (n)
Видалити0 (журнал n)0 (n)

виклики freeCodeCamp

  • Знайдіть мінімальне та максимальне значення у бінарному дереві пошуку
  • Додайте новий елемент до бінарного дерева пошуку
  • Перевірте, чи присутній елемент у бінарному дереві пошуку
  • Знайдіть мінімальну та максимальну висоту двійкового дерева пошуку
  • Використовуйте глибинний перший пошук у бінарному дереві пошуку
  • Використовуйте Breadth First Search у бінарному дереві пошуку
  • Видаліть листяний вузол у двійковому дереві пошуку
  • Видаліть вузол з однією дитиною в двійковому дереві пошуку
  • Видаліть вузол з двома дітьми в бінарному дереві пошуку
  • Інвертувати двійкове дерево

Тріє

Трі (вимовляється як "спробувати"), або дерево префіксів, є різновидом дерева пошуку. Trie зберігає дані з кроками, де кожен крок є вузлом у trie. Спроби часто використовуються для зберігання слів для швидкого пошуку, наприклад функції автоматичного заповнення слів.

Кожен вузол мовної триє містить одну букву слова. Ви стежите за гілками триє, щоб писати слово, по одній букві. Етапи починають розгалужуватися, коли порядок букв розходиться з іншими словами в триє або коли слово закінчується. Кожен вузол містить букву (дані) та логічну форму, яка вказує, чи є вузол останнім вузлом у слові.

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

Перегляньте код триє в JavaScript тут.

виклики freeCodeCamp

  • Створіть дерево пошуку Trie

Двійкова купа

Бінарний куп - це ще один тип деревної структури даних. Кожен вузол має щонайбільше двох дітей. Крім того, це ціле дерево. Це означає, що всі рівні заповнені повністю до останнього рівня, а останній - зліва направо.

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

Порядок між рівнями важливий, але порядок вузлів на одному рівні не важливий. На зображенні ви можете бачити, що третій рівень міні-купи має значення 10, 6 і 12. Ці цифри не в порядку.

Перегляньте код для купи в JavaScript тут.

Складність часу двійкової купи

АлгоритмСереднійНайгірший випадок
Космос0 (n)0 (n)
Пошук0 (1)0 (журнал n)
Вставити0 (журнал n)0 (журнал n)
Видалити0 (1)0 (1)

виклики freeCodeCamp

  • Вставте елемент у максимальну купу
  • Видаліть елемент з максимальної купи
  • Реалізуйте сортування купи за мінімальною купою

Графік

Графіки - це колекції вузлів (їх також називають вершинами) та з'єднань (званих ребрами) між ними. Графіки також відомі як мережі.

Одним із прикладів графіків є соціальна мережа. Вузли - це люди, а краї - дружба.

Існує два основних типи графіків: спрямовані та ненаправлені. Непрямі графіки - це графіки без будь-якого напрямку по краях між вузлами. Навпаки, спрямовані графіки - це графіки з напрямком по краях.

Два найпоширеніші способи представлення графіка - це список суміжності та матриця суміжності.

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

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

Алгоритми обходу - це алгоритми обходу або відвідування вузлів на графіку. Основними типами алгоритмів обходу є пошук по ширині та пошук по глибині. Одне із застосувань - визначити, наскільки вузли близькі до кореневого вузла. Подивіться, як реалізувати пошук у широту в JavaScript у відео нижче.

Дивіться код для пошуку по ширині на графіку матриці суміжності в JavaScript.

Складність часу двійкового пошуку

АлгоритмЧас
ЗберіганняO (| V | + | E |)
Додайте вершинуO (1)
Додати крайO (1)
Видалити вершинуO (| V | + | E |)
Видаліть крайO (| E |)
ЗапитO (| V |)

виклики freeCodeCamp

  • Список суміжності
  • Матриця суміжності
  • Матриця випадковості
  • Широкий пошук
  • Глибина-перший пошук

Більше

Книга " Grokking Algorithms" - найкраща книга з цієї теми, якщо ви новачок у структурах даних / алгоритмах і не маєте знань з інформатики. У ньому використовуються легкі для розуміння пояснення та веселі, намальовані від руки ілюстрації (від автора, який є провідним розробником Etsy), щоб пояснити деякі структури даних, представлені в цій статті.

Grokking Algorithms: Ілюстрований посібник для програмістів та інших цікавих людей

Короткий зміст алгоритмів Grokking - це повністю проілюстрований, дружній посібник, який вчить вас застосовувати загальні алгоритми до ... www.amazon.com

Або ви можете ознайомитись з моїм відеокурсом, заснованим на цій книзі: Алгоритми в русі від Manning Publications. Знизьте 39% на мій курс, використовуючи код ' 39carnes '!