Работали ли вы со связными списками?

Да, работал. Хотя в PHP нет нативной необходимости часто реализовывать их с нуля (в отличие от C++), понимание принципов работы связных списков критически важно для алгоритмического мышления. Я реализовывал их для решения специфических задач и лучшего понимания структур данных.

Моя реализация двусвязного списка для задачи кэширования (LRU Cache):

class ListNode {
    public $key;
    public $value;
    public $prev = null;
    public $next = null;

    public function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
    }
}

class LRUCache {
    private $capacity;
    private $map = []; // Хеш-таблица для быстрого доступа
    private $head; // Псевдо-голова (самый новый)
    private $tail; // Псевдо-хвост (самый старый)

    public function __construct($capacity) {
        $this->capacity = $capacity;
        $this->head = new ListNode(null, null);
        $this->tail = new ListNode(null, null);
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    private function _addToHead($node) {
        // Вставляет узел сразу после псевдо-головы
        $node->prev = $this->head;
        $node->next = $this->head->next;
        $this->head->next->prev = $node;
        $this->head->next = $node;
    }

    private function _removeNode($node) {
        // Удаляет узел из списка
        $prev = $node->prev;
        $next = $node->next;
        $prev->next = $next;
        $next->prev = $prev;
    }

    public function get($key) {
        if (!isset($this->map[$key])) return -1;
        $node = $this->map[$key];
        $this->_removeNode($node); // Удаляем из текущей позиции
        $this->_addToHead($node);  // И добавляем в голову как самый новый
        return $node->value;
    }
    // ... методы put и другие
}

Ключевые преимущества и где я их применял:

• Динамический размер и O(1) вставка/удаление в начало/конец делают их идеальными для реализации очередей (FIFO) или стеков (LIFO). В PHP для этого часто используют SplDoublyLinkedList из стандартной библиотеки (SPL).
• Алгоритмические задачи: Многие задачи на LeetCode или Codility (например, разворот списка, обнаружение цикла, слияние отсортированных списков) требуют работы со связными списками.
• Понимание основ: Работа со списками помогает глубже понять, как работают более сложные структуры, такие как деревья и графы.