Skip to content

Data Structures

Структури даних⚑

Що таке структури даних?⚑

Summary

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

Структура даних — це спосіб організації інформації для більш ефективного використання. У програмуванні структурою зазвичай називають набір даних, пов'язаних певним чином. Наприклад, масив – це структура.

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

Характеристики структур даних

  • Дані у пам'яті представлені певним чином, що однозначно дозволяє визначити структуру.
  • Найчастіше до структури можна додати елемент або отримати. Ця властивість не постійна - бувають структури, які не можна змінювати після створення.
  • Існують алгоритми, які дозволяють взаємодіяти із цією структурою.

При цьому даних необов'язково має бути багато. Масив із одного елемента — вже структура даних.

Структури потрібні, щоб упорядковувати, шукати, аналізувати та використовувати дані із застосуванням алгоритмів програмування.

Масив⚑

Summary

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

Масив оптимальний для індексування, повільний для пошуку, вставки та видалення (якщо не робити цього в самому кінці масиву). Основний різновид - лінійні масиви, або однорозмірні. Їх розмір статичний, тобто при оголошенні лінійного масиву задається фіксований розмір. Динамічні масиви подібні до лінійних, але в них зарезервований простір для додаткових елементів. При заповненні динамічного масиву його вміст копіюється в масив більшого розміру. Двовимірні масиви мають два індекси x та y, як сітки або вкладені масиви

Ефективність операцій (О велике)

  • індексування - O(1)
  • пошук - O(n)
  • оптимізований пошук - O(log n)
  • вставка - O(n)

Динамічний масив⚑

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

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

Хеш таблиця⚑

Summary

Хеш-таблиця (Hash Table) — це структура даних, яка використовується для зберігання пар "ключ-значення" і забезпечує ефективний доступ до даних. Основною особливістю хеш-таблиці є використання хеш-функції для перетворення ключа в індекс масиву, де зберігається відповідне значення. Це дозволяє здійснювати пошук, вставку і видалення елементів з високою швидкістю.

Хеш-таблиці забезпечують складність вставки, видалення та доступ до елементів з постійним часом (O(1)).

Хеш-функція перетворює ключ у індекс масиву, за яким зберігається відповідне значення. При цьому можуть виникати колізії. Вони виникають, коли хеш-функція дає однаковий індекс для різних ключів. Існують різні методи вирішення колізій, такі як ланцюгове з'єднання (chaining) і відкрита адресація (open addressing).

Переваги хеш-таблиць

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

Ефективність (О велике)

  • Індексування- O(1)
  • Пошук - O(1)
  • Вставка - O(1)
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % size  # 'size' - size of hash table

    def insert(self, key, value):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])

    def search(self, key):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None

    def delete(self, key):
        index = self.hash_function(key)
        for i, pair in enumerate(self.table[index]):
            if pair[0] == key:
                del self.table[index][i]
                return

hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
print(hash_table.search("apple"))  # Output: 1
hash_table.delete("apple")
print(hash_table.search("apple"))  # Output: None

Зв'язаний список⚑

Summary

Зв'язаний список (Linked List) — це динамічна структура даних, яка складається з вузлів, де кожен вузол містить елемент даних і посилання на наступний вузол в списку. Зв'язані списки використовуються для зберігання послідовностей елементів і надають гнучкість для вставки та видалення елементів.

Властивості зв'язаного списку

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

Зв'язаний список розроблений для того щоб оптимізувати операції вставки та видалення. Він повільно працює при індексуванні та пошуку. Двозв'язаний список містить вузли, які посилаються на попередні вузли. Кільцевий зв'язковий список - це простий зв'язковий список, хвіст якого (останній вузол) посилається на голову (перший вузол).

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

Переваги зв'язаних списків

  • Динамічний розмір: Зв'язані списки можуть динамічно змінювати розмір під час виконання програми.
  • Ефективні вставки/видалення: Вставка і видалення елементів може бути виконана швидко, особливо при відомому місці в списку.

