Что является типом и структурой данных?

Что является типом и структурой данных?

Это две взаимосвязанные, но разные концепции в программировании, которые часто путают.

Тип данных (Data Type)

Тип данных определяет:

• Какие значения может хранить переменная
• Какие операции можно выполнять
• Сколько памяти требуется для хранения
• Как интерпретировать биты в памяти

Примитивные типы в Python:

# Целые числа (int)
age = 25
print(type(age))  # <class 'int'>

# Вещественные числа (float)
price = 99.99
print(type(price))  # <class 'float'>

# Строки (str)
name = "Alice"
print(type(name))  # <class 'str'>

# Булевы значения (bool)
is_active = True
print(type(is_active))  # <class 'bool'>

# None
empty = None
print(type(empty))  # <class 'NoneType'>

Свойства типов:

# Размер в памяти
import sys
print(sys.getsizeof(42))        # 28 байт для int
print(sys.getsizeof(3.14))      # 24 байта для float
print(sys.getsizeof("hello"))   # 54 байта для str

# Допустимые операции
print(5 + 3)        # int: сложение
print(5 * 2)        # int: умножение
print("hi" + "!")   # str: конкатенация
print("x" * 3)      # str: повтор

# Недопустимые
# print(5 + "text")  # TypeError: can't add int and str

Структура данных (Data Structure)

Структура данных — это способ организации и хранения данных в памяти для эффективного доступа и модификации.

Отличие от типа: структура определяет как данные организованы, типы определяют какие данные хранятся.

Базовые структуры данных в Python:

1. Массив (Array) / Список (List)

# Список — динамический массив
students = ["Alice", "Bob", "Charlie"]
print(students[0])        # O(1) доступ
students.append("David")  # O(1) в конце
students.insert(1, "Eve") # O(n) посередине

2. Кортеж (Tuple)

# Неизменяемый список — быстрее и экономнее
coordinates = (10, 20)
print(coordinates[0])  # O(1)
# coordinates[0] = 15  # TypeError: 'tuple' object does not support item assignment

3. Словарь (Dictionary) / Хеш-таблица (Hash Table)

# Быстрый поиск по ключам
user = {"name": "Alice", "age": 30, "city": "NYC"}
print(user["name"])      # O(1) доступ по ключу
user["email"] = "a@example.com"  # O(1) вставка

4. Множество (Set)

# Уникальные значения, быстрый поиск
tags = {"python", "django", "rest-api"}
print("python" in tags)  # O(1) проверка принадлежности
tags.add("fastapi")      # O(1) добавление

5. Стек (Stack)

# LIFO — Last In, First Out
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):     # добавить в конец
        self.items.append(item)
    
    def pop(self):            # удалить из конца
        return self.items.pop()
    
    def peek(self):           # посмотреть верх
        return self.items[-1]

stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # 2

6. Очередь (Queue)

# FIFO — First In, First Out
from collections import deque

queue = deque()
queue.append(1)      # добавить в конец
queue.append(2)
print(queue.popleft())  # 1 — удалить из начала

7. Связный список (Linked List)

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, value):     # O(n)
        node = Node(value)
        if not self.head:
            self.head = node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = node
    
    def display():
        current = self.head
        while current:
            print(current.value, end=" -> ")
            current = current.next

8. Дерево (Tree) / Двоичное дерево поиска (BST)

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)

9. Граф (Graph)

# Граф — вершины и рёбра
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Поиск в глубину (DFS)
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

dfs(graph, 'A')  # A B D C

Сравнение типов и структур:

Типы данных:

• Определяют значение (int, str, float)
• Примитивные или составные
• Часть языка программирования

Структуры данных:

• Организуют коллекции значений
• Определяют, как получать доступ
• Реализуются с использованием типов

Выбор структуры данных:

# Быстрый поиск → Set или Dict
if user_id in user_ids:  # O(1) для set
    ...

# Порядок важен → List
logged_events = []  # сохраняет порядок

# LIFO операции → Stack
undo_stack.push(action)

# Иерархия → Tree
organization = TreeNode("CEO")

# Рекомендации → Graph
find_similar_users(user, graph)

Практический совет:

При выборе структуры данных анализируйте:

1. Частота операций: вставка, удаление, поиск
2. Требуемая сложность: O(1), O(n), O(log n)
3. Требуемая память: количество данных
4. Порядок данных: важен ли порядок