Какие существуют структуры данных?

Существуют следующие основные структуры данных:

Примитивные (Primitive):

• Целые числа (Integer)
• Числа с плавающей точкой (Floating-point numbers)
• Булевы значения (Boolean)
• Символы (Character)

Абстрактные (Abstract):

• Массив (Array): Упорядоченная коллекция элементов одного типа, доступ по индексу с постоянным временем.
• Связный список (Linked List): Коллекция узлов, каждый из которых содержит данные и ссылку на следующий узел. Добавление/удаление в начале/конце efficient, доступ по индексу - $O(n)$.
  • Односвязный (Singly Linked List)
  • Двусвязный (Doubly Linked List)
  • Циклический (Circular Linked List)
• Стек (Stack): Структура данных LIFO (Last-In, First-Out). Операции: push (добавление), pop (удаление), peek (просмотр верхнего элемента).

  struct Stack<Element> {
      private var elements: [Element] = []
  
      mutating func push(_ element: Element) {
          elements.append(element)
      }
  
      mutating func pop() -> Element? {
          return elements.popLast()
      }
  
      func peek() -> Element? {
          return elements.last
      }
  
      var isEmpty: Bool {
          return elements.isEmpty
      }
  }
  

• Очередь (Queue): Структура данных FIFO (First-In, First-Out). Операции: enqueue (добавление), dequeue (удаление), peek (просмотр первого элемента).

  struct Queue<Element> {
      private var elements: [Element] = []
  
      mutating func enqueue(_ element: Element) {
          elements.append(element)
      }
  
      mutating func dequeue() -> Element? {
          guard !elements.isEmpty else { return nil }
          return elements.removeFirst()
      }
  
      func peek() -> Element? {
          return elements.first
      }
  
      var isEmpty: Bool {
          return elements.isEmpty
      }
  }
  

• Хеш-таблица (Hash Table) / Словарь (Dictionary) / Ассоциативный массив (Associative Array): Коллекция пар "ключ-значение", позволяющая эффективный поиск, добавление и удаление по ключу, используя хеш-функцию.

  var dictionary = [String: Any]() // Пример словаря в Swift
  dictionary["key1"] = "value1"
  let value = dictionary["key1"]
  

• Множество (Set): Неупорядоченная коллекция уникальных элементов. Поддерживает операции: добавление, удаление, проверка на существование, объединение, пересечение, разность.

  var set: Set<Int> = [1, 2, 3] // Пример множества в Swift
  set.insert(4)
  let containsTwo = set.contains(2)
  

• Дерево (Tree): Иерархическая структура данных, состоящая из узлов, связанных ребрами. Имеет корневой узел и дочерние узлы.
  • Бинарное дерево (Binary Tree)
  • Бинарное дерево поиска (Binary Search Tree - BST)
  • Сбалансированное бинарное дерево (Balanced Binary Tree) - AVL, красно-черное дерево.
  • B-дерево (B-Tree)
• Граф (Graph): Набор вершин (узлов) и ребер (связей), соединяющих вершины. Может быть направленным или ненаправленным, взвешенным или невзвешенным.

Понимание этих структур данных критически важно для написания эффективного и масштабируемого кода. Выбор правильной структуры данных зависит от требований к производительности операций (поиск, вставка,удаление) и характера данных.