Что такое односвязный список?

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

Основные характеристики:

• Узлы: Каждый узел содержит значение и указатель на следующий узел.
• Голова (Head): Указатель на первый узел списка.
• Хвост (Tail): Указатель на последний узел.
• Последовательность: Элементы расположены в определенной последовательности.
• Прямой доступ: Доступ к элементам возможен только последовательно, начиная с головы.
• Динамический размер: Размер списка может изменяться во время выполнения программы.

Преимущества:

• Эффективная вставка и удаление элементов в начале списка.
• Экономия памяти по сравнению с массивами при непредсказуемом размере данных.

Недостатки:

• Медленный доступ к элементам по индексу (требуется обход с начала).
• Требует дополнительной памяти для хранения указателей.

Простая реализация на PHP:

<?php

class Node {
    public $data;
    public $next;

    public function __construct($data, $next = null) {
        $this->data = $data;
        $this->next = $next;
    }
}

class SinglyLinkedList {
    public $head;

    public function __construct() {
        $this->head = null; // Список изначально пуст
    }

    // Добавление элемента в начало списка
    public function prepend($data) {
        $newNode = new Node($data, $this->head);
        $this->head = $newNode;
    }

    // Простой вывод элементов списка
    public function display() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }
}

// Пример использования
$list = new SinglyLinkedList();
$list->prepend(10);
$list->prepend(20);
$list->prepend(30);

$list->display(); // Вывод: 30 20 10 
?>

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