Недоліки зв'язаних списків

  • Доступ до елементів: Доступ до елементів менш ефективний, ніж у масивів.
  • Додаткова пам'ять: Кожен вузол потребує додаткової пам'яті для зберігання посилань.

Ефективність (О велике)

  • Індексування - O(n).
  • Пошук - O(n).
  • Оптимізований пошук - O(n).
  • Вставка - O(1).
class Node:
  def __init__(self, data):
      self.data = data
      self.next = None

class SinglyLinkedList:
  def __init__(self):
      self.head = None

  def append(self, data):
      new_node = Node(data)
      if not self.head:
          self.head = new_node
          return
      last = self.head
      while last.next:
          last = last.next
      last.next = new_node

Двозв'язний список⚑

Двозв'язний список (Doubly Linked List) - зв'язаний список, в якому кожен вузол містить посилання на наступний і попередній вузли.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

Різниця між масивом та зв'язаним списком⚑

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

Стек⚑

Summary

Стек (Stack) — це структура даних, яка працює за принципом LIFO (Last In, First Out), тобто останнім прийшов - першим вийшов. Це означає, що останній елемент, який був доданий до стеку, буде першим, який видаляється. Стек використовується в багатьох алгоритмах і програмах через його простоту і ефективність.

Застосування стеків

  • Рекурсія: Стеки використовуються для управління викликами рекурсивних функцій.
  • Управління пам'яттю: Стекові кадри (stack frames) використовуються для зберігання контексту виконання програм.
  • Відкочування операцій (Undo): Використовуються в текстових редакторах і інших додатках для реалізації функцій відміни дій.
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)  # Add item to the top

    def pop(self):
        if not self.is_empty():
            return self.items.pop()  # Remove and return the top item
        raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]  # Return the top item without removing it
        raise IndexError("peek from empty stack")

    def is_empty(self):
        return len(self.items) == 0  # Check if stack is empty

    def size(self):
        return len(self.items)  # Return the size of the stack

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2
print(stack.is_empty())  # Output: False
print(stack.size())  # Output: 2

Черга⚑

Summary

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

Черги є важливою структурою даних, яка дозволяє ефективно управляти послідовним доступом до ресурсів і процесів.

Застосування черг

  • Обробка завдань: Використовуються для управління завданнями або процесами, які потребують обробки в порядку їх надходження.
  • Черга друку: Управління завданнями друку в принтері.
  • Обробка подій: Черга подій в графічних інтерфейсах користувача (GUI).
  • Управління ресурсами: Використовуються в системах для управління чергами клієнтів, ресурсами або заявками.
class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)  # Add item to the end of the queue

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)  # Remove and return the front item
        raise IndexError("dequeue from empty queue")

    def peek(self):
        if not self.is_empty():
            return self.items[0]  # Return the front item without removing it
        raise IndexError("peek from empty queue")

    def is_empty(self):
        return len(self.items) == 0  # Check if the queue is empty

    def size(self):
        return len(self.items)  # Return the size of the queue

queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.peek())  # Output: 2
print(queue.is_empty())  # Output: False
print(queue.size())  # Output: 2

Граф⚑

Summary

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

Граф – це загальніший випадок дерева. Іноді дерева називають ациклічними графами.

Графи бувають орієнтовані та неорієнтовані, зважені та незважені.

У направленому графі ребра між вузлами мають напрямок та мають стрілки, а відносини діють в напрямку стрілки (А -> Б означає, що Б - сусід А, а А - батько Б). Отже порядок елементів важливий. У ненаправленому графі стрілок немає, а відносини діють у обидві сторони.

Застосування графів

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

Дерево⚑

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

Двійкове дерево⚑

Summary

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

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

Особливості структури

  • Ключ лівого дочірнього вузла менший, ніж у батьківського.
  • Ключ правого дочірнього вузла більший, ніж у батьківського.
  • Не може бути дублюючих вузлів.

Ефективність (О велике)

  • Індексування - O (log n).
  • Пошук - O (log n).
  • Вставка - O (log n).