Что можно положить в односвязный список?

Что можно положить в односвязный список?

Односвязный список (Singly Linked List) — это структура данных, которая может хранить данные любого типа. В Python и других языках программирования нет ограничений на тип значения, которое может содержаться в узле списка.

Типы данных

В односвязный список можно поместить:

1. Примитивные типы — целые числа (int), вещественные числа (float), строки (str), булевы значения (bool)
2. Сложные типы — списки (list), словари (dict), кортежи (tuple), множества (set)
3. Объекты пользовательских классов — экземпляры любого класса
4. Функции и методы — поскольку в Python функции являются объектами первого класса
5. None — нулевое значение
6. Смешанные типы — список может содержать элементы разных типов одновременно

Примеры реализации

Вот простая реализация односвязного списка:

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
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        return elements

Примеры использования

# Создаём список
linked_list = SinglyLinkedList()

# Добавляем примитивные типы
linked_list.append(42)
linked_list.append(3.14)
linked_list.append("привет")
linked_list.append(True)
linked_list.append(None)

# Добавляем сложные типы
linked_list.append([1, 2, 3])
linked_list.append({"ключ": "значение"})
linked_list.append((1, 2))

print(linked_list.display())
# Вывод: [42, 3.14, привет, True, None, [1, 2, 3], {ключ: значение}, (1, 2)]

# Добавляем объект класса
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def __repr__(self):
        return f"Person({self.name}, {self.age})"

person = Person("Иван", 30)
linked_list.append(person)

# Добавляем функцию
def my_function():
    return "Я функция"

linked_list.append(my_function)

Важные особенности

Динамическая типизация — В Python односвязный список работает с данными благодаря динамической типизации. Каждый узел может содержать объект любого типа, так как все значения в Python являются объектами.

Производительность — Время добавления и удаления элементов зависит от позиции:

• Добавление в начало: O(1)
• Добавление в конец: O(n) без хранения ссылки на последний узел
• Удаление элемента: O(n) в худшем случае

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

Сравнение со встроенными структурами

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