PhpLinkedList.md

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

Узел (Node)

Каждый узел в связном списке содержит данные и ссылку на следующий узел:

class Node {
    public $data;
    public $next;

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

Связный список (LinkedList)

Класс связного списка содержит методы для добавления, удаления и поиска узлов:

class LinkedList {
    private $head;

    public function __construct() {
        $this->head = null;
    }

    // Добавление узла в конец списка
    public function append($data) {
        $newNode = new Node($data);

        if ($this->head === null) {
            $this->head = $newNode;
            return;
        }

        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        $current->next = $newNode;
    }

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

    // Удаление узла по значению
    public function delete($data) {
        if ($this->head === null) {
            return;
        }

        if ($this->head->data === $data) {
            $this->head = $this->head->next;
            return;
        }

        $current = $this->head;
        while ($current->next !== null && $current->next->data !== $data) {
            $current = $current->next;
        }

        if ($current->next !== null) {
            $current->next = $current->next->next;
        }
    }

    // Поиск узла по значению
    public function find($data) {
        $current = $this->head;
        while ($current !== null && $current->data !== $data) {
            $current = $current->next;
        }
        return $current;
    }

    // Печать списка
    public function print() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }
}

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

$list = new LinkedList();

// Добавление элементов
$list->append(1);
$list->append(2);
$list->append(3);

// Печать списка
$list->print(); // 1 2 3

// Добавление элемента в начало
$list->prepend(0);
$list->print(); // 0 1 2 3

// Поиск элемента
$foundNode = $list->find(2);
echo $foundNode ? $foundNode->data : 'Not found'; // 2

// Удаление элемента
$list->delete(2);
$list->print(); // 0 1 3

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