Каковы устройство и основные свойства односвязного списка?

Односвязный (или однонаправленный) список — это линейная структура данных, состоящая из последовательности узлов. Каждый узел хранит данные и ссылку (указатель) на следующий узел. Последний узел в списке указывает на null.

Ключевые характеристики:

• Динамический размер: Список может легко расти и сжиматься во время выполнения программы.
• Последовательный доступ: Для доступа к элементу с индексом n необходимо пройти через все n-1 предыдущих элементов. Произвольный доступ (как в массивах) неэффективен и имеет сложность O(n).
• Эффективная вставка/удаление: Вставка или удаление узла в начале списка — очень быстрая операция (O(1)), так как требует только изменения указателя head. Вставка в конец или середину требует обхода списка (O(n)).

Пример реализации на Python:

class Node:
    """Узел списка, хранящий данные и ссылку на следующий узел."""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """Класс, реализующий односвязный список."""
    def __init__(self):
        self.head = None # Начало списка

    # Метод для добавления элемента в конец списка
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

# Использование:
my_list = LinkedList()
my_list.append("A")
my_list.append("B")
my_list.append("C")

# Обход списка: my_list.head.data -> "A", my_list.head.next.data -> "B"

